A representation of trees by languages. I

DOI10.1016/0304-3975(78)90008-7MaRDI QIDQ1246271zbMATH OpenOpenAlexFDO

Authors 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

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

Cites work

• scientific article; zbMATH DE number 3490487 (Why is no real title available?)
• scientific article; zbMATH DE number 3448092 (Why is no real title available?)
• scientific article; zbMATH DE number 3293666 (Why is no real title available?)
• scientific article; zbMATH DE number 3332047 (Why is no real title available?)
• A regularity test for pushdown machines
• Bottom-up and top-down tree transformations— a comparison
• Completeness results for the equivalence of recursive schemas
• Equivalence problems for deterministic context-free languages and monadic recursion schemes
• Forêts Algébriques et Homomorphismes Inverses
• IO and OI. II
• Initial Algebra Semantics and Continuous Algebras
• On context-free languages and push-down automata
• On jump-deterministic pushdown automata
• On the Parsing of Deterministic Languages
• Optimality of a Two-Phase Strategy for Routing in Interconnection Networks
• Program equivalence and context-free grammars
• Properties of deterministic top-down grammars
• Strict deterministic grammars
• The decidability of equivalence for deterministic stateless pushdown automata
• The equivalence problem for deterministic finite-turn pushdown automata
• The inclusion problem for simple languages
• Tree acceptors and some of their applications
• Tree-Manipulating Systems and Church-Rosser Theorems
• Un théorème de duplication pour les forets algébriques

Cited in

(19)

• Parameter reduction and automata evaluation for grammar-compressed trees
• A note on ordinal DFAs
• \(L(A)=L(B)\)? decidability results from complete formal systems
• The complexity of tree automata and XPath on grammar-compressed trees
• On branching and looping. I
• A hierarchy of deterministic languages
• An axiomatic approach to the Korenjak-Hopcroft algorithms
• scientific article; zbMATH DE number 3631912 (Why is no real title available?)
• Reducing higher-order recursion scheme equivalence to coinductive higher-order constrained Horn clauses
• Decidable subcases of the equivalence problem for recursive program schemes
• scientific article; zbMATH DE number 7136663 (Why is no real title available?)
• A closure property of deterministic context-free languages
• Recursion-closed algebraic theories
• An extended direct branching algorithm for checking equivalence of deterministic pushdown automata
• Some negative results concerning DPDA's
• The tree equivalence of linear recursion schemes
• Model-checking games for typed \(\lambda\)-calculi
• The simultaneous accessibility of two configurations of two equivalent DPDA's
• A hierarchy of real-time deterministic languages and their equivalence

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

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