wMSO theories as grammar formalisms

DOI10.1016/S0304-3975(01)00349-8zbMath1025.68045MaRDI QIDQ1870569

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)

Related Items (2)

The equivalence of tree adjoining grammars and monadic linear context-free tree grammars ⋮ Two Equivalent Regularizations for Tree Adjoining Grammars

Uses Software

• MONA
• Mosel

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A geometric hierarchy beyond context-free languages
• Tree adjunct grammars
• Characterizing derivation trees of context-free grammars through a generalization of finite automata theory
• Tree acceptors and some of their applications
• 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
• Mappings and grammars on trees
• Decidability of Second-Order Theories and Automata on Infinite Trees

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