On n-equivalence of binary trees

DOI10.1305/NDJFL/1093636941MaRDI QIDQ579237zbMATH OpenOpenAlexFDO

Authors Kees Doets

Publication date 1987

Published in Notre Dame Journal of Formal Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1305/ndjfl/1093636941

zbMATH Keywords

binary treesEhrenfeucht gamefirst-order sentences of quantifier depth nquantifier depth n-equivalence

Mathematics Subject Classification ID

Quantifier elimination, model completeness, and related topics (03C10) Model theory of finite structures (03C13) Trees (05C05) Semilattices (06A12)

Review text

The paper contains a simple characterization of the binary trees which satisfy the same first-order sentences of quantifier depth n as the binary tree with one root whose branches all have length m (for all n and m). It follows immediately that, e.g., ``finiteness is not a first- order property of binary trees. The proof employs the Ehrenfeucht game.

Recommendations

• Games on Trees and Syntactical Complexity of Formulas
• scientific article; zbMATH DE number 4051033
• scientific article; zbMATH DE number 4008381
• First-order logic on finite trees
• scientific article; zbMATH DE number 1418347

Cited in

(4)

• Homogeneous trees are bilipschitz equivalent
• scientific article; zbMATH DE number 6376879 (Why is no real title available?)
• scientific article; zbMATH DE number 4008381 (Why is no real title available?)
• scientific article; zbMATH DE number 1867119 (Why is no real title available?)

This page was built for publication: On n-equivalence of binary trees

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