A comparison of tree transductions defined by monadic second order logic and by attribute grammars
From MaRDI portal
DOI10.1006/JCSS.1999.1684zbMATH Open0960.68086OpenAlexW2056445915MaRDI QIDQ1582010FDOQ1582010
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
Recommendations
- Macro tree transducers, attribute grammars, and MSO definable tree translations.
- Monadic Datalog Tree Transducers
- scientific article; zbMATH DE number 3858450
- A characterization of attributed tree transformations by a subclass of macro tree transducers
- Macro Tree Translations of Linear Size Increase are MSO Definable
Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Grammars and rewriting systems (68Q42)
Cites Work
- Title not available (Why is that?)
- Top-down tree transducers with regular look-ahead
- Handle-rewriting hypergraph grammars
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Easy problems for tree-decomposable graphs
- Monadic second-order definable graph transductions: a survey
- Title not available (Why is that?)
- Handbook of Graph Grammars and Computing by Graph Transformation
- Attribute grammars and recursive program schemes. I. II
- Attribute grammars. Definitions, systems and bibliography
- Tree transducers with external functions
- Weak Second‐Order Arithmetic and Finite Automata
- Title not available (Why is that?)
- Decision Problems of Finite Automata Design and Related Arithmetics
- Title not available (Why is that?)
- Title not available (Why is that?)
- 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
- The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability
- Monadic second-order evaluations on tree-decomposable graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Increasing modularity and language-independency in automatically generated compilers
- Composition and evaluation of attribute coupled grammars
- Tree acceptors and some of their applications
- Parallel and two-way automata on directed ordered acyclic graphs
- Algebraic automata and context-free sets
- Tree transducers, L systems, and two-way machines
- Logical description of context-free graph languages
- Macro tree transducers
- Macro tree transducers, attribute grammars, and MSO definable tree translations.
- The formal power of one-visit attribute grammars
- Title not available (Why is that?)
- Title not available (Why is that?)
- 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
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Synthesized and inherited functions. A new computational model for syntax-directed semantics
- Joint COMPUGRAPH/ SEMAGRAPH workshop on Graph rewriting and computation (SEGRAGRA '95). Selected papers from the workshop, Volterra, Italy, August 28 - September 1, 1995
- Attributed tree transducers cannot induce all deterministic bottom-up tree transformations
- The monadic second-order logic of graphs. XIII: Graph drawings with edge crossings
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (30)
- Title not available (Why is that?)
- Weighted tree automata and weighted logics
- Title not available (Why is that?)
- Recognizability, hypergraph operations, and logical types
- 10th Asian Logic Conference
- Tree Transformations and Dependencies
- Definable transductions and weighted logics for texts
- Storage-to-tree transducers with look-ahead
- Macro tree transducers, attribute grammars, and MSO definable tree translations.
- Determinacy and rewriting of functional top-down and MSO tree transformations
- Decision problems of tree transducers with origin
- On the power of tree-walking automata.
- The equivalence problem for deterministic MSO tree transducers is decidable
- Extended multi bottom-up tree transducers
- Attribute grammars for unranked trees as a query language for structured documents
- Deciding whether an attributed translation can be realized by a top-down transducer
- Streamable regular transductions
- RESEARCH FRONTIERS OF MEMBRANE COMPUTING: OPEN PROBLEMS AND RESEARCH TOPICS
- Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity
- Distributional Learning and Context/Substructure Enumerability in Nonlinear Tree Grammars
- Monadic Datalog Tree Transducers
- XML navigation and transformation by tree-walking automata and transducers with visible and invisible pebbles
- Attributed tree transducers for partial functions
- Balancedness of MSO transductions in polynomial time
- Title not available (Why is that?)
- GETGRATS
- Characterizing attributed tree translations in terms of macro tree transducers
- COMPUTING BY COMMUNICATION IN NETWORKS OF MEMBRANES
- Title not available (Why is that?)
- A bottom-up characterization of deterministic top-down tree transducers with regular look-ahead
This page was built for publication: A comparison of tree transductions defined by monadic second order logic and by attribute grammars
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1582010)
