Complexity of Conjugacy, Factoring and Embedding for Countable Sofic Shifts of Rank 2 - UTU Research Portal

A3 Refereed book chapter or chapter in a compilation book

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

Authors: Salo V, Torma I

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

Conference name: AUTOMATA

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

Publication year: 2015

Journal: Lecture Notes in Computer Science

Book title : Cellular automata and discrete complex systems

Journal name in source: CELLULAR AUTOMATA AND DISCRETE COMPLEX SYSTEMS (AUTOMATA 2014)

Journal acronym: LECT NOTES COMPUT SC

Series title: Lecture notes in computer science

Volume: 8996

First page : 121

Last page: 134

Number of pages: 14

ISBN: 978-3-319-18812-6

ISSN: 0302-9743

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

Abstract

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.