Computational Parallels between the Regular and Context-Free Languages

DOI10.1137/0207007zbMath0374.68046OpenAlexW2002922589MaRDI QIDQ4151734

Daniel J. Rosenkrantz, Harry B. III Hunt

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

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

Related Items (15)

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

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