A representation of trees by languages. I

DOI10.1016/0304-3975(78)90008-7zbMATH Open0377.68040OpenAlexW4213252762MaRDI QIDQ1246271FDOQ1246271

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

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

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
• Title not available (Why is that?)
• Reducing higher-order recursion scheme equivalence to coinductive higher-order constrained Horn clauses
• Decidable subcases of the equivalence problem for recursive program schemes
• Title not available (Why is that?)
• 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
• Model-checking games for typed \(\lambda\)-calculi
• The tree equivalence of linear recursion schemes
• 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)