Observations on the complexity of regular expression problems
From MaRDI portal
Publication:1149249
DOI10.1016/0022-0000(79)90002-3zbMath0453.68015MaRDI QIDQ1149249
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
time complexity; regular languages; equivalence problem; containment problem; regular grammars; program schemes; LL(k) grammars
68Q25: Analysis of algorithms and problem complexity
68Q45: Formal languages and automata
68Q60: Specification and verification (program logics, model checking, etc.)
Related Items
PARAMETER IDENTIFICATION APPROACHES TO FRACTAL MODEL OF MASS TRANSPORT FOR UNSATURATED SOILS, Descriptional and computational complexity of finite automata -- a survey, Descriptional and Computational Complexity of Finite Automata, A note on the inclusion problem for szilard languages†
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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