On jump-deterministic pushdown automata

DOI10.1007/BF01768471MaRDI QIDQ4141220zbMATH OpenOpenAlexFDO

Authors 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

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

Cites work

• A regularity test for pushdown machines
• A result on the equivalence problem for deterministic pushdown automata
• Characterization of flowchartable recursions
• Deterministic context free languages
• scientific article; zbMATH DE number 3490487 (Why is no real title available?)
• scientific article; zbMATH DE number 3560694 (Why is no real title available?)
• scientific article; zbMATH DE number 3293666 (Why is no real title available?)
• Jump PDA’s and Hierarchies of Deterministic Context-Free Languages
• On context-free languages and push-down automata
• On the Parsing of Deterministic Languages
• Properties of deterministic top-down grammars
• Real-Time Strict Deterministic Languages
• Regular canonical systems
• Regularity and Related Problems for Deterministic Pushdown Automata
• Strict deterministic grammars
• The decidability of equivalence for deterministic stateless pushdown automata
• Tree generating regular systems

Cited in

(14)

• Fundamental properties of infinite trees
• Some results on subclass containment problems for special classes of dpda's related to nonsingular machines
• A representation of trees by languages. II
• DPDA's in 'Atomic normal form' and applications to equivalence problems
• Tree equivalence of linear recursive schemata is polynomial-time decidable
• A representation of trees by languages. I
• The tree equivalence of linear recursion schemes
• Deep pushdown automata
• Pushdown tree automata
• Decidable subcases of the equivalence problem for recursive program schemes
• Automata with two-sided pushdowns defined over free groups generated by reduced alphabets
• The tree equivalence problem for linear recursion schemes
• New families of non real time dpda's and their decidability results
• A characterisation of deterministic context-free languages by means of right-congruences

This page was built for publication: On jump-deterministic pushdown automata

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