On bounded languages and reversal-bounded automata

DOI10.1016/J.IC.2015.11.007MaRDI QIDQ899318zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 1988976 (Why is no real title available?)
• scientific article; zbMATH DE number 3293666 (Why is no real title available?)
• A characterization of semilinear sets
• CHARACTERIZATIONS OF BOUNDED SEMILINEAR LANGUAGES BY ONE-WAY AND TWO-WAY DETERMINISTIC MACHINES
• Descriptional Complexity of Bounded Context-Free Languages
• Finite turns and the regular closure of linear context-free languages
• Linearity is polynomially decidable for realtime pushdown store automata
• On Context-Free Languages
• Reversal-Bounded Multicounter Machines and Their Decision Problems

Cited in

(14)

• CHARACTERIZATIONS OF BOUNDED SEMILINEAR LANGUAGES BY ONE-WAY AND TWO-WAY DETERMINISTIC MACHINES
• Automata with Reversal-Bounded Counters: A Survey
• scientific article; zbMATH DE number 6606353 (Why is no real title available?)
• On bounded languages and reversal-bounded automata
• The context-freeness problem is coNP-complete for flat counter systems
• scientific article; zbMATH DE number 2086620 (Why is no real title available?)
• 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

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)