A representation of trees by languages. I

DOI10.1016/0304-3975(78)90008-7zbMath0377.68040OpenAlexW4213252762MaRDI 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

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Formal languages and automata (68Q45)

Related Items (18)

An axiomatic approach to the Korenjak-Hopcroft algorithms ⋮ The complexity of tree automata and XPath on grammar-compressed trees ⋮ Unnamed Item ⋮ On branching and looping. I ⋮ A hierarchy of deterministic languages ⋮ Decidable subcases of the equivalence problem for recursive program schemes ⋮ Unnamed Item ⋮ A note on ordinal DFAs ⋮ A closure property of deterministic context-free languages ⋮ The simultaneous accessibility of two configurations of two equivalent DPDA's ⋮ Recursion-closed algebraic theories ⋮ Parameter reduction and automata evaluation for grammar-compressed trees ⋮ 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 ⋮ Some negative results concerning DPDA's ⋮ Model-Checking Games for Typed λ-Calculi ⋮ An extended direct branching algorithm for checking equivalence of deterministic pushdown 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
• 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

This page was built for publication: A representation of trees by languages. I