A comparison of tree transductions defined by monadic second order logic and by attribute grammars
From MaRDI portal
Publication:1582010
DOI10.1006/jcss.1999.1684zbMath0960.68086OpenAlexW2056445915MaRDI QIDQ1582010
Roderick Bloem, Joost Engelfriet
Publication date: 10 October 2000
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/e83997db1f674025079804a6e953604b8efeda11
Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Grammars and rewriting systems (68Q42)
Related Items (27)
Tree Transformations and Dependencies ⋮ Definable transductions and weighted logics for texts ⋮ The equivalence problem for deterministic MSO tree transducers is decidable ⋮ Decision problems of tree transducers with origin ⋮ A bottom-up characterization of deterministic top-down tree transducers with regular look-ahead ⋮ Weighted tree automata and weighted logics ⋮ Characterizing attributed tree translations in terms of macro tree transducers ⋮ On the power of tree-walking automata. ⋮ Deciding whether an attributed translation can be realized by a top-down transducer ⋮ Balancedness of MSO transductions in polynomial time ⋮ Unnamed Item ⋮ XML navigation and transformation by tree-walking automata and transducers with visible and invisible pebbles ⋮ RESEARCH FRONTIERS OF MEMBRANE COMPUTING: OPEN PROBLEMS AND RESEARCH TOPICS ⋮ COMPUTING BY COMMUNICATION IN NETWORKS OF MEMBRANES ⋮ GETGRATS ⋮ Storage-to-tree transducers with look-ahead ⋮ Recognizability, hypergraph operations, and logical types ⋮ Attribute grammars for unranked trees as a query language for structured documents ⋮ Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Determinacy and rewriting of functional top-down and MSO tree transformations ⋮ Streamable regular transductions ⋮ Monadic Datalog Tree Transducers ⋮ 10th Asian Logic Conference ⋮ Distributional Learning and Context/Substructure Enumerability in Nonlinear Tree Grammars ⋮ Extended multi bottom-up tree transducers
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Monadic second-order evaluations on tree-decomposable graphs
- Increasing modularity and language-independency in automatically generated compilers
- Macro tree transducers
- Composition and evaluation of attribute coupled grammars
- Tree transducers, L systems, and two-way machines
- The formal power of one-visit attribute grammars
- Attribute grammars and recursive program schemes. I. II
- The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability
- A regular characterization of graph languages definable in monadic second-order logic
- Context-free hypergraph grammars have the same term-generating power as attribute grammars
- Tree transducers with external functions
- Attribute grammars. Definitions, systems and bibliography
- Joint COMPUGRAPH/ SEMAGRAPH workshop on Graph rewriting and computation (SEGRAGRA '95). Selected papers from the workshop, Volterra, Italy, August 28 - September 1, 1995
- Monadic second-order definable graph transductions: a survey
- Synthesized and inherited functions. A new computational model for syntax-directed semantics
- Logical description of context-free graph languages
- The monadic second-order logic of graphs. XIII: Graph drawings with edge crossings
- Macro tree transducers, attribute grammars, and MSO definable tree translations.
- Attributed tree transducers cannot induce all deterministic bottom-up tree transformations
- Handle-rewriting hypergraph grammars
- Tree acceptors and some of their applications
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Weak Second‐Order Arithmetic and Finite Automata
- Easy problems for tree-decomposable graphs
- Decision Problems of Finite Automata Design and Related Arithmetics
- Parallel and two-way automata on directed ordered acyclic graphs
- Top-down tree transducers with regular look-ahead
- Handbook of Graph Grammars and Computing by Graph Transformation
- Algebraic automata and context-free sets
- Generalized finite automata theory with an application to a decision problem of second-order logic
- Semantics of context-free languages
- Translations on a context free grammar
This page was built for publication: A comparison of tree transductions defined by monadic second order logic and by attribute grammars
