On Determinism and Unambiguity of Weighted Two-Way Automata

被引：1

作者：

Carnino, Vincent ^{[1
]}

Lombardy, Sylvain ^{[2
]}

机构：

[1] Univ Paris Est Marne la Vallee, LIGM, UMR 8049, 5 Blvd Descartes, F-77420 Champs Sur Marne, France

[2] Inst Polytech Bordeaux, LaBRI, UMR 5800, F-33405 Talence, France

来源：

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE | 2015年 / 26卷 / 08期

关键词：

Weighted automata; two-way automata; determinization; unambiguity;

D O I：

10.1142/S0129054115400158

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

This paper deals with one-way and two-way weighted automata. When the semiring of weights is commutative, we prove that unambiguous one-way automata, unambiguous two-way automata and deterministic two-way automata realize the same (rational) power series. If the semiring of weights is not commutative, unambiguous one-way automata and deterministic two-way automata realize the same rational power series, but unambiguous two-way automata may realize non rational power series.

引用

页码：1127 / 1146

页数：20

共 14 条

[1]

Anselmo M., 1990, Automata, Languages and Programming. 17th International Colloquium Proceedings, P88, DOI 10.1007/BFb0032024

[2]

Carnino Vincent, 2014, Theoretical Computer Science. 8th IFIP TC 1/WG 2.2 International Conference, TCS 2014. Proceedings: LNCS 8705, P195, DOI 10.1007/978-3-662-44602-7_16

[3] On Determinism and Unambiguity of Weighted Two-way Automata [J].

Carnino, Vincent ;

Lombardy, Sylvain .

ELECTRONIC PROCEEDINGS IN THEORETICAL COMPUTER SCIENCE, 2014, (151) :188-200

[4]

Carton O, 2012, LECT NOTES COMPUT SC, V7410, P263, DOI 10.1007/978-3-642-31653-1_24

[5]

Engelfriet Joost, 2001, ACM T COMPUT LOG, V2, P216, DOI [10.1145/371316.371512, DOI 10.1145/371316.371512]

[6]

Ésik Z, 2009, MONOGR THEOR COMPUT, P69, DOI 10.1007/978-3-642-01492-5_3

[7]

FLIESS M, 1974, J MATH PURE APPL, V53, P197

[8]

Hopcroft J. E., 1967, IEEE COMPUTER SOC, P140, DOI DOI 10.1109/FOCS.1967.4

[9] Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton [J].

Klimann, I ;

Lombardy, S ;

Mairesse, J ;

Prieur, C .

THEORETICAL COMPUTER SCIENCE, 2004, 327 (03) :349-373

[10]

Lallement G., 1979, Semigroups and combinatorial applications

← 1 2 →