scientific article; zbMATH DE number 177164

zbMATH Open0787.68073MaRDI QIDQ4037012FDOQ4037012

Authors: Dominique Perrin, Marcel Paul Schützenberger 

Publication date: 18 May 1993

Title of this publication is not available (Why is that?)

Recommendations

• The road coloring problem
• Synchronised automata
• scientific article; zbMATH DE number 2087221
• A NOTE ON SYNCHRONIZED AUTOMATA AND ROAD COLORING PROBLEM
• Synchronizing finite automata on Eulerian digraphs.

zbMATH Keywords

prefix codesfinite deterministic automatonsynchronizing wordsreset sequenceresolving blockroad coloring conjecturesemigroup of transitions

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Algebraic theory of languages and automata (68Q70) Free semigroups, generators and relations, word problems (20M05)

Cited In (12)

• Sofic shifts with synchronizing presentations
• Cycles of relatively prime length and the road coloring problem
• Non-commutative symbolic coding
• A Quadratic Upper Bound on the Size of a Synchronizing Word in One-Cluster Automata
• An algorithm for road coloring
• Černý's conjecture and the road colouring problem
• A NOTE ON SYNCHRONIZED AUTOMATA AND ROAD COLORING PROBLEM
• Finding short synchronizing words for prefix codes
• Synchronizing finite automata on Eulerian digraphs.
• Level Eulerian posets.
• A quadratic algorithm for road coloring
• The road coloring problem

This page was built for publication:

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