Computational Parallels between the Regular and Context-Free Languages
From MaRDI portal
Publication:4151734
DOI10.1137/0207007zbMATH Open0374.68046OpenAlexW2002922589MaRDI QIDQ4151734FDOQ4151734
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
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
- More on Minimizing Finite Automata with Errors — Nondeterministic Machines
- On the equivalence, containment, and covering problems for the regular and context-free languages
- 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
- Decision problems for subregular classes
- Decidability of trajectory-based equations
- Decision Problems for Convex Languages
- 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)
