Succinctness of the Complement and Intersection of Regular Expressions

DOI10.1145/2071368.2071372zbMath1351.68139OpenAlexW2082135413MaRDI QIDQ2946652

Wouter Gelade, Frank Neven

Publication date: 17 September 2015

Published in: ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2008/1354/

zbMATH Keywords

complexityregular expressionsintersectioncomplementsuccinctnessXML schema languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Descriptive complexity and finite models (68Q19)

Related Items (12)

Closure properties and descriptional complexity of deterministic regular expressions ⋮ On Boolean combinations forming piecewise testable languages ⋮ Deciding definability by deterministic regular expressions ⋮ Regular language representations in the constructive type theory of Coq ⋮ Simplifying XML schema: single-type approximations of regular tree languages ⋮ Negation-closure for JSON schema ⋮ PROVABLY SHORTER REGULAR EXPRESSIONS FROM FINITE AUTOMATA ⋮ Regular expression length via arithmetic formula complexity ⋮ Regular expression order-sorted unification and matching ⋮ Descriptional complexity of regular languages ⋮ Checking determinism of regular expressions with counting ⋮ A formalisation of the Myhill-Nerode theorem based on regular expressions

This page was built for publication: Succinctness of the Complement and Intersection of Regular Expressions