Back to Search Start Over

Definability in the Homomorphic Quasiorder of Finite Labeled Forests.

Authors :
Hutchison, David
Kanade, Takeo
Kittler, Josef
Kleinberg, Jon M.
Mattern, Friedemann
Mitchell, John C.
Naor, Moni
Nierstrasz, Oscar
Rangan, C. Pandu
Steffen, Bernhard
Sudan, Madhu
Terzopoulos, Demetri
Tygar, Doug
Vardi, Moshe Y.
Weikum, Gerhard
Cooper, S. Barry
Löwe, Benedikt
Sorbi, Andrea
Kudinov, Oleg V.
Selivanov, Victor L.
Source :
Computation & Logic in the Real World; 2007, p436-445, 10p
Publication Year :
2007

Abstract

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. [ABSTRACT FROM AUTHOR]

Details

Language :
English
ISBNs :
9783540730002
Database :
Supplemental Index
Journal :
Computation & Logic in the Real World
Publication Type :
Book
Accession number :
33191471
Full Text :
https://doi.org/10.1007/978-3-540-73001-9_45