Closure properties of linear context-free tree languages with an application to optimality theory

DOI10.1016/J.TCS.2005.11.024zbMATH Open1088.68081OpenAlexW1971051128MaRDI QIDQ2368942FDOQ2368942

Uwe Mönnich, Stephan Kepser

Publication date: 28 April 2006

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2005.11.024

zbMATH Keywords

Context-free tree grammarFinite-state techniquesOptimality theory

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Cites Work

• Bottom-up and top-down tree transformations— a comparison
• IO and OI. II
• 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
• Mappings and grammars on trees
• Tree acceptors and some of their applications
• IO and OI. I
• A Model-Theoretic Description of Tree Adjoining Grammars1 1The research presented in this paper was supported by the Deutsche Forschungsgemeinschaft within the Sonderforschungsbereich 441, TP A2. The authors wish to thank Jens Michaelis and Stephan Kepser for helpful comments.
• Title not available (Why is that?)
• Macro tree transducers
• A generalized approach to formal languages
• Some notes on the formal properties of bidirectional optimality theory
• An operational and denotational approach to non-context-freeness
• Descriptions of cross-serial dependencies

Cited In (12)

• Regular Approximation of Weighted Linear Context-Free Tree Languages
• Second-order abstract categorial grammars as hyperedge replacement grammars
• Restarting Tree Automata and Linear Context-Free Tree Languages
• An operational and denotational approach to non-context-freeness
• The equivalence of tree adjoining grammars and monadic linear context-free tree grammars
• Optimality theory as a family of cumulative logics
• The Boolean closure of linear context-free languages
• The generative power of delegation networks
• The Pumping Lemma for Well-Nested Multiple Context-Free Languages
• The congruence theory of closure properties of regular tree languages
• Linear context-free tree languages and inverse homomorphisms
• Finite turns and the regular closure of linear context-free languages

   Recommendations

• The congruence theory of closure properties of regular tree languages 👍 👎
• Closure of Tree Automata Languages under Innermost Rewriting 👍 👎
• Developments in Language Theory 👍 👎
• The Boolean closure of linear context-free languages 👍 👎
• On closure properties of \(\mathcal{L}\)-valued linear languages 👍 👎
• Characterization and closure properties of linear \(\omega\)-languages 👍 👎
• Closure properties of minimalist derivation tree languages 👍 👎
• On the closure properties of linear conjunctive languages. 👍 👎
• Title not available (Why is that?) 👍 👎
• Composition closure of linear extended top-down tree transducers 👍 👎

This page was built for publication: Closure properties of linear context-free tree languages with an application to optimality theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2368942)