The membership problem for regular expressions with intersection is complete in LOGCFL

DOI10.1007/3-540-45841-7_42MaRDI QIDQ4736867zbMATH OpenFDO

Authors Holger Petersen

Publication date 11 August 2004

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2285/22850513.htm

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Formal languages and automata (68Q45)

Recommendations

• Compressed membership problems for regular expressions and hierarchical automata
• Intersection of regular languages and star hierarchy
• The membership problem for regular expressions with unordered concatenation and numerical constraints
• An improved algorithm for the membership problem for extended regular expressions
• scientific article; zbMATH DE number 1134629

Cited in

(6)

• On the state complexity of partial derivative automata for regular expressions with intersection
• Expressive capacity of subregular expressions
• Subregular expressions with two operations
• On switching finite state automata
• On the complexity of timed pattern matching
• Succinctness of regular expressions with interleaving, intersection and counting

This page was built for publication: The membership problem for regular expressions with intersection is complete in LOGCFL

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