On counter machines, reachability problems, and diophantine equations

被引：2

作者：

Ibarra, Oscar H. ^{[1
]}

Dang, Zhe ^{[2
]}

Yang, Linmin ^{[2
]}

机构：

[1] Univ Calif Santa Barbara, Dept Comp Sci, Santa Barbara, CA 93106 USA

[2] Washington State Univ, Sch Elect Engn & Comp Sci, Pullman, WA 99164 USA

来源：

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE | 2008年 / 19卷 / 04期

关键词：

counter machine; reversal-bounded; reachability; Diophantine equation;

D O I：

10.1142/S0129054108006042

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We give a brief survey of results that use "reversal-bounded counters" in studying reachability problems for various classes of transition systems. We also discuss the connection between the decidability of reachability in counter machines and the solvability of certain Diophantine equations.

引用

页码：919 / 934

页数：16

共 22 条

[1] A THEORY OF TIMED AUTOMATA [J].

ALUR, R ;

DILL, DL .

THEORETICAL COMPUTER SCIENCE, 1994, 126 (02) :183-235

[2]

BOZGA M, 2006, ICALP, P577

[3]

Comon H, 1998, LECT NOTES COMPUT SC, V1427, P268, DOI 10.1007/BFb0028751

[4]

DANG Z, 2002, P 13 INT S ALG COMP, P103

[5]

DANG Z, THEORETICAL COMPUTER, V302

[6]

DANG Z, 2000, LECT NOTES COMPUTER, V185, P69

[7] Decidability of model checking for infinite-state concurrent systems [J].

Esparza, J .

ACTA INFORMATICA, 1997, 34 (02) :85-107

[8] SEMIGROUPS PRESBURGER FORMULAS AND LANGUAGES [J].

GINSBURG, S ;

SPANIER, EH .

PACIFIC JOURNAL OF MATHEMATICS, 1966, 16 (02) :285-&

[9] 2-WAY COUNTER MACHINES AND DIOPHANTINE EQUATIONS [J].

GURARI, EM ;

IBARRA, OH .

JOURNAL OF THE ACM, 1982, 29 (03) :863-873

[10] THE COMPLEXITY OF DECISION-PROBLEMS FOR FINITE-TURN MULTICOUNTER MACHINES [J].

GURARI, EM ;

IBARRA, OH .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1981, 22 (02) :220-229

← 1 2 3 →