Deprecated: Function split() is deprecated in /srv/www/htdocs-cs/cie06/db-code.php on line 73

Deprecated: Function split() is deprecated in /srv/www/htdocs-cs/cie06/db-code.php on line 80
CiE 2006 - Regular Talk: - Undecidability in the Homomorphic Quasiorder  of Finite Labeled Forests
Computability in Europe 2006
Logical Approaches to Computational Barriers

Print current page  Print this page

Regular Talk:
Undecidability in the Homomorphic Quasiorder  of Finite Labeled Forests

Speaker: Victor Selivanov
Author(s): Oleg Kudinov and Victor Selivanov
Slot: Tue, 14:50-15:10, Faraday B (col. 2)

Abstract

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


websites: Arnold Beckmann
Warning: date(): It is not safe to rely on the system's timezone settings. You are *required* to use the date.timezone setting or the date_default_timezone_set() function. In case you used any of those methods and you are still getting this warning, you most likely misspelled the timezone identifier. We selected the timezone 'UTC' for now, but please set date.timezone to select your timezone. in /srv/www/htdocs-cs/cie06/conf-code.php on line 135
2006-06-23 Valid HTML 4.01! Valid CSS! eXTReMe Tracker hit counters by www.free-counters.net