Linearity is polynomially decidable for realtime pushdown store automata

DOI10.1016/S0019-9958(79)90134-7MaRDI QIDQ3048299zbMATH OpenFDO

Authors Sheila A. Greibach

Publication date 1979

Published in Information and Control (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0019-9958(79)90134-7

zbMATH Keywords

acceptancelinear context free languagespolynomial decidabilityreal-time pushdown store automata

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Formal languages and automata (68Q45)

Cited in

(7)

• Some results on subclass containment problems for special classes of dpda's related to nonsingular machines
• The interchange or pump (di)lemmas for context-free languages
• On equivalence and subclass containment problems for deterministic context-free languages
• Ogden's lemma for nonterminal bounded languages
• Comparisons between some pumping conditions for context-free languages
• New families of non real time dpda's and their decidability results
• On bounded languages and reversal-bounded automata

This page was built for publication: Linearity is polynomially decidable for realtime pushdown store automata

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