Automatic Structures: Richness and Limitations

Turku, Finland July 13-July 17

DOI Bookmark:

http://doi.ieeecomputersociety.org/10.1109/LICS.2004.1319599

19th Annual IEEE Symposium on Logic i ...

	This Article
	PURCHASE ARTICLE: $19 PDF HTML IEEE Xplore Subscribers
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Bakhadyr Khoussainov Articles by Andre Nies Articles by Sasha Rubin Articles by Frank Stephan

	ASCII Text	x
	Bakhadyr Khoussainov, Andre Nies, Sasha Rubin, Frank Stephan, "Automatic Structures: Richness and Limitations," Logic in Computer Science, Symposium on, pp. 44-53, 19th Annual IEEE Symposium on Logic in Computer Science (LICS'04), 2004.

	BibTex	x
	@article{ 10.1109/LICS.2004.1319599, author = {Bakhadyr Khoussainov and Andre Nies and Sasha Rubin and Frank Stephan}, title = {Automatic Structures: Richness and Limitations}, journal ={Logic in Computer Science, Symposium on}, volume = {0}, year = {2004}, issn = {1043-6871}, pages = {44-53}, doi = {http://doi.ieeecomputersociety.org/10.1109/LICS.2004.1319599}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Logic in Computer Science, Symposium on TI - Automatic Structures: Richness and Limitations SN - 1043-6871 SP44 EP53 A1 - Bakhadyr Khoussainov, A1 - Andre Nies, A1 - Sasha Rubin, A1 - Frank Stephan, PY - 2004 KW - null VL - 0 JA - Logic in Computer Science, Symposium on ER -

Bakhadyr Khoussainov, University of Auckland, New Zealand

Andre Nies, University of Auckland, New Zealand

Sasha Rubin, University of Auckland, New Zealand

Frank Stephan, National ICT Australia

This paper studies the existence of automatic presentations for various algebraic structures. The automatic Boolean algebras are characterised, and it is proven that the free Abelian group of infinite rank and many Fra?ss? limits do not have automatic presentations. In particular, the countably infinite random graph and the universal partial order do not have automatic presentations. Furthermore, no infinite integral domain is automatic. The second topic of the paper is the isomorphism problem. We prove that the complexity of the isomorphism problem for the class of all automatic structures is \sum\nolimits_1^1-complete.

Citation:

Bakhadyr Khoussainov, Andre Nies, Sasha Rubin, Frank Stephan, "Automatic Structures: Richness and Limitations," lics, pp.44-53, 19th Annual IEEE Symposium on Logic in Computer Science (LICS'04), 2004

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.