Decidability of the finiteness of ranges of tree transductions
From MaRDI portal
Publication:1271464
DOI10.1006/inco.1998.2715zbMath1034.68525OpenAlexW1965983776MaRDI QIDQ1271464
Joost Engelfriet, Frank Drewes
Publication date: 24 November 2002
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/4042859980f8fde6397aa4cd4d089433c652a256
Related Items (11)
Decision Problems of Tree Transducers with Origin ⋮ Decision problems of tree transducers with origin ⋮ Branching synchronization grammars with nested tables ⋮ Deciding origin equivalence of weakly self-nesting macro tree transducers ⋮ The generative power of delegation networks ⋮ Deciding whether an attributed translation can be realized by a top-down transducer ⋮ Look-ahead removal for total deterministic top-down tree transducers ⋮ GETGRATS ⋮ Selected Decision Problems for Square-Refinement Collage Grammars ⋮ Tree-based picture generation ⋮ Output string languages of compositions of deterministic macro tree transducers
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Deterministic top-down tree transducers with iterated look-ahead
- Hyperedge replacement: grammars and languages
- Monadic second-order evaluations on tree-decomposable graphs
- Macro tree transducers
- High level tree transducers and iterated pushdown tree transducers
- The OI-hierarchy is closed under control
- The IO- and OI-hierarchies
- Attribute grammars and recursive program schemes. I. II
- Iterated stack automata and complexity classes
- On derivation trees of indexed grammars - an extension of the uvwxy- theorem
- A generalized approach to formal languages
- IO and OI. I
- IO and OI. II
- On tree transducers for partial functions
- Finite tree automata with cost functions
- On the decidability of certain integer subgraph problems on context-free graph languages
- Compositions of deterministic bottom-up, top-down, and regular look-ahead tree transformations
- Language theoretic and algorithmic properties of \(d\)-dimensional collages and patterns in a grid
- Top-down tree transducers with deterministic top-down look-ahead
- Generalized sequential machine maps
- An automata-theoretical characterization of the OI-hierarchy
- Complexity of some problems concerningL systems
- Bottom-up and top-down tree transformations— a comparison
- Top-down tree transducers with regular look-ahead
- Generalized Syntax Directed Translation, Tree Transducers, and Linear Space
- Tree transducers and tree languages
- Composition of top-down and bottom-up tree transductions
- Equivalence of finite-valued tree transducers is decidable
- Decidability of equivalence for a class of non-deterministic tree transducers
- Three hierarchies of transducers
- Superlinear deterministic top-down tree transducers
- Algebraic automata and context-free sets
- Mappings and grammars on trees
- Translations on a context free grammar
This page was built for publication: Decidability of the finiteness of ranges of tree transductions
