An operational and denotational approach to non-context-freeness

DOI10.1016/S0304-3975(01)00348-6MaRDI QIDQ1870568zbMATH OpenFDO

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)

zbMATH Keywords

tree grammarsMSO logicnon-context-free phenomena

Mathematics Subject Classification ID

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

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

Cites work

• scientific article; zbMATH DE number 3854429 (Why is no real title available?)
• scientific article; zbMATH DE number 3615891 (Why is no real title available?)
• scientific article; zbMATH DE number 1086493 (Why is no real title available?)
• scientific article; zbMATH DE number 1104368 (Why is no real title available?)
• scientific article; zbMATH DE number 1142314 (Why is no real title available?)
• scientific article; zbMATH DE number 1142315 (Why is no real title available?)
• scientific article; zbMATH DE number 1504824 (Why is no real title available?)
• scientific article; zbMATH DE number 1447282 (Why is no real title available?)
• A generalized approach to formal languages
• Algebraic automata and context-free sets
• Decision Problems of Finite Automata Design and Related Arithmetics
• Derivational minimalism
• 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
• Languages that Capture Complexity Classes
• Macro tree transducers
• Macro tree transducers, attribute grammars, and MSO definable tree translations.
• On multiple context-free grammars
• On the generative power of transformational grammars
• Regular description of context-free graph languages
• The equivalence of four extensions of context-free grammars
• The monadic second-order logic of graphs. VII: Graphs as relational structures
• Tree acceptors and some of their applications
• Weak Second‐Order Arithmetic and Finite Automata

Cited in

(5)

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

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)