Computational complexity of problems for deterministic presentations of sofic shifts

Justin Cai, Rafael Frongillo

Sofic shifts are symbolic dynamical systems defined by the set of bi-infinite sequences on an edge-labeled directed graph, called a presentation. We study the computational complex…