Continuous-time orbit problems are decidable in polynomial-time

被引：5

作者：

Chen, Taolue ^{[1
]}

Yu, Nengkun ^{[3
,4
]}

Han, Tingting ^{[2
]}

机构：

[1] Middlesex Univ, Dept Comp Sci, London N17 8HR, England

[2] Univ London, Dept Comp Sci & Informat Syst, London WC1E 7HU, England

[3] Univ Waterloo, Inst Quantum Comp, Waterloo, ON N2L 3G1, Canada

[4] Univ Guelph, Dept Math & Stat, Guelph, ON N1G 2W1, Canada

来源：

INFORMATION PROCESSING LETTERS | 2015年 / 115卷 / 01期

关键词：

Dynamical systems; Differential equation; Computational complexity; Continuous-time orbit problem; Linear algebra;

D O I：

10.1016/j.ipl.2014.08.004

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

引用

页码：11 / 14

页数：4

共 9 条

[1]

[Anonymous], SODA

[2]

Arvind V, 2008, LECT NOTES COMPUT SC, V5092, P160

[3]

Baker A., 1990, Transcendental Number Theory

[4] The continuous Skolem-Pisot problem [J].

Bell, Paul C. ;

Delvenne, Jean-Charles ;

Jungers, Raphael M. ;

Blondel, Vincent D. .

THEORETICAL COMPUTER SCIENCE, 2010, 411 (40-42) :3625-3634

[5]

Chonev V, 2013, STOC'13: PROCEEDINGS OF THE 2013 ACM SYMPOSIUM ON THEORY OF COMPUTING, P941

[6]

Cohen H., 1993, COURSE COMPUTATIONAL

[7] Reachability in linear dynamical systems [J].

Hainry, Emmanuel .

LOGIC AND THEORY OF ALGORITHMS, 2008, 5028 :241-250

[8]

Jin-Yi Cai, 1994, International Journal of Foundations of Computer Science, V5, P293, DOI 10.1142/S0129054194000165

[9] POLYNOMIAL-TIME ALGORITHM FOR THE ORBIT PROBLEM [J].

KANNAN, R ;

LIPTON, RJ .

JOURNAL OF THE ACM, 1986, 33 (04) :808-821

← 1 →