Undecidable problems for probabilistic automata of fixed dimension

被引：64

作者：

Blondel, VD ^{[1
]}

Canterini, V ^{[1
]}

机构：

[1] Univ Louvain, Div Appl Math, B-1348 Louvain, Belgium

来源：

THEORY OF COMPUTING SYSTEMS | 2003年 / 36卷 / 03期

关键词：

D O I：

10.1007/s00224-003-1061-2

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We prove that several problems associated with probabilistic finite automata are undecidable for automata whose number of input letters and number of states are fixed. As a corollary of one of our results we prove that the problem of determining if the set of all products of two 47 x 47 matrices with nonnegative rational entries is bounded is undecidable.

引用

收藏

页码：231 / 245

页数：15

相关论文

共 32 条

[1] ARTHUR-MERLIN GAMES - A RANDOMIZED PROOF SYSTEM, AND A HIERARCHY OF COMPLEXITY CLASSES [J].

BABAI, L ;

MORAN, S .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1988, 36 (02) :254-276

[2]

Bertoni A., 1975, GI 4 JAHRESTAGUNG LE, V26, P107

[3]

Bertoni A., 1977, Automata, Languages and Programming, V52, P87

[4] When is a pair of matrices mortal? [J].

Blondel, VD ;

Tsitsiklis, JN .

INFORMATION PROCESSING LETTERS, 1997, 63 (05) :283-286

[5] A survey of computational complexity results in systems and control [J].

Blondel, VD ;

Tsitsiklis, JN .

AUTOMATICA, 2000, 36 (09) :1249-1274

[6] The boundedness of all products of a pair of matrices is undecidable [J].

Blondel, VD ;

Tsitsiklis, JN .

SYSTEMS & CONTROL LETTERS, 2000, 41 (02) :135-140

[7]

Blythe J., 1999, Artificial intelligence today. Recent trends and developments, P85

[8] On the power of finite automata with both nondeterministic and probabilistic states [J].

Condon, A ;

Hellerstein, L ;

Pottle, S ;

Wigderson, A .

SIAM JOURNAL ON COMPUTING, 1998, 27 (03) :739-762

[9]

Condon Anne, 1989, P 30 ANN S FDN COMP, P462

[10]

EHRENFEUCHT A, 1982, THEOR COMPUT SCI, V21, P119, DOI 10.1016/0304-3975(89)90080-7

← 1 2 3 4 →