On n-equivalence of binary trees (Q579237)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Publication:579237 |
scientific article; zbMATH DE number 4014683
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | On n-equivalence of binary trees |
scientific article; zbMATH DE number 4014683 |
Statements
On n-equivalence of binary trees (English)
0 references
1987
0 references
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.
0 references
quantifier depth n-equivalence
0 references
binary trees
0 references
first-order sentences of quantifier depth n
0 references
Ehrenfeucht game
0 references
0.7855023741722107
0 references
0.7678050398826599
0 references
