On n-equivalence of binary trees
type: Item
instance of: scholarly article
title: On n-equivalence of binary trees
zbMATH Open document ID: 0625.03013
author: Kees Doets
published in: Notre Dame Journal of Formal Logic
publication date: 1987-01-01T00:00:00Z
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.
Mathematics Subject Classification ID: 03C10
Mathematics Subject Classification ID: 03C13
Mathematics Subject Classification ID: 06A12
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 4014683
zbMATH Keywords: quantifier depth n-equivalence
zbMATH Keywords: binary trees
zbMATH Keywords: first-order sentences of quantifier depth n
zbMATH Keywords: Ehrenfeucht game
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1305/ndjfl/1093636941
OpenAlex ID: W2066680155
DOI: 10.1305/NDJFL/1093636941
description: scientific article; zbMATH DE number 4014683