Succinctness of the Complement and Intersection of Regular Expressions
From MaRDI portal
Publication:2946652
DOI10.1145/2071368.2071372zbMath1351.68139OpenAlexW2082135413MaRDI QIDQ2946652
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/
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