scientific article; zbMATH DE number 177164

MaRDI QIDQ4037012zbMATH OpenFDO

Authors Dominique Perrin, Marcel Paul Schützenberger

Publication date 18 May 1993

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)

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.

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
• Synchronizing finite automata on Eulerian digraphs.
• A NOTE ON SYNCHRONIZED AUTOMATA AND ROAD COLORING PROBLEM
• Level Eulerian posets.
• Finding short synchronizing words for prefix codes
• 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)