A representation of trees by languages. II

DOI10.1016/0304-3975(78)90039-7zbMath0428.68088OpenAlexW1988436966MaRDI QIDQ1137390

Bruno Courcelle

Publication date: 1978

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(78)90039-7

zbMATH Keywords

reductionsrecursive program schemesdeterministic pushdown automataequivalence problemssimple deterministic tree grammars

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Specification and verification (program logics, model checking, etc.) (68Q60)

Related Items

Variétés d'automates descendants d'arbres infinis, Equivalences and transformations of regular systems - applications to recursive program schemes and grammars, Parameter-reduction of higher level grammars, The complexity of tree automata and XPath on grammar-compressed trees, Deterministic top-down tree automata with Boolean deterministic look-ahead, Unnamed Item, Decidable subcases of the equivalence problem for recursive program schemes, Unnamed Item, An undecidable property of context-free linear orders, Unnamed Item, DPDA's in 'Atomic normal form' and applications to equivalence problems, The IO- and OI-hierarchies, Unnamed Item, The monadic second-order logic of graphs. IX: Machines and their behaviours, Alphabetic tree relations, Variants of top-down tree transducers with look-ahead, Infinite trees in normal form and recursive equations having a unique solution, Basic tree transducers, On some classes of interpretations, The solutions of two star-height problems for regular trees, Recursion induction principle revisited, \(L(A)=L(B)\)? decidability results from complete formal systems, Fundamental properties of infinite trees, Infinitary tree languages recognized by \(\omega\)-automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Program equivalence and context-free grammars
• Un théorème de duplication pour les forets algébriques
• Completeness results for the equivalence of recursive schemas
• The inclusion problem for simple languages
• Equivalence problems for deterministic context-free languages and monadic recursion schemes
• Tree acceptors and some of their applications
• Strict deterministic grammars
• Optimality of a Two-Phase Strategy for Routing in Interconnection Networks
• On the Parsing of Deterministic Languages
• Bottom-up and top-down tree transformations— a comparison
• Initial Algebra Semantics and Continuous Algebras
• On jump-deterministic pushdown automata
• The decidability of equivalence for deterministic stateless pushdown automata
• Forêts Algébriques et Homomorphismes Inverses
• The equivalence problem for deterministic finite-turn pushdown automata
• A regularity test for pushdown machines
• Properties of deterministic top-down grammars
• Tree-Manipulating Systems and Church-Rosser Theorems
• On context-free languages and push-down automata