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)

zbMATH Keywords

grammarDescriptive complexityModel-theoretic syntaxTree-adjoiningwSnS

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

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

Cites work

• scientific article; zbMATH DE number 3510287 (Why is no real title available?)
• scientific article; zbMATH DE number 3615891 (Why is no real title available?)
• scientific article; zbMATH DE number 1341537 (Why is no real title available?)
• scientific article; zbMATH DE number 475427 (Why is no real title available?)
• scientific article; zbMATH DE number 1447282 (Why is no real title available?)
• scientific article; zbMATH DE number 3238653 (Why is no real title available?)
• A geometric hierarchy beyond context-free languages
• Characterizing derivation trees of context-free grammars through a generalization of finite automata theory
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Decision Problems of Finite Automata Design and Related Arithmetics
• Generalized finite automata theory with an application to a decision problem of second-order logic
• Mappings and grammars on trees
• Tree acceptors and some of their applications
• Tree adjunct grammars
• Weak Second‐Order Arithmetic and Finite Automata

Cited in

(4)

• The equivalence of tree adjoining grammars and monadic linear context-free tree grammars
• Two Equivalent Regularizations for Tree Adjoining Grammars
• scientific article; zbMATH DE number 1447282 (Why is no real title available?)
• Syntactic structures as multi-dimensional trees

Describes a project that uses

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)