Decidability, undecidability, and PSPACE-completeness of the twins property in the tropical semiring

被引：7
作者：
Kirsten, Daniel [1 ]
机构：
[1] Humboldt Univ, Inst Informat, D-10099 Berlin, Germany
来源：
THEORETICAL COMPUTER SCIENCE | 2012年 / 420卷
关键词：
Weighted finite automata; Formal power series; Tropical semiring; Twins property; STAR HEIGHT; TRANSDUCERS; AUTOMATA; SEQUENTIALITY;
D O I：
10.1016/j.tcs.2011.11.006
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We solve a problem already investigated by Mohri in 1997: we show that the twins property for weighted finite automata over the tropical semiring is decidable and PSPACE-complete. We also point out that it is undecidable whether two given states are twins. (C) 2011 Elsevier B.V. All rights reserved.
引用
收藏
页码：56 / 63
页数：8
相关论文
共 28 条
  • [1] Allauzen C., 2003, Journal of Automata, Languages and Combinatorics, V8, P117
  • [2] Squaring transducers:: an efficient procedure for deciding functionality and sequentiality
    Béal, MP
    Carton, O
    Prieur, C
    Sakarovitch, J
    [J]. THEORETICAL COMPUTER SCIENCE, 2003, 292 (01) : 45 - 63
  • [3] Berstel J., 1984, EATCS MONOGRAPHS THE
  • [4] Berstel J., 2010, ENCY MATH APPL, V137
  • [5] Borchardt B., 2003, ACTA CYBERNET, V14, P509
  • [6] Buchse M., 2010, J AUTOMATA LANGUAGES, V15
  • [7] Choffrut C., 1977, Theoretical Computer Science, V5, P325, DOI 10.1016/0304-3975(77)90049-4
  • [8] Droste M, 2009, MONOGR THEOR COMPUT, P1, DOI 10.1007/978-3-642-01492-5
  • [9] On the Burnside problem for semigroups of matrices in the (max,+) algebra
    Gaubert, S
    [J]. SEMIGROUP FORUM, 1996, 52 (03) : 271 - 292
  • [10] Gaubert S., 1998, T AUTOMATIC CONTROL, V44, P683
123