Deciding the isomorphism problem in classes of unary automatic structures |
| |
| Authors: | Jiamou Liu Mia Minnes |
| |
| Affiliation: | a Department of Computer Science, University of Auckland, Auckland, New Zealandb Department of Mathematics, MIT, Cambridge, MA, USA |
| |
| Abstract: | We solve the isomorphism problem for certain classes of unary automatic structures: unary automatic equivalence relations, unary automatic linear orders, and unary automatic trees. That is, we provide algorithms which decide whether two given elements of these classes are isomorphic. In doing so, we define new finite representations for these structures which give normal forms.1 |
| |
| Keywords: | Unary automatic structures The isomorphism problem Graphs |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
