|
This article is cited in 1 scientific paper (total in 1 paper)
Definability of closure operations in the $h$-quasiorder of labeled forests
A. V. Zhukova, O. V. Kudinovb, V. L. Selivanovc a Novosibirsk State Pedagogical University, Novosibirsk, Russia
b Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk, Russia
c A. P. Ershov Institute of Informatics Systems Sib. Br. RAS, Novosibirsk, Russia
Abstract:
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, $h$-quasiorder, definability, closure operation.
Received: 29.10.2008
Citation:
A. V. Zhukov, O. V. Kudinov, V. L. Selivanov, “Definability of closure operations in the $h$-quasiorder of labeled forests”, Algebra Logika, 49:2 (2010), 181–194; Algebra and Logic, 49:2 (2010), 120–129
Linking options:
https://www.mathnet.ru/eng/al435 https://www.mathnet.ru/eng/al/v49/i2/p181
|
Statistics & downloads: |
Abstract page: | 352 | Full-text PDF : | 96 | References: | 58 | First page: | 2 |
|