2016/12/14 by J. Andrés Montoya, J. Andres Montoya, Montoya, J. Andres +2
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Algorithm #Artificial intelligence #Automaton #Cellular Automata and Applications #Class (philosophy) #Combinatorics #Computer science #Conjecture #DNA and Biological Computing #Deterministic finite automaton #Discrete mathematics #FOS: Computer and information sciences #Finite-state machine #Formal Languages and Automata Theory (cs.FL) #Mathematics #Planar #Synchronization (alternating current) #Synchronizing #Theoretical computer science #Topology (electrical circuits) #cs.FL #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1612.04462
17 pages, 2 figures
arxiv created 2016/12/14 · openalex publication_date 2016/12/14 · arxiv updated 2016/12/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
Planar automata seems to be representative of the synchronizing behavior of deterministic finite state automata. We conjecture that Černy's conjecture holds true, if and only if, it holds true for planar automata. In this paper we have gathered some evidence concerning this conjecture. This evidence amounts to show that the class of planar automata is representative of the algorithmic hardness of synchronization