TY - GEN

T1 - Definability in the homomorphic quasiorder of finite labeled forests

AU - Kudinov, Oleg V.

AU - Selivanov, Victor L.

PY - 2007/12/1

Y1 - 2007/12/1

N2 - We prove that for any k ≥ 3 each element of the homomorphic quasiorder of finite k-labeled forests is definable, provided that the minimal non-smallest elements are allowed as parameters. As corollaries, we show that the structure is atomic and characterize the automorphism group of the structure. Similar results hold true for two other relevant structures: the homomorphic quasiorder of finite k-labeled trees, and of finite k-labeled trees with a fixed label of the root element. © Springer-Verlag Berlin Heidelberg 2007.

AB - We prove that for any k ≥ 3 each element of the homomorphic quasiorder of finite k-labeled forests is definable, provided that the minimal non-smallest elements are allowed as parameters. As corollaries, we show that the structure is atomic and characterize the automorphism group of the structure. Similar results hold true for two other relevant structures: the homomorphic quasiorder of finite k-labeled trees, and of finite k-labeled trees with a fixed label of the root element. © Springer-Verlag Berlin Heidelberg 2007.

KW - Atomic structure

KW - Automorphism

KW - Definability

KW - Forest

KW - Homomorphic quasiorder

KW - Labeled tree

UR - http://www.scopus.com/inward/record.url?scp=38149138689&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-73001-9_45

DO - 10.1007/978-3-540-73001-9_45

M3 - Conference contribution

AN - SCOPUS:38149138689

SN - 978-354073000-2

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 436

EP - 445

BT - 3rd Conference on Computability in Europe, CiE 2007

T2 - computability in europe-2007

Y2 - 18 June 2007

ER -