wMSO theories as grammar formalisms

DOI10.1016/S0304-3975(01)00349-8zbMATH Open1025.68045MaRDI QIDQ1870569FDOQ1870569

Authors: Yanyan Li 

Publication date: 14 May 2003

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

Recommendations

• scientific article; zbMATH DE number 1341537
• On Monadic Second-Order Theories of Multidominance Structures
• A model theoretic description of tree adjoining grammars
• scientific article; zbMATH DE number 17791
• The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability

zbMATH Keywords

grammarDescriptive complexityModel-theoretic syntaxTree-adjoiningwSnS

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Cites Work

• Title not available (Why is that?)
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Title not available (Why is that?)
• A geometric hierarchy beyond context-free languages
• Tree adjunct grammars
• Weak Second‐Order Arithmetic and Finite Automata
• Decision Problems of Finite Automata Design and Related Arithmetics
• Generalized finite automata theory with an application to a decision problem of second-order logic
• Characterizing derivation trees of context-free grammars through a generalization of finite automata theory
• Mappings and grammars on trees
• Tree acceptors and some of their applications
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (4)

• Title not available (Why is that?)
• The equivalence of tree adjoining grammars and monadic linear context-free tree grammars
• Syntactic structures as multi-dimensional trees
• Two Equivalent Regularizations for Tree Adjoining Grammars

Uses Software

• MONA
• Mosel

This page was built for publication: wMSO theories as grammar formalisms

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