Computational complexity of problems for deterministic presentations of sofic shifts

DOI10.1016/J.TCS.2022.09.017MaRDI QIDQ2087461zbMATH OpenOpenAlexFDO

Authors 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 complexitysymbolic dynamicsautomata theorysofic shifts

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Sofic shifts with synchronizing presentations
• Determining presentations of sofic shifts
• Minimal presentations for irreducible sofic shifts
• Complexity of conjugacy, factoring and embedding for countable sofic shifts of rank 2
• Sofic tree-shifts

Cites work

• scientific article; zbMATH DE number 58314 (Why is no real title available?)
• scientific article; zbMATH DE number 3460178 (Why is no real title available?)
• scientific article; zbMATH DE number 1747444 (Why is no real title available?)
• An introduction to symbolic dynamics and coding
• Cocyclic subshifts
• Computational Complexity
• Computational complexity of \(k\)-block conjugacy
• Exact synchronization for finite-state sources
• Finite procedures for sofic systems
• Isomorphism Testing for Graphs, Semigroups, and Finite Automata are Polynomially Equivalent Problems
• Minimizing finite automata is computationally hard
• On two algorithmic problems about synchronizing automata (short paper)
• Reset Sequences for Monotonic Automata
• Sofic shifts via Conley index theory: computing lower bounds on recurrent dynamics for maps
• Sofic shifts with synchronizing presentations
• Synchronizing Automata and the Černý Conjecture
• Transfer operator, topological entropy and maximal measure for cocyclic subshifts

Cited in

(2)

• Resource-Bounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts
• Computational complexity of problems for deterministic presentations of sofic shifts

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2087461)