Succinctness of the Complement and Intersection of Regular Expressions

DOI10.1145/2071368.2071372MaRDI QIDQ2946652zbMATH OpenOpenAlexFDO

Authors 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

complementcomplexityintersectionregular expressionssuccinctnessXML schema languages

Mathematics Subject Classification ID

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

Recommendations

• Succinctness of the complement and intersection of regular expressions
• Succinctness of Regular Expressions with Interleaving, Intersection and Counting
• Succinctness of regular expressions with interleaving, intersection and counting
• Extended regular expressions: succinctness and decidability
• Extended Regular Expressions: Succinctness and Decidability
• On the intersection of regex languages with regular languages
• On a generalization of regular expressions
• scientific article; zbMATH DE number 7651219
• Simplifying regular expressions. A quantitative perspective
• Mathematical Foundations of Computer Science 2004

Cited in

(25)

• Regular language representations in the constructive type theory of Coq
• Intersection of \(-\omega \)-regular expressions
• Descriptional complexity of regular languages
• Complexity of regex crosswords
• Checking determinism of regular expressions with counting
• A formalisation of the Myhill-Nerode theorem based on regular expressions
• On Boolean combinations forming piecewise testable languages
• Deciding definability by deterministic regular expressions
• Closure properties and descriptional complexity of deterministic regular expressions
• Negation-closure for JSON schema
• Extended Regular Expressions: Succinctness and Decidability
• Succinctness of Regular Expressions with Interleaving, Intersection and Counting
• Simplifying XML schema: single-type approximations of regular tree languages
• scientific article; zbMATH DE number 1134629 (Why is no real title available?)
• Succinctness of the complement and intersection of regular expressions
• Provably shorter regular expressions from finite automata
• Expressive capacity of subregular expressions
• Mathematical Foundations of Computer Science 2004
• Regular expression length via arithmetic formula complexity
• Games for succinctness of regular expressions
• On concurrent program algebra and demonic automata
• Disambiguation of regular expressions with backreferences via term rewriting
• Optimal regular expressions for palindromes of given length
• Regular expression order-sorted unification and matching
• Succinctness of regular expressions with interleaving, intersection and counting

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2946652)