An operational and denotational approach to non-context-freeness

DOI10.1016/S0304-3975(01)00348-6zbMATH Open1025.68099MaRDI QIDQ1870568FDOQ1870568

Authors: Hans-Peter Kolb, Jens Michaelis, Uwe Mönnich, Frank Morawietz 

Publication date: 14 May 2003

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

Recommendations

• Descriptions of cross-serial dependencies
• A model theoretic description of tree adjoining grammars
• Multiple context-free tree grammars: lexicalization and characterization
• Closure properties of linear context-free tree languages with an application to optimality theory
• Non-self-embedding linear context-free tree grammars generate regular tree languages

zbMATH Keywords

tree grammarsMSO logicnon-context-free phenomena

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42) Natural language processing (68T50)

Cites Work

• IO and OI. II
• Title not available (Why is that?)
• Title not available (Why is that?)
• Languages that Capture Complexity Classes
• The equivalence of four extensions of context-free grammars
• Weak Second‐Order Arithmetic and Finite Automata
• Title not available (Why is that?)
• Decision Problems of Finite Automata Design and Related Arithmetics
• Generalized finite automata theory with an application to a decision problem of second-order logic
• On multiple context-free grammars
• Derivational minimalism
• Title not available (Why is that?)
• Title not available (Why is that?)
• Tree acceptors and some of their applications
• Algebraic automata and context-free sets
• IO and OI. I
• On the generative power of transformational grammars
• Title not available (Why is that?)
• Macro tree transducers
• Macro tree transducers, attribute grammars, and MSO definable tree translations.
• A generalized approach to formal languages
• The monadic second-order logic of graphs. VII: Graphs as relational structures
• Regular description of context-free graph languages
• Title not available (Why is that?)
• Title not available (Why is that?)
• Descriptions of cross-serial dependencies

Cited In (5)

• Monadic Second-Order Logic and Transitive Closure Logics over Trees
• A note on the strong and weak generative powers of formal systems
• Anti-context-free languages
• Closure properties of linear context-free tree languages with an application to optimality theory
• Descriptions of cross-serial dependencies

This page was built for publication: An operational and denotational approach to non-context-freeness

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