Multiple context-free tree grammars: lexicalization and characterization
From MaRDI portal
Abstract: Multiple (simple) context-free tree grammars are investigated, where "simple" means "linear and nondeleting". Every multiple context-free tree grammar that is finitely ambiguous can be lexicalized; i.e., it can be transformed into an equivalent one (generating the same tree language) in which each rule of the grammar contains a lexical symbol. Due to this transformation, the rank of the nonterminals increases at most by 1, and the multiplicity (or fan-out) of the grammar increases at most by the maximal rank of the lexical symbols; in particular, the multiplicity does not increase when all lexical symbols have rank 0. Multiple context-free tree grammars have the same tree generating power as multi-component tree adjoining grammars (provided the latter can use a root-marker). Moreover, every multi-component tree adjoining grammar that is finitely ambiguous can be lexicalized. Multiple context-free tree grammars have the same string generating power as multiple context-free (string) grammars and polynomial time parsing algorithms. A tree language can be generated by a multiple context-free tree grammar if and only if it is the image of a regular tree language under a deterministic finite-copying macro tree transducer. Multiple context-free tree grammars can be used as a synchronous translation device.
Recommendations
Cites work
- scientific article; zbMATH DE number 3854429 (Why is no real title available?)
- scientific article; zbMATH DE number 3566209 (Why is no real title available?)
- scientific article; zbMATH DE number 1200800 (Why is no real title available?)
- scientific article; zbMATH DE number 475427 (Why is no real title available?)
- scientific article; zbMATH DE number 522865 (Why is no real title available?)
- scientific article; zbMATH DE number 1504824 (Why is no real title available?)
- scientific article; zbMATH DE number 1517989 (Why is no real title available?)
- A bottom-up characterization of deterministic top-down tree transducers with regular look-ahead
- A characterization of parenthesis languages
- An Automata Theoretic Approach to Rational Tree Relations
- An axiomatic definition of context-free rewriting and its application to NLC graph grammars
- An extension of ALGOL-like languages
- Attribute grammars and recursive program schemes. I. II
- Bottom-up and top-down tree transformations— a comparison
- Composition of top-down and bottom-up tree transductions
- Compositions of extended top-down tree transducers
- Context-free grammars: covers, normal forms, and parsing
- Context-free graph grammars and concatenation of graphs
- Context-free hypergraph grammars have the same term-generating power as attribute grammars
- Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton
- Dependency structures and lexicalized grammars. An algebraic approach
- Extended multi bottom-up tree transducers
- Graph expressions and graph rewritings
- Graph structure and monadic second-order logic. A language-theoretic approach
- Handbook of Graph Grammars and Computing by Graph Transformation
- IO and OI. I
- IO and OI. II
- Independent parallelism in finite copying parallel rewriting systems
- Logical Aspects of Computational Linguistics
- MINIMAL RECOGNIZERS AND SYNTACTIC MONOIDS OF DR TREE LANGUAGES
- MSO definable string transductions and two-way finite-state transducers
- Macro Tree Translations of Linear Size Increase are MSO Definable
- Macro tree transducers
- Macro tree transducers, attribute grammars, and MSO definable tree translations.
- Mappings and grammars on trees
- Monadic second-order definable text languages
- Multidimensional trees and a Chomsky-Schützenberger-Weir representation theorem for simple context-free tree grammars
- Multiple context-free tree grammars and multi-component tree adjoining grammars
- On IO-copying and mildly-context sensitive formalisms
- On extensions of ALGOL-like languages
- On multiple context-free grammars
- On the Covering and Reduction Problems for Context-Free Grammars
- On the relation between ambiguity and nondeterminism in finite automata
- Output string languages of compositions of deterministic macro tree transducers
- Parameter reduction and automata evaluation for grammar-compressed trees
- Parsing beyond context-free grammars
- Polynomial-Time Identification of an Extension of Very Simple Grammars from Positive Data
- Rational tree relations
- Restarting Tree Automata and Linear Context-Free Tree Languages
- Second-order abstract categorial grammars as hyperedge replacement grammars
- Single-Path Restarting Tree Automata
- Spinal-formed context-free tree grammars
- Synchronous forest substitution grammars
- The Pumping Lemma for Well-Nested Multiple Context-Free Languages
- The copying power of one-state tree transducers
- The copying power of well-nested multiple context-free grammars
- The equivalence of tree adjoining grammars and monadic linear context-free tree grammars
- The formal power of one-visit attribute grammars
- The string generating power of context-free hypergraph grammars
- Three hierarchies of transducers
- Top-down tree transducers with regular look-ahead
- Towards more precise rewriting approximations
- Transductions des langages de Chomsky
- Tree adjunct grammars
- Tree transducers, L systems, and two-way machines
- Uniform \textit{vs.} nonuniform membership for mildly context-sensitive languages: a brief survey
Cited in
(14)- An Algebraic Approach to Multiple Context-Free Grammars
- On the relation between multi-depth grammars and tree adjoining grammars
- Tree-local multicomponent tree-adjoining grammars with shared nodes
- Synchronous forest substitution grammars
- An operational and denotational approach to non-context-freeness
- Multi-Component Tree Insertion Grammars
- Multiple context-free tree grammars and multi-component tree adjoining grammars
- scientific article; zbMATH DE number 1523042 (Why is no real title available?)
- Combinatory categorial grammars as generators of weighted forests
- A context-free language for binary multinomial processing tree models
- Tree parsing for tree-adjoining machine translation
- Pushdown machines for weighted context-free tree translation
- scientific article; zbMATH DE number 475427 (Why is no real title available?)
- Bag context tree grammars
This page was built for publication: Multiple context-free tree grammars: lexicalization and characterization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1749480)
