An operational and denotational approach to non-context-freeness

DOI10.1016/S0304-3975(01)00348-6zbMath1025.68099MaRDI QIDQ1870568

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

Publication date: 14 May 2003

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

zbMATH Keywords

MSO logictree grammarsnon-context-free phenomena

Mathematics Subject Classification ID

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

Related Items

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

Cites Work

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