Examples of undecidable problems for 2-generator matrix semigroups

被引：20

作者：

Cassaigne, J

Karhumaki, J

机构：

[1] Inst Math Luminy, F-13288 Marseille 09, France

[2] Univ Turku, Dept Math, FIN-20014 Turku, Finland

[3] Turku Ctr Comp Sci, Turku, Finland

来源：

THEORETICAL COMPUTER SCIENCE | 1998年 / 204卷 / 1-2期

基金：

芬兰科学院;

关键词：

undecidability; matrix problems; two-generator semigroup;

D O I：

10.1016/S0304-3975(98)00029-2

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We show that the following two problems are undecidable: given two square matrices, decide whether the semigroup that they generate contains the zero matrix, and whether it contains a matrix having a zero in the right upper corner. (C) 1998-Elsevier Science B.V. All rights reserved.

引用

页码：29 / 34

页数：6

共 10 条

[1]

[Anonymous], 1978, AUTOMATA THEORETIC A

[2]

Berstel J., 1988, RATIONAL SERIES THEI

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

Blondel, VD ;

Tsitsiklis, JN .

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

[4]

Harju T., 1997, HDB FORMAL LANGUAGES, V1, P439

[5] FINITENESS OF SEMIGROUP LINEAR REPRESENTATIONS IS DECIDABLE [J].

JACOB, G .

JOURNAL OF ALGEBRA, 1978, 52 (02) :437-459

[6]

Klarner D. A., 1991, International Journal of Algebra and Computation, V1, P223, DOI 10.1142/S0218196791000146

[7]

Mandel A., 1977, Theoretical Computer Science, V5, P101, DOI 10.1016/0304-3975(77)90001-9

[8]

MARMA Z, 1974, MATH THEORY COMPUTAT

[9] Decision problems for semi-Thue systems with a few rules [J].

Matiyasevich, Y ;

Senizergues, G .

11TH ANNUAL IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE, PROCEEDINGS, 1996, :523-531

[10]

PATERSON MS, 1970, STUD APPL MATH, V49, P105

← 1 →