Observations on the complexity of regular expression problems

DOI10.1016/0022-0000(79)90002-3zbMath0453.68015OpenAlexW1966072464MaRDI QIDQ1149249

Harry B. III Hunt

Publication date: 1979

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(79)90002-3

zbMATH Keywords

time complexityregular languagesequivalence problemcontainment problemregular grammarsprogram schemesLL(k) grammars

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Specification and verification (program logics, model checking, etc.) (68Q60)

Related Items (4)

PARAMETER IDENTIFICATION APPROACHES TO FRACTAL MODEL OF MASS TRANSPORT FOR UNSATURATED SOILS ⋮ A note on the inclusion problem for szilard languages^† ⋮ Descriptional and computational complexity of finite automata -- a survey ⋮ Descriptional and Computational Complexity of Finite Automata

Cites Work

• Regular expressions and the equivalence of programs
• On formalised computer programs
• On Time Versus Space
• Computational Parallels between the Regular and Context-Free Languages
• On the equivalence and containment problems for context-free languages
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Observations on the complexity of regular expression problems