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

DOI10.1016/J.TCS.2005.11.024MaRDI QIDQ2368942zbMATH OpenOpenAlexFDO

Authors Stephan Kepser, Uwe Mönnich

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)

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.
• scientific article; zbMATH DE number 4057034
• Composition closure of linear extended top-down tree transducers

Cites work

• scientific article; zbMATH DE number 3615891 (Why is no real title available?)
• scientific article; zbMATH DE number 1142316 (Why is no real title available?)
• scientific article; zbMATH DE number 1447282 (Why is no real title available?)
• A generalized approach to formal languages
• A model theoretic description of tree adjoining grammars
• An operational and denotational approach to non-context-freeness
• Bottom-up and top-down tree transformations— a comparison
• Descriptions of cross-serial dependencies
• Generalized finite automata theory with an application to a decision problem of second-order logic
• IO and OI. I
• IO and OI. II
• Macro tree transducers
• Mappings and grammars on trees
• Some notes on the formal properties of bidirectional optimality theory
• Tree acceptors and some of their applications

Cited in

(12)

• Regular Approximation of Weighted Linear Context-Free Tree Languages
• Second-order abstract categorial grammars as hyperedge replacement grammars
• An operational and denotational approach to non-context-freeness
• Restarting Tree Automata and Linear Context-Free Tree Languages
• The equivalence of tree adjoining grammars and monadic linear context-free tree grammars
• Optimality theory as a family of cumulative logics
• Reference-set constraints as linear tree transductions via controlled optimality systems
• 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
• Finite turns and the regular closure of linear context-free languages

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)