Optimal state amalgamation is NP-hard

DOI10.1017/ETDS.2017.105MaRDI QIDQ4968744zbMATH OpenOpenAlexFDO

Authors Rafael Frongillo

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

zbMATH Keywords

conjugacystate amalgamationsubshifts of finite type

Mathematics Subject Classification ID

Symbolic dynamics (37B10)

Recommendations

• Computational complexity of k-block conjugacy
• Hardness of conjugacy, embedding and factorization of multidimensional subshifts
• THE CONJUGACY PROBLEM IN AMALGAMATED PRODUCTS I: REGULAR ELEMENTS AND BLACK HOLES
• On the conjugacy problem for finite-state automorphisms of regular rooted trees. With an appendix by Raphaël M. Jungers
• Hardness of conjugacy, embedding and factorization of multidimensional subshifts of finite type

Cites work

• A Note on Minimal Covers for Sofic Systems
• Algorithms for Rigorous Entropy Bounds and Symbolic Dynamics
• An algorithm to prune the area-preserving Hénon map
• An Introduction to Symbolic Dynamics and Coding
• Classification of subshifts of finite type
• Comparing dynamical systems by a graph matching method
• Computational Complexity
• Construction of Markov partitions
• Determining presentations of sofic shifts
• ENTROPY, A COMPLETE METRIC INVARIANT FOR AUTOMORPHISMS OF THE TORUS
• Hardness of conjugacy, embedding and factorization of multidimensional subshifts
• How does a choice of Markov partition affect the resultant symbolic dynamics?
• scientific article; zbMATH DE number 1714648 (Why is no real title available?)
• scientific article; zbMATH DE number 5380239 (Why is no real title available?)
• scientific article; zbMATH DE number 14993 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 3339152 (Why is no real title available?)
• Markov partitions and \(C\)-diffeomorphisms
• Markov Partitions for Axiom A Diffeomorphisms
• Markov shifts in the Hénon family
• Minimal presentations for irreducible sofic shifts
• Multiplicities of covers for sofic shifts
• Sofic shifts with synchronizing presentations
• Symbolic dynamics and Markov partitions
• Symbolic dynamics. One-sided, two-sided and countable state Markov shifts
• The decomposition theorem for two-dimensional shifts of finite type
• The undecidability of the domino problem
• The Williams conjecture is false for irreducible subshifts
• Tree-shifts of finite type

Cited in

(2)

• Computational complexity of k-block conjugacy
• Sofic shifts via Conley index theory: computing lower bounds on recurrent dynamics for maps

This page was built for publication: Optimal state amalgamation is NP-hard

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