scientific article; zbMATH DE number 2086412

MaRDI QIDQ4736867zbMATH OpenFDO

Authors Holger Petersen

Publication date 11 August 2004

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
• scientific article; zbMATH DE number 2086619
• The membership problem for regular expressions with unordered concatenation and numerical constraints
• scientific article; zbMATH DE number 1929959
• 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:

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