A representation of trees by languages. I

DOI10.1016/0304-3975(78)90008-7zbMath0377.68040MaRDI QIDQ1246271

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)90008-7

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C05: Trees

68Q45: Formal languages and automata

Related Items

Parameter reduction and automata evaluation for grammar-compressed trees, An extended direct branching algorithm for checking equivalence of deterministic pushdown automata, The complexity of tree automata and XPath on grammar-compressed trees, Some negative results concerning DPDA's, On branching and looping. I, A hierarchy of deterministic languages, A closure property of deterministic context-free languages, The simultaneous accessibility of two configurations of two equivalent DPDA's, Recursion-closed algebraic theories, A hierarchy of real-time deterministic languages and their equivalence, The tree equivalence of linear recursion schemes, \(L(A)=L(B)\)? decidability results from complete formal systems, A note on ordinal DFAs, Model-Checking Games for Typed λ-Calculi, An axiomatic approach to the Korenjak-Hopcroft algorithms, Decidable subcases of the equivalence problem for recursive program schemes, Unnamed Item

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
• IO and OI. II
• 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