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
    Carnino, Vincent
    Lombardy, Sylvain
    [J]. 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
    Klimann, I
    Lombardy, S
    Mairesse, J
    Prieur, C
    [J]. THEORETICAL COMPUTER SCIENCE, 2004, 327 (03) : 349 - 373
  • [10] Lallement G., 1979, Semigroups and combinatorial applications
12