The membership question for ETOL-languages is polynomially complete
From MaRDI portal
Publication:1219165
DOI10.1016/0020-0190(75)90027-7zbMath0309.68065OpenAlexW2038287030MaRDI QIDQ1219165
Publication date: 1975
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(75)90027-7
Related Items (18)
Recurrent words and simultaneous growth in T0L systems ⋮ Pattern selector grammars and several parsing algorithms in the context- free style ⋮ Applications of scheduling theory to formal language theory ⋮ On Distinguishing NC $$^1$$ and NL ⋮ On the Kleijn-Rozenberg k-adjacent languages ⋮ Parallel complexity of iterated morphisms and the arithmetic of small numbers ⋮ Complexity of EOL structural equivalence ⋮ The Euclidean traveling salesman problem and a space-filling curve ⋮ Abstract grammars based on transductions ⋮ Complexity of E0L structural equivalence ⋮ ETOL-grammars and N-grammars ⋮ Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity ⋮ On the complexity of formal grammars ⋮ The complexity of the membership problem for some extensions of context-free languagest† ⋮ Complexity of some problems concerningL systems ⋮ Manipulating derivation forests by scheduling techniques ⋮ Grouped partial ET0L systems and parallel multiple context-free grammars ⋮ On the complexity of the recognition of parallel 2D-image languages
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A relationship between ETOL and EDTOL languages
- Optimization of LR(k) parsers
- On some families of languages related to developmental systems
- Description of developmental languages using recurrence systems
- TOL systems and languages
- Programmed Grammars and Classes of Formal Languages
- The complexity of theorem-proving procedures
This page was built for publication: The membership question for ETOL-languages is polynomially complete
