A representation of trees by languages. I
From MaRDI portal
Publication:1246271
DOI10.1016/0304-3975(78)90008-7zbMath0377.68040MaRDI QIDQ1246271
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
68Q25: Analysis of algorithms and problem complexity
05C05: Trees
68Q45: Formal languages and automata
Related Items
Unnamed Item, 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