Regularity and Related Problems for Deterministic Pushdown Automata
From MaRDI portal
Publication:4045649
DOI10.1145/321864.321865zbMath0293.68046OpenAlexW2079601390MaRDI QIDQ4045649
Publication date: 1975
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/321864.321865
Related Items
On the sizes of DPDAs, PDAs, LBAs, On a subclass of context-free groups, Rational subsets of partially reversible monoids, On the Descriptional Complexity of the Window Size for Deterministic Restarting Automata, Unnamed Item, A hierarchy of deterministic languages, Definability Results for Top-Down Tree Transducers, Descriptional complexity of two-way pushdown automata with restricted head reversals, Unnamed Item, More Concise Representation of Regular Languages by Automata and Regular Expressions, A graph-based regularity test for deterministic context-free languages, ON THE DESCRIPTIONAL COMPLEXITY OF THE WINDOW SIZE FOR DELETING RESTARTING AUTOMATA, More concise representation of regular languages by automata and regular expressions, Investigations on Automata and Languages Over a Unary Alphabet, Simple context-free languages and free monadic recursion schemes, On jump-deterministic pushdown automata, Unnamed Item, Unnamed Item, Deterministic Pushdown Automata and Unary Languages, Unnamed Item, On the separability of sparse context-free languages and of bounded rational relations, Descriptional Complexity of Two-Way Pushdown Automata with Restricted Head Reversals, Simplification Problems for Deterministic Pushdown Automata on Infinite Words, On equivalence and subclass containment problems for deterministic context-free languages, Set Automata, Deciding semantic finiteness of pushdown processes and first-order grammars w.r.t. bisimulation equivalence, DETERMINISTIC PUSHDOWN AUTOMATA AND UNARY LANGUAGES, Descriptional Complexity of Bounded Regular Languages, 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, Generalized parenthesis languages and minimization of their parenthesis parts, On reducing the number of stack symbols in a PDA
