What's decidable about weighted automata

被引：9

作者：

Almagor, Shaull ^{[1
]}

Boker, Udi ^{[2
]}

Kupferman, Orna ^{[3
]}

机构：

[1] Technion, Comp Sci Dept, Haifa, Israel

[2] Interdisciplinary Ctr IDC, Herzliyya, Israel

[3] Hebrew Univ Jerusalem, Sch Engn & Comp Sci, Jerusalem, Israel

来源：

INFORMATION AND COMPUTATION | 2022年 / 282卷

基金：

欧盟地平线“2020”; 以色列科学基金会;

关键词：

LIMITEDNESS; SEMIGROUPS;

D O I：

10.1016/j.ic.2020.104651

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Weighted automata map input words to values, and have numerous applications in computer science. A result by Krob from the 90s implies that the universality problem is decidable for weighted automata over the tropical semiring with weights in N boolean OR {infinity} and is undecidable when the weights are in Z boolean OR {infinity}. We continue the study of the borders of decidability in weighted automata over the tropical semiring. We give a complete picture of the decidability and complexity of various decision problems for them, including non-emptiness, universality, equality, and containment. For the undecidability results, we provide direct proofs, which stay in the terrain of state machines. This enables us to tighten the results and apply them to a very simple class of automata. In addition, we provide a toolbox of algorithms and techniques for weighted automata, on top of which we establish the complexity bounds. (C) 2020 Elsevier Inc. All rights reserved.

引用

页数：20

共 45 条

[1] Weak Cost Register Automata Are Still Powerful [J].

Almagor, Shaull ;

Cadilhac, Michael ;

Mazowiecki, Filip ;

Perez, Guillermo A. .

DEVELOPMENTS IN LANGUAGE THEORY, DLT 2018, 2018, 11088 :83-95

[2]

Almagor S, 2011, LECT NOTES COMPUT SC, V6996, P13, DOI 10.1007/978-3-642-24372-1_2

[3] Reasoning about Online Algorithms with Weighted Automata [J].

Aminof, Benjamin ;

Kupferman, Orna ;

Lampert, Robby .

ACM TRANSACTIONS ON ALGORITHMS, 2010, 6 (02)

[4]

Andersson Daniel, 2006, P ESSLLI STUD SESS, P91

[5]

[Anonymous], 2012, AUTOMATA THEORETIC A

[6]

[Anonymous], 1967, Prentice-Hall Series in Automatic Computation

[7] Probabilistic Automata over Infinite Words: Expressiveness, Efficiency, and Decidability [J].

Baier, Christel ;

Bertrand, Nathalie ;

Groesser, Marcus .

ELECTRONIC PROCEEDINGS IN THEORETICAL COMPUTER SCIENCE, 2009, (03) :3-16

[8]

Berstel Jr J., 1988, RATIONAL SERIES THEI

[9]

Boker U, 2015, IEEE S LOG, P750, DOI 10.1109/LICS.2015.74

[10] Temporal Specifications with Accumulative Values [J].

Boker, Udi ;

Chatterjee, Krishnendu ;

Henzinger, Thomas A. ;

Kupferman, Orna .

ACM TRANSACTIONS ON COMPUTATIONAL LOGIC, 2014, 15 (04)

← 1 2 3 4 5 →