Complexity of Conjugacy, Factoring and Embedding for Countable Sofic Shifts of Rank 2



: Salo V, Torma I

: Teijiro Isokawa,Katsunobu Imai, Nobuyuki Matsui,Ferdinand Peper,Hiroshi Umeo

: AUTOMATA

Publisher: SPRINGER-VERLAG NEW YORK, MS INGRID CUNNINGHAM, 175 FIFTH AVE, NEW YORK, NY 10010 USA

: 2015

: Lecture Notes in Computer Science

: Cellular automata and discrete complex systems

: CELLULAR AUTOMATA AND DISCRETE COMPLEX SYSTEMS (AUTOMATA 2014)

: LECT NOTES COMPUT SC

: Lecture notes in computer science

: 8996

: 121

: 134

: 14

: 978-3-319-18812-6

: 0302-9743

DOI: https://doi.org/10.1007/978-3-319-18812-6_10


In this article, we study countable sofic shifts of Cantor-Bendixson rank at most 2. We prove that their conjugacy problem is complete for GI, the complexity class of graph isomorphism, and that the existence problems of block maps, factor maps and embeddings are NP-complete.




Last updated on 2024-26-11 at 21:28