Geodesic
Definability of closure operations in the $h$-quasiorder of labeled forests
Algebra i logika, Tome 49 (2010) no. 2, pp. 181-194.

Voir la notice de l'article provenant de la source Math-Net.Ru

We prove that natural closure operations on quotient structures of the $h$-quasiorder of finite and (at most) countable $k$-labeled forests ($k\ge3$) are definable provided that minimal nonsmallest elements are allowed as parameters. This strengthens our previous result which holds that each element of the $h$-quasiorder of finite $k$-labeled forests is definable in the first-order language, and each element of the $h$-quasiorder of (at most) countable $k$-labeled forests is definable in the language $L_{\omega_1\omega}$; in both cases $k\ge3$ and minimal nonsmallest elements are allowed as parameters. Similar results hold true for two other relevant structures: the $h$-quasiorder of finite (resp. countable) $k$-labeled trees and $k$-labeled trees with a fixed label on the root element.
Keywords: labeled forest, labeled tree, definability, closure operation.
Mots-clés : $h$-quasiorder 
@article{AL_2010_49_2_a2,
     author = {A. V. Zhukov and O. V. Kudinov and V. L. Selivanov},
     title = {Definability of closure operations in the $h$-quasiorder of labeled forests},
     journal = {Algebra i logika},
     pages = {181--194},
     publisher = {mathdoc},
     volume = {49},
     number = {2},
     year = {2010},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2010_49_2_a2/}
}
TY  - JOUR
AU  - A. V. Zhukov
AU  - O. V. Kudinov
AU  - V. L. Selivanov
TI  - Definability of closure operations in the $h$-quasiorder of labeled forests
JO  - Algebra i logika
PY  - 2010
SP  - 181
EP  - 194
VL  - 49
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2010_49_2_a2/
LA  - ru
ID  - AL_2010_49_2_a2
ER  - 
%0 Journal Article
%A A. V. Zhukov
%A O. V. Kudinov
%A V. L. Selivanov
%T Definability of closure operations in the $h$-quasiorder of labeled forests
%J Algebra i logika
%D 2010
%P 181-194
%V 49
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2010_49_2_a2/
%G ru
%F AL_2010_49_2_a2
A. V. Zhukov; O. V. Kudinov; V. L. Selivanov. Definability of closure operations in the $h$-quasiorder of labeled forests. Algebra i logika, Tome 49 (2010) no. 2, pp. 181-194. http://geodesic.mathdoc.fr/item/AL_2010_49_2_a2/

[1] P. Hertling, Topologische Komplexitätsgrade von Funktionen mit endlichem Bild, Informatik-Berichte 152, Fernuniversität Hagen, December 1993

[2] V. L. Selivanov, “Bulevy ierarkhii razbienii nad redutsiruemoi bazoi”, Algebra i logika, 43:1 (2004), 77–109 | MR | Zbl

[3] O. V. Kudinov, V. L. Selivanov, “Definability in the homomorphic quasiorder of finite labeled forests”, Computation and logic in the real world. Third conference on computability in Europe, CiE 2007 (Siena, Italy, June 18–23, 2007), Lect. Notes Comput. Sci., 4497, ed. S. B. Cooper et al., Springer-Verlag, Berlin, 2007, 436–445 | Zbl

[4] O. V. Kudinov, V. L. Selivanov, “Undecidability in the homomorphic quasiorder of finite labeled forests”, J. Log. Comput., 17:6 (2007), 1135–1151 | DOI | MR | Zbl

[5] V. L. Selivanov, “Faktor-algebra razmechennykh lesov po modulyu $h$-ekvivalentnosti”, Algebra i logika, 46:2 (2007), 217–243 | MR | Zbl

[6] D. Kuske, “Theories of orders on the set of words”, Theor. Inform. Appl., 40:1 (2006), 53–74 | DOI | MR | Zbl

[7] V. L. Selivanov, “Hierarchies of $\Delta^0_2$-measurable $k$-partitions”, Math. Log. Q., 53:4–5 (2007), 446–461 | DOI | MR | Zbl

[8] V. L. Selivanov, “O strukture stepenei obobschënnykh indeksnykh mnozhestv”, Algebra i logika, 21:4 (1982), 472–491 | MR

[9] O. V. Kudinov, V. L. Selivanov, A. V. Zhukov, “Definability in the $h$-quasiorder of labeled forests”, Ann. Pure Appl. Logic, 159:3 (2009), 318–332 | MR | Zbl