A regularity test for pushdown machines
From MaRDI portal
Publication:5537615
DOI10.1016/S0019-9958(67)90591-8zbMath0155.01901OpenAlexW2064465758WikidataQ56224610 ScholiaQ56224610MaRDI QIDQ5537615
Publication date: 1967
Published in: Information and Control (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0019-9958(67)90591-8
Related Items
On solving star equations, On the sizes of DPDAs, PDAs, LBAs, On a subclass of context-free groups, On the Descriptional Complexity of the Window Size for Deterministic Restarting Automata, Unnamed Item, A hierarchy of deterministic languages, Complexity of multi-head finite automata: origins and directions, A representation of trees by languages. II, Unnamed Item, A graph-based regularity test for deterministic context-free languages, THE PHENOMENON OF NON-RECURSIVE TRADE-OFFS, ON THE DESCRIPTIONAL COMPLEXITY OF THE WINDOW SIZE FOR DELETING RESTARTING AUTOMATA, A lower bound for the nondeterministic space complexity of context-free recognition, Unnamed Item, Self-Verifying Pushdown and Queue Automata, Set of memories of a D-graph, On the degrees of non-regularity and non-context-freeness, Simple context-free languages and free monadic recursion schemes, Pushdown automata and constant height: decidability and bounds, On jump-deterministic pushdown automata, Unnamed Item, Deterministic Pushdown Automata and Unary Languages, On LR(k) grammars and languages, Economy of description by parsers, DPDA's, and PDA's, On the separability of sparse context-free languages and of bounded rational relations, A representation of trees by languages. I, \(\omega\)-computations on deterministic pushdown machines, Simplification Problems for Deterministic Pushdown Automata on Infinite Words, Lower bounds on space complexity for contextfree recognition, On equivalence and subclass containment problems for deterministic context-free languages, Equivalent transformations of metalinear LA(1) grammars and unary recursive schemes, Set Automata, Deciding semantic finiteness of pushdown processes and first-order grammars w.r.t. bisimulation equivalence, Unnamed Item, DETERMINISTIC PUSHDOWN AUTOMATA AND UNARY LANGUAGES, LR-regular grammars - an extension of LR(k) grammars, Sur une propriété d'itération des langages algébriques déterministes, Theory of formal grammars, Decision problems among the main subfamilies of rational relations, New families of non real time dpda's and their decidability results, Some results on subclass containment problems for special classes of dpda's related to nonsingular machines, On reducing the number of stack symbols in a PDA
