Optimal state amalgamation is NP-hard
From MaRDI portal
Publication:4968744
DOI10.1017/ETDS.2017.105zbMath1420.37006OpenAlexW2767222152MaRDI QIDQ4968744
Publication date: 9 July 2019
Published in: Ergodic Theory and Dynamical Systems (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/ed971a0ce3a30b5f2d3c8648bfef70870a32b43f
Related Items (2)
Computational complexity of \(k\)-block conjugacy ⋮ Sofic Shifts via Conley Index Theory: Computing Lower Bounds on Recurrent Dynamics for Maps
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Hardness of conjugacy, embedding and factorization of multidimensional subshifts
- Markov shifts in the Hénon family
- Sofic shifts with synchronizing presentations
- Symbolic dynamics. One-sided, two-sided and countable state Markov shifts
- Tree-shifts of finite type
- Classification of subshifts of finite type
- Comparing dynamical systems by a graph matching method
- Markov partitions and \(C\)-diffeomorphisms
- Construction of Markov partitions
- Algorithms for Rigorous Entropy Bounds and Symbolic Dynamics
- A Note on Minimal Covers for Sofic Systems
- The decomposition theorem for two-dimensional shifts of finite type
- The Williams conjecture is false for irreducible subshifts
- Symbolic dynamics and Markov partitions
- An algorithm to prune the area-preserving Hénon map
- Minimal presentations for irreducible sofic shifts
- An Introduction to Symbolic Dynamics and Coding
- How does a choice of Markov partition affect the resultant symbolic dynamics?
- ENTROPY, A COMPLETE METRIC INVARIANT FOR AUTOMORPHISMS OF THE TORUS
- The undecidability of the domino problem
- Markov Partitions for Axiom A Diffeomorphisms
- Computational Complexity
- Determining presentations of sofic shifts
- Multiplicities of covers for sofic shifts
This page was built for publication: Optimal state amalgamation is NP-hard
