Undecidability and Finite Automata

被引：0

作者：

Endrullis, Jorg ^{[1
]}

Shallit, Jeffrey ^{[2
]}

Smith, Tim ^{[2
]}

机构：

[1] Vrije Univ Amsterdam, Dept Comp Sci, Boelelaan 1081a, NL-1081 HV Amsterdam, Netherlands

[2] Univ Waterloo, Sch Comp Sci, Waterloo, ON N2L 3G1, Canada

来源：

DEVELOPMENTS IN LANGUAGE THEORY, DLT 2017 | 2017年 / 10396卷

关键词：

Finite automata; Undecidability; Conjugate; Power;

D O I：

10.1007/978-3-319-62809-7_11

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Using a novel rewriting problem, we show that several natural decision problems about finite automata are undecidable (i.e., recursively unsolvable). In contrast, we also prove three related problems are decidable. We apply one result to prove the undecidability of a related problem about k-automatic sets of rational numbers.

引用

页码：160 / 172

页数：13

共 16 条

[1]

Alur R, 2011, LECT NOTES COMPUT SC, V6756, P1, DOI 10.1007/978-3-642-22012-8_1

[2]

[Anonymous], 2009, 2 COURSE FORMAL LANG

[3]

[Anonymous], 1972, Mathematical systems theory, DOI 10.1007/BF01706087

[4]

[Anonymous], 1979, Introduction to Automata Theory, Languages, and Computation

[5]

[Anonymous], 1961, SPRACHTYPOLOGIE UNIV

[6]

Book RV., 1993, STRING REWRITING SYS, DOI DOI 10.1007/978-1-4613-9771-7

[7] FIXED-POINT LANGUAGES, EQUALITY LANGUAGES, AND REPRESENTATION OF RECURSIVELY-ENUMERABLE LANGUAGES [J].

ENGELFRIET, J ;

ROZENBERG, G .

JOURNAL OF THE ACM, 1980, 27 (03) :499-518

[8] SOME RECURSIVELY UNSOLVABLE PROBLEMS IN ALGOL-LIKE LANGUAGES [J].

GINSBURG, S ;

ROSE, GF .

JOURNAL OF THE ACM, 1963, 10 (01) :29-&

[9]

Hoogeboom H. J., 2012, ARE THERE UNDECIDABL

[10]

Lyndon R. C., 1962, Michigan Math. J, V9, P289

← 1 2 →