On bounded languages and reversal-bounded automata

DOI10.1016/J.IC.2015.11.007zbMath1333.68168OpenAlexW2186218795MaRDI 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

zbMATH Keywords

semilinear setcontext-free language (CFL)nondeterministic pushdown automaton (NPDA)reversal-boundedstratified linear set

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (2)

Descriptional Complexity of Bounded Regular Languages ⋮ On families of full trios containing counter machine 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

This page was built for publication: On bounded languages and reversal-bounded automata