Some results on automatic structures
Proceedings - Symposium on Logic in Computer Science - Trang 235-242
Tóm tắt
We study the class of countable structures which can be presented by synchronous finite automata. We reduce the problem of existence of an automatic presentation of a structure to that for a graph. We exhibit a series of properties of automatic equivalence structures, linearly ordered sets and permutation structures. These serve as a first step in producing practical descriptions of some automatic structures or illuminating the complexity of doing so for others.
Từ khóa
#Automata #Computer science #Mathematics #Terminology #Automatic logic units #PolynomialsTài liệu tham khảo
rubin, 1999, Finite automata and well ordered sets, New Zealand J Comput, 7, 39
10.1007/3-540-55808-X_48
khoussainov, 1995, Automatic presentations of structures, Lecture Notes in Computer Science, 960, 367, 10.1007/3-540-60178-3_93
khoussainov, 2001, Graphs with automatic presentations over a unary alphabet, Journal of Automata Languages and Combinatorics, 6
blumensath, 0
10.1147/rd.176.0525
10.1109/LICS.2001.932518
10.1017/CBO9780511551574
10.1016/0021-8693(69)90107-0
delhomme, 0, Automatic Linear Orderings
10.1109/LICS.2000.855755
blumensath, 1999, Automatic Structures
10.1016/0020-0190(90)90051-X
epstein, 1992, Word Processing in Groups, 10.1201/9781439865699