On jump-deterministic pushdown automata

DOI10.1007/BF01768471zbMath0365.02021OpenAlexW2073787041MaRDI QIDQ4141220

Bruno Courcelle

Publication date: 1977

Published in: Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01768471

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05)

Related Items

Unnamed Item, A representation of trees by languages. II, Decidable subcases of the equivalence problem for recursive program schemes, DPDA's in 'Atomic normal form' and applications to equivalence problems, A characterisation of deterministic context-free languages by means of right-congruences, Tree equivalence of linear recursive schemata is polynomial-time decidable, Pushdown tree automata, Deep pushdown automata, A representation of trees by languages. I, The tree equivalence of linear recursion schemes, Fundamental properties of infinite trees, 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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A result on the equivalence problem for deterministic pushdown automata
• Strict deterministic grammars
• Characterization of flowchartable recursions
• Regularity and Related Problems for Deterministic Pushdown Automata
• On the Parsing of Deterministic Languages
• The decidability of equivalence for deterministic stateless pushdown automata
• Jump PDA’s and Hierarchies of Deterministic Context-Free Languages
• Regular canonical systems
• Deterministic context free languages
• A regularity test for pushdown machines
• Tree generating regular systems
• Properties of deterministic top-down grammars
• Real-Time Strict Deterministic Languages
• On context-free languages and push-down automata