On bounded languages and reversal-bounded automata

DOI10.1016/J.IC.2015.11.007zbMATH Open1333.68168OpenAlexW2186218795MaRDI QIDQ899318FDOQ899318

Authors: Oscar H. Ibarra, B. 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

Recommendations

• On bounded languages and reversal-bounded automata
• A note on bounded-reversal multipushdown machines
• Automata with Reversal-Bounded Counters: A Survey
• ON THE EQUIVALENCE OF TWO-WAY PUSHDOWN AUTOMATA AND COUNTER MACHINES OVER BOUNDED LANGUAGES
• Descriptional complexity of bounded context-free languages

zbMATH Keywords

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Title not available (Why is that?)
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• CHARACTERIZATIONS OF BOUNDED SEMILINEAR LANGUAGES BY ONE-WAY AND TWO-WAY DETERMINISTIC MACHINES
• On Context-Free Languages
• Title not available (Why is that?)
• Descriptional Complexity of Bounded Context-Free Languages
• A characterization of semilinear sets
• Linearity is polynomially decidable for realtime pushdown store automata
• Finite turns and the regular closure of linear context-free languages
• Title not available (Why is that?)

Cited In (14)

• Automata with Reversal-Bounded Counters: A Survey
• Title not available (Why is that?)
• On bounded languages and reversal-bounded automata
• Title not available (Why is that?)
• The context-freeness problem is coNP-complete for flat counter systems
• Pushdown automata with reversal-bounded counters
• Closure under reversal of languages over infinite alphabets
• A generalization of the flip-flop lemma
• Bounded underapproximations
• Descriptional complexity of bounded regular languages
• On families of full trios containing counter machine languages
• A note on bounded-reversal multipushdown machines
• Quotients and Atoms of Reversible Languages
• CHARACTERIZATIONS OF BOUNDED SEMILINEAR LANGUAGES BY ONE-WAY AND TWO-WAY DETERMINISTIC MACHINES

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q899318)