Computational Parallels between the Regular and Context-Free Languages

DOI10.1137/0207007MaRDI QIDQ4151734zbMATH OpenOpenAlexFDO

Authors H. B. III Hunt, Daniel J. Rosenkrantz

Publication date 1978

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0207007

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25)

Cited in

(17)

• Complexity metatheorems for context-free grammar problems
• Decision problems for convex languages
• On Boolean combinations forming piecewise testable languages
• Algebraic properties of substitution on trajectories
• Complexity of universality and related problems for partially ordered NFAs
• Observations on the complexity of regular expression problems
• On the equivalence, containment, and covering problems for the regular and context-free languages
• More on Minimizing Finite Automata with Errors — Nondeterministic Machines
• Descriptional and Computational Complexity of Finite Automata
• Pumping lemmas can be ``harmful
• Descriptional and computational complexity of finite automata -- a survey
• Classifying the computational complexity of problems
• Decidability of trajectory-based equations
• Decision Problems for Convex Languages
• Decision problems for subregular classes
• On the undecidability and descriptional complexity of synchronized regular expressions
• On the index of positive programmed formal languages

This page was built for publication: Computational Parallels between the Regular and Context-Free Languages

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