The road problem and homomorphisms of directed graphs

DOI10.1016/j.tcs.2023.113981arXiv2201.12942MaRDI QIDQ6175007

Sophie MacDonald

Publication date: 21 July 2023

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2201.12942

zbMATH Keywords

synchronizationMarkov chaindirected graphgraph homomorphismfinite automataroad colouring

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• The generalized road coloring problem and periodic digraphs
• The road coloring problem
• The road-colouring problem
• Equivalence of topological Markov shifts
• Graph isomorphism, general remarks
• Synchronizing finite automata on Eulerian digraphs.
• Between primitive and 2-transitive: synchronization and its friends
• A quadratic algorithm for road coloring
• Unzerlegbare, nicht negative Matrizen
• On the Probability of Being Synchronizable
• Subset Synchronization and Careful Synchronization of Binary Finite Automata
• On Two Algorithmic Problems about Synchronizing Automata
• Regular isomorphism of Markov chains is almost topological
• Reset Sequences for Monotonic Automata
• Slowly Synchronizing Automata and Digraphs
• The classification of one-sided Markov chains
• ENTROPY, A COMPLETE METRIC INVARIANT FOR AUTOMORPHISMS OF THE TORUS
• An Efficient Algorithm for Graph Isomorphism

This page was built for publication: The road problem and homomorphisms of directed graphs