Complexity of Conjugacy, Factoring and Embedding for Countable Sofic Shifts of Rank 2 - UTU Tutkimustietojärjestelmä

A3 Vertaisarvioitu kirjan tai muun kokoomateoksen osa

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

Tekijät: Salo V, Torma I

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

Konferenssin vakiintunut nimi: AUTOMATA

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

Julkaisuvuosi: 2015

Journal: Lecture Notes in Computer Science

Kokoomateoksen nimi: Cellular automata and discrete complex systems

Tietokannassa oleva lehden nimi: CELLULAR AUTOMATA AND DISCRETE COMPLEX SYSTEMS (AUTOMATA 2014)

Lehden akronyymi: LECT NOTES COMPUT SC

Sarjan nimi: Lecture notes in computer science

Vuosikerta: 8996

Aloitussivu: 121

Lopetussivu: 134

Sivujen määrä: 14

ISBN: 978-3-319-18812-6

ISSN: 0302-9743

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

Tiivistelmä

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.