Seventeenth Annual IEEE Symposium on

Logic in Computer Science (LICS 2002)

Paper: Some Results on Automatic Structures (at LICS 2002)

Authors: Hajime Ishihara Bakhadyr Khoussainov Sasha Rubin


In this paper we study structures defined by finite automata, called automatic structures. We provide a method that reduces the study of automatic structures to the study of automatic graphs. We investigate isomorphism invariants of automatic structures with an emphasis to equivalence relation structures, linearly ordered sets, and permutation structures.


    author = 	 {Hajime Ishihara and Bakhadyr Khoussainov and Sasha Rubin},
    title = 	 {Some Results on Automatic Structures},
    booktitle =  {Proceedings of the Seventeenth Annual IEEE Symp. on Logic in Computer Science, {LICS} 2002},
    year =	 2002,
    editor =	 {Gordon Plotkin},
    month =	 {July}, 
    location =   {Copenhagen, Denmark}, 
    publisher =	 {IEEE Computer Society Press}