scientific article; zbMATH DE number 7310067

zbMath1477.68146MaRDI QIDQ5150411

Mikhail V. Berlinkov

Publication date: 15 February 2021

Full work available at URL: http://mathnet.ru/eng/pdm273

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

road coloring problemoptimal coloringsynchronizing automata

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Related Items (3)

Approximating the minimum length of synchronizing words is hard ⋮ A multi-parameter analysis of hard problems on deterministic finite automata ⋮ A complete solution to the complexity of synchronizing road coloring for non-binary alphabets

Cites Work

• Unnamed Item
• The road coloring problem
• Equivalence of topological Markov shifts
• Approximating the minimum length of synchronizing words is hard
• A quadratic algorithm for road coloring
• Reset Sequences for Monotonic Automata
• Synchronizing Automata and the Černý Conjecture
• Similarity of automorphisms of the torus

This page was built for publication: