On efficient recognition of transductions and relations
From MaRDI portal
Publication:1066679
DOI10.1016/0304-3975(85)90132-XzbMath0578.68068OpenAlexW2031547912MaRDI QIDQ1066679
Jik H. Chang, Oscar H. Ibarra, Michael A. Palis
Publication date: 1985
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(85)90132-x
recognition algorithmscounter machinesrandom access machinepushdown machineslanguage recognitionlinear context-free languagesone- counter languages
Related Items (2)
Parallel parsing on a one-way linear array of finite-state machines ⋮ Notes on looping deterministic two-way pushdown automata
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Halting space-bounded computations
- Time complexity of languages recognized by one-way multihead pushdown automata
- Efficient recognition of rational relations
- A note on two-way nondeterministic pushdown automata
- General context-free recognition in less than cubic time
- On the computational power of pushdown automata
- Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata
- On two-way multihead automata
- Time and tape complexity of pushdown automaton languages
This page was built for publication: On efficient recognition of transductions and relations
