Synchronizing finite automata on Eulerian digraphs

被引：81

作者：

Kari, J ^{[1
]}

机构：

[1] Univ Iowa, Dept Comp Sci, Iowa City, IA 52242 USA

来源：

THEORETICAL COMPUTER SCIENCE | 2003年 / 295卷 / 1-3期

关键词：

finite automata; synchronization;

D O I：

10.1016/S0304-3975(02)00405-X

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Cerny's conjecture and the road coloring problem are two open problems concerning synchronization of finite automata. We prove these conjectures in the special case that the vertices have uniform in- and outdegrees. (C) 2002 Elsevier Science B.V. All rights reserved.

引用

页码：223 / 232

页数：10

共 16 条

[1]

Adler R. L., 1970, MEM AM MATH SOC, V98

[2] EQUIVALENCE OF TOPOLOGICAL MARKOV SHIFTS [J].

ADLER, RL ;

GOODWYN, LW ;

WEISS, B .

ISRAEL JOURNAL OF MATHEMATICS, 1977, 27 (01) :49-63

[3] Cycles of relatively prime length and the road coloring problem [J].

Carbone, A .

ISRAEL JOURNAL OF MATHEMATICS, 2001, 123 (1) :303-316

[4]

Cerny Jan, 1964, Mat.-Fyz. Cas., V14, P208

[5]

CULIK K, 1999, 323 TUCS U TURK TURK

[6] ON THE ROAD COLORING PROBLEM [J].

FRIEDMAN, J .

PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY, 1990, 110 (04) :1133-1135

[7]

Gohring W., 1997, Journal of Automata, Languages and Combinatorics, V2, P209

[8]

Jonoska N., 1995, C NUMERANTIUM, V110, P201

[9]

MATEESCU A, 1999, EATCS B, V68, P134

[10]

OBRIEN GL, 1981, ISRAEL J MATH, V39, P145, DOI 10.1007/BF02762860

← 1 2 →