Computational complexity of problems for deterministic presentations of sofic shifts

DOI10.1016/j.tcs.2022.09.017OpenAlexW4226329059MaRDI QIDQ2087461

Justin Cai, Rafael Frongillo

Publication date: 21 October 2022

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2112.03484

zbMATH Keywords

computational complexityautomata theorysymbolic dynamicssofic shifts

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Exact synchronization for finite-state sources
• Minimizing finite automata is computationally hard
• Finite procedures for sofic systems
• Sofic shifts with synchronizing presentations
• Cocyclic subshifts
• Computational complexity of \(k\)-block conjugacy
• On Two Algorithmic Problems about Synchronizing Automata
• Transfer operator, topological entropy and maximal measure for cocyclic subshifts
• Reset Sequences for Monotonic Automata
• Synchronizing Automata and the Černý Conjecture
• Isomorphism Testing for Graphs, Semigroups, and Finite Automata are Polynomially Equivalent Problems
• An Introduction to Symbolic Dynamics and Coding
• Sofic Shifts via Conley Index Theory: Computing Lower Bounds on Recurrent Dynamics for Maps
• Computational Complexity

This page was built for publication: Computational complexity of problems for deterministic presentations of sofic shifts