Monadic Second-Order Logic and Transitive Closure Logics over Trees

DOI10.1016/J.ENTCS.2006.05.044MaRDI QIDQ4917997zbMATH OpenOpenAlexFDO

Authors 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

derivation treedescriptive complexitymodel-theoretic syntaxmonadic second-order logicnatural languagetransitive closure logic

Mathematics Subject Classification ID

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

Recommendations

• Monadic second-order logic on tree-like structures
• Monadic second order logic on tree-like structures
• scientific article; zbMATH DE number 1086493
• Monadic second-order logic, graph coverings and unfoldings of transition systems
• Complete axiomatizations of fragments of monadic second-order logic on finite trees
• Existential monadic second order logic on random rooted trees
• Expressing cardinality quantifiers in monadic second-order logic over trees
• scientific article; zbMATH DE number 2079025
• Second-order propositional modal logic and monadic alternation hierarchies

Cites work

• A descriptive characterisation of indexed grammars
• An operational and denotational approach to non-context-freeness
• Characterizing derivation trees of context-free grammars through a generalization of finite automata theory
• scientific article; zbMATH DE number 1722707 (Why is no real title available?)
• scientific article; zbMATH DE number 408785 (Why is no real title available?)
• scientific article; zbMATH DE number 1254648 (Why is no real title available?)
• scientific article; zbMATH DE number 1142315 (Why is no real title available?)
• scientific article; zbMATH DE number 2079028 (Why is no real title available?)
• scientific article; zbMATH DE number 1447282 (Why is no real title available?)
• Monadic generalized spectra
• Reachability and the power of local ordering
• Syntactic structures as multi-dimensional trees
• Undecidability results on two-variable logics

Cited in

(14)

• Inessential features, ineliminable features, and modal logics for model theoretic syntax
• Monadic second-order logic, graph coverings and unfoldings of transition systems
• Monadic second-order logic on tree-like structures
• Existential monadic second order logic on random rooted trees
• Querying linguistic treebanks with monadic second-order logic in linear time
• Querying linguistic trees
• Branch-width, parse trees, and monadic second-order logic for matroids.
• Transitive closure logic, nested tree walking automata, and XPath
• Complete Axiomatizations of MSO, FO(TC 1 ) and FO(LFP 1 ) on Finite Trees
• scientific article; zbMATH DE number 1519892 (Why is no real title available?)
• A model theoretic description of tree adjoining grammars
• scientific article; zbMATH DE number 1447282 (Why is no real title available?)
• Expressivity within second-order transitive-closure logic
• Descriptions of cross-serial dependencies

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

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