Observations on the complexity of regular expression problems

DOI10.1016/0022-0000(79)90002-3MaRDI QIDQ1149249zbMATH OpenOpenAlexFDO

Authors H. 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

containment problemequivalence problemLL(k) grammarsprogram schemesregular grammarsregular languagestime complexity

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)

Cites work

• Computational Parallels between the Regular and Context-Free Languages
• scientific article; zbMATH DE number 3463159 (Why is no real title available?)
• scientific article; zbMATH DE number 3560737 (Why is no real title available?)
• scientific article; zbMATH DE number 3569849 (Why is no real title available?)
• scientific article; zbMATH DE number 3449757 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• scientific article; zbMATH DE number 3368555 (Why is no real title available?)
• scientific article; zbMATH DE number 3189697 (Why is no real title available?)
• On formalised computer programs
• On the equivalence and containment problems for context-free languages
• On Time Versus Space
• Regular expressions and the equivalence of programs

Cited in

(5)

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

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

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