Standard

Undecidability in the homomorphic quasiorder of finite labeled forests. / Kudinov, Oleg V.; Selivanov, Victor L.

Logical Approaches to Computational Barriers (CiE 2006). 2006. p. 289-296 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3988).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

Harvard

Kudinov, OV & Selivanov, VL 2006, Undecidability in the homomorphic quasiorder of finite labeled forests. in Logical Approaches to Computational Barriers (CiE 2006). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3988, pp. 289-296, computability in europe-2006, 30/06/06. https://doi.org/10.1007/11780342_31

APA

Kudinov, O. V., & Selivanov, V. L. (2006). Undecidability in the homomorphic quasiorder of finite labeled forests. In Logical Approaches to Computational Barriers (CiE 2006) (pp. 289-296). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3988). https://doi.org/10.1007/11780342_31

Vancouver

Kudinov OV, Selivanov VL. Undecidability in the homomorphic quasiorder of finite labeled forests. In Logical Approaches to Computational Barriers (CiE 2006). 2006. p. 289-296. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/11780342_31

Author

Kudinov, Oleg V. ; Selivanov, Victor L. / Undecidability in the homomorphic quasiorder of finite labeled forests. Logical Approaches to Computational Barriers (CiE 2006). 2006. pp. 289-296 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{5ce37d9555024406bc1130ada24e1546,
title = "Undecidability in the homomorphic quasiorder of finite labeled forests",
abstract = "We prove that the homomorphic quasiorder of finite k-labeled forests has undecidable elementary theory for k ≥ 3, in contrast to the known decidability result for k = 2. We establish also undecidablity (again for every k ≥ 3) of elementary theories of 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. {\textcopyright} Springer-Verlag Berlin Heidelberg 2006.",
keywords = "Elementary theory, Forest, Homomorphic quasiorder, Labeled tree, Tree, Undecidability",
author = "Kudinov, {Oleg V.} and Selivanov, {Victor L.}",
year = "2006",
month = jan,
day = "1",
doi = "10.1007/11780342_31",
language = "English",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Nature",
pages = "289--296",
booktitle = "Logical Approaches to Computational Barriers (CiE 2006)",
note = "computability in europe-2006 ; Conference date: 30-06-2006",

}

RIS

TY - GEN

T1 - Undecidability in the homomorphic quasiorder of finite labeled forests

AU - Kudinov, Oleg V.

AU - Selivanov, Victor L.

PY - 2006/1/1

Y1 - 2006/1/1

N2 - We prove that the homomorphic quasiorder of finite k-labeled forests has undecidable elementary theory for k ≥ 3, in contrast to the known decidability result for k = 2. We establish also undecidablity (again for every k ≥ 3) of elementary theories of 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 2006.

AB - We prove that the homomorphic quasiorder of finite k-labeled forests has undecidable elementary theory for k ≥ 3, in contrast to the known decidability result for k = 2. We establish also undecidablity (again for every k ≥ 3) of elementary theories of 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 2006.

KW - Elementary theory

KW - Forest

KW - Homomorphic quasiorder

KW - Labeled tree

KW - Tree

KW - Undecidability

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

U2 - 10.1007/11780342_31

DO - 10.1007/11780342_31

M3 - Conference contribution

AN - SCOPUS:33746089931

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

SP - 289

EP - 296

BT - Logical Approaches to Computational Barriers (CiE 2006)

T2 - computability in europe-2006

Y2 - 30 June 2006

ER -

ID: 127139962