Computational complexity of problems for deterministic presentations of sofic shifts

DOI10.1016/J.TCS.2022.09.017OpenAlexW4226329059MaRDI QIDQ2087461FDOQ2087461

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

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

zbMATH Keywords

computational complexitysymbolic dynamicsautomata theorysofic shifts

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

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

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)