On bounded languages and reversal-bounded automata
From MaRDI portal
Publication:899318
DOI10.1016/j.ic.2015.11.007zbMath1333.68168MaRDI QIDQ899318
Oscar H. Ibarra, Bala Ravikumar
Publication date: 28 December 2015
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2015.11.007
semilinear set; context-free language (CFL); nondeterministic pushdown automaton (NPDA); reversal-bounded; stratified linear set
68Q45: Formal languages and automata
Related Items
On families of full trios containing counter machine languages, Descriptional Complexity of Bounded Regular Languages
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Finite turns and the regular closure of linear context-free languages
- A characterization of semilinear sets
- Linearity is polynomially decidable for realtime pushdown store automata
- Reversal-Bounded Multicounter Machines and Their Decision Problems
- CHARACTERIZATIONS OF BOUNDED SEMILINEAR LANGUAGES BY ONE-WAY AND TWO-WAY DETERMINISTIC MACHINES
- Descriptional Complexity of Bounded Context-Free Languages
- On Context-Free Languages