DEPARTMENT RESEARCH ACADEMICS PEOPLE NEWS
Rice Computer Science		SEARCH:
Rice University Department of Computer Science presents Bakhadyr Khoussainov University of Auckland, New Zealand Research Seminar: Automatic Structures Abstract A structure is automatic if its domain and atomic relations can be recognized by finite automata. We say that a structure has finite automata implementation (or presentation) if it is isomorphic to an automatic structure. In this talk we survey several directions and results in the study of automatic structures. We describe several methods necessary for a structure to have finite automata implementations. Secondly, we discuss the question on the complexity of the isomorphism problem for automatic structures. Finally, we investigate the definability issues of regular relations in automatic structures. In particular we provide an automatic implementation of the successor structure (N,S) under which the set of even numbers is not regular. Wednesday, Oct. 22 at 4:00 p.m. in DH 3076 Copyright 2000 Rice University site problems: www@cs.rice.edu --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- ---