On the structure of the monadic logic of the binary tree

DOI10.1007/3-540-48340-3_28MaRDI QIDQ4941910zbMATH OpenFDO

Authors David Janin, Giacomo Lenzi

Publication date 5 September 2000

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-48340-3_28

zbMATH Keywords

binary treedescriptive complexityEhrenfeucht-Fraïssé gamemonadic formulasmonadic second-order logic

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Descriptive complexity and finite models (68Q19)

Recommendations

• Monadic second order definable relations on the binary tree
• scientific article; zbMATH DE number 2113976
• On monadic theories of monadic predicates
• MSO on the Infinite Binary Tree: Choice and Order
• scientific article; zbMATH DE number 4051592

Cited in

(18)

• Monadic second-order logic on tree-like structures
• Existential monadic second order logic on random rooted trees
• A characterization of Büchi tree automata
• The full binary tree cannot be interpreted in a chain
• Baire category quantifier in monadic second order logic
• On monadic theories of monadic predicates
• MSO on the Infinite Binary Tree: Choice and Order
• scientific article; zbMATH DE number 4008381 (Why is no real title available?)
• Monadic second order definable relations on the binary tree
• scientific article; zbMATH DE number 4051592 (Why is no real title available?)
• scientific article; zbMATH DE number 475417 (Why is no real title available?)
• scientific article; zbMATH DE number 2113976 (Why is no real title available?)
• GETGRATS: a summary of scientific results (with annotated bibliography)
• Monadic Second Order Logic And Its Fragments
• scientific article; zbMATH DE number 2206111 (Why is no real title available?)
• A Combinatorial Theorem for Trees
• Monodic Tree Kleene Algebra
• On n-equivalence of binary trees

This page was built for publication: On the structure of the monadic logic of the binary tree

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