Monadic Second-Order Logic and Transitive Closure Logics over Trees

DOI10.1016/j.entcs.2006.05.044zbMath1262.03050OpenAlexW2124638910MaRDI QIDQ4917997

Hans-Jörg Tiede, Stephan Kepser

Publication date: 3 May 2013

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

Full work available at URL: https://doi.org/10.1016/j.entcs.2006.05.044

zbMATH Keywords

monadic second-order logicnatural languagedescriptive complexitymodel-theoretic syntaxderivation treetransitive closure logic

Mathematics Subject Classification ID

Logic of natural languages (03B65) Grammars and rewriting systems (68Q42) Descriptive complexity and finite models (68Q19)

Related Items (2)

Querying linguistic trees ⋮ Complete Axiomatizations of MSO, FO(TC 1 ) and FO(LFP 1 ) on Finite Trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A descriptive characterisation of indexed grammars
• Undecidability results on two-variable logics
• Reachability and the power of local ordering
• Syntactic structures as multi-dimensional trees
• An operational and denotational approach to non-context-freeness
• Characterizing derivation trees of context-free grammars through a generalization of finite automata theory
• Monadic generalized spectra

This page was built for publication: Monadic Second-Order Logic and Transitive Closure Logics over Trees