Geodesic
Weighted automata and weighted logic on infinite words
Izvestiâ vysših učebnyh zavedenij. Matematika, no. 1 (2010), pp. 34-58.

Voir la notice de l'article provenant de la source Math-Net.Ru

We introduce weighted automata over infinite words with Muller acceptance condition and we show that their behaviors coincide with the semantics of weighted restricted MSO-sentences. Furthermore, we establish an equivalence property of weighted Muller and weighted Büchi automata over certain semirings.
Keywords: weighted logic, weighted Muller automata, infinitary formal power series, weighted Büchi automata. 
@article{IVM_2010_1_a4,
     author = {M. Droste and G. Rahonis},
     title = {Weighted automata and weighted logic on infinite words},
     journal = {Izvesti\^a vys\v{s}ih u\v{c}ebnyh zavedenij. Matematika},
     pages = {34--58},
     publisher = {mathdoc},
     number = {1},
     year = {2010},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IVM_2010_1_a4/}
}
TY  - JOUR
AU  - M. Droste
AU  - G. Rahonis
TI  - Weighted automata and weighted logic on infinite words
JO  - Izvestiâ vysših učebnyh zavedenij. Matematika
PY  - 2010
SP  - 34
EP  - 58
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IVM_2010_1_a4/
LA  - ru
ID  - IVM_2010_1_a4
ER  - 
%0 Journal Article
%A M. Droste
%A G. Rahonis
%T Weighted automata and weighted logic on infinite words
%J Izvestiâ vysših učebnyh zavedenij. Matematika
%D 2010
%P 34-58
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IVM_2010_1_a4/
%G ru
%F IVM_2010_1_a4
M. Droste; G. Rahonis. Weighted automata and weighted logic on infinite words. Izvestiâ vysših učebnyh zavedenij. Matematika, no. 1 (2010), pp. 34-58. http://geodesic.mathdoc.fr/item/IVM_2010_1_a4/

[1] Büchi J. R., “On a decision method in restricted second order arithmetic”, Proc. 1960 Int. Congr. for Logic, Methodology and Philosophy of Science, Standford, 1962, 1–11 | MR | Zbl

[2] Perrin D., Pin J. E., Infinite words, Elsevier, Amsterdam–Boston, 2004, 538 pp. | Zbl

[3] Thomas W., “Automata on infinite objects”, Handbook of Theoretical Computer Science, V. B., Elsevier, Amsterdam, 1990, 135–191 | MR

[4] Thomas W., “Languages, automata and logic”, Handbook of Formal Languages, V. 3, Springer, Berlin, 1997, 389–485 | MR

[5] Arnold A., Finite transition systems: semantics of communicating systems, Prentice Hall, Hertfordshire, 1994, 177 pp.

[6] Kurshan R. P., Computer-aided verification of coordinating processes, Princeton University Press, Princeton, 1994, 270 pp. | MR

[7] McMillan K., Symbolic model checking, Kluwer Academic Publishers, Boston, 1993, 194 pp. | Zbl

[8] Schützenberger M., “On the definition of a family of automata”, Inf. Control, 4:2–3 (1961), 245–270 | MR | Zbl

[9] Berstel J., Reutenauer C., Rational series and their languages, EATCS Monographs in Theoretical Computer Science, 12, Springer, Berlin, 1988, 151 pp. | MR | Zbl

[10] Kuich W., “Semirings and formal power series: their relevance to formal languages and automata theory”, Handbook of formal languages, V. 1, Springer, Berlin, 1997, 609–677 | MR

[11] Kuich W., Salomaa A., Semirings, automata, languages, EATCS Monographs in Theoretical Computer Science, 5, Springer, Berlin, 1986, 374 pp. | MR | Zbl

[12] Salomaa A., Soittola M., Automata-theoretic aspects of formal power series, Texts and Monographs in Computer Science, Springer, New York, 1978, 171 pp. | MR | Zbl

[13] Culik K., Kari J., “Image compression using weighted finite automata”, Comput. and Graphics, 17 (1993), 305–313 | DOI | MR

[14] Hafner U., Low bit-rate image and video coding with weighted finite automata, Ph. D. thesis, Universität Würzburg, 1999

[15] Jiang Z., Litow B., de Vel O., “Similarity enrichment in image compression through weighted finite automata”, Computing and Combinatorics, 6th Annual Internat. Conf. COCOON 2000, Lect. Notes Comput. Sci., 1858, Springer, Berlin, 2000, 447–456 | MR | Zbl

[16] Katritzke F., Refinements of data compression using weighted finite automata, Ph. D. thesis, Universität Siegen, 2001

[17] Knight K., Graehl J., “Machine transliteration”, Comput. Linguist., 24:4 (1998), 599–612

[18] Mohri M., Pereira F., Riley M., “The design principles of a weighted finite-state transducer library”, Theoret. Comput. Sci., 231:1 (2000), 17–32 | DOI | MR | Zbl

[19] Culik K., Karhumäki J., “Finite automata computing real functions”, SIAM J. Comput., 23:4 (1994), 789–814 | DOI | MR | Zbl

[20] Droste M., Kuske D., “Skew and infinitary formal power series”, Theoret. Comput. Sci., 366:3 (2006), 189–227 | MR

[21] Droste M., Püschmann U., “On weighted Büchi automata with order-complete weights”, Int. J. of Algebra and Comp., 17:2 (2007), 235–260 | DOI | MR | Zbl

[22] Ésik Z., Kuich W., “A semiring-semimodule generalization of $\omega$-regular languages. I”, J. Automata, Languages and Combinatorics, 10:2–3, Special issue on “Weighted automata” (2005), 203–242 | MR | Zbl

[23] Ésik Z., Kuich W., “A semiring-semimodule generalization of $\omega$-regular languages. II”, J. Automata, Languages and Combinatorics, 10:2–3, Special issue on “Weighted automata” (2005), 243–264 | MR | Zbl

[24] Krithivasan K., Sharda K., “Fuzzy $\omega$-automata”, Inf. Sci., 138:1–4 (2001), 257–281 | DOI | MR | Zbl

[25] Kuich W., Rahonis G., “Fuzzy regular languages over finite and infinite words”, Fuzzy Sets and Systems, 157:11 (2006), 1532–1549 | DOI | MR | Zbl

[26] Rahonis G., “Infinite fuzzy computations”, Fuzzy Sets and Systems, 153:2 (2005), 275–288 | DOI | MR | Zbl

[27] Droste M., Gastin P., “Weighted automata and weighted logics”, Theoret. Comput. Sci., 380:1–2 (2007), 69–86 | DOI | MR | Zbl

[28] Büchi J. R., “Weak second-order arithmetic and finite automata”, Z. Math. Logik Grundlagen Math., 6:1 (1960), 66–92 | DOI | MR | Zbl

[29] Elgot C., “Decision problems of finite automata design and related arithmetics”, Trans. Amer. Math. Soc., 98 (1961), 21–52 | DOI | MR

[30] Kuich W., “On skew formal power series”, Proc. Conf. on Algebraic Informatics, Thessaloniki, 2005, 7–30 | MR

[31] Bloom S. L., Ésik Z., Iteration Theories, EATCS Monographs on Theoretical Computer Science, Springer, Berlin, 1993, 630 pp. | MR

[32] Eilenberg S., Automata, languages and machines, Vol. A, Academic Press, New York, 1974, 387 pp. | MR | Zbl

[33] Droste M., Rahonis G., “Weighted automata and weighted logics on infinite words”, Developments in Language Theory, 10th Internat. Conf. DLT 2006, Lect. Notes Comput. Sci., 4036, 2006, 49–58 | MR | Zbl

[34] Droste M., Vogler H., “Weighted tree automata and weighted logics”, Theoret. Comput. Sci., 366:3 (2006), 228–247 | DOI | MR | Zbl

[35] Mäurer I., “Weighted picture automata and weighted logics”, 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS 2006, Lect. Notes Comput. Sci., 3884, 2006, 313–324 | MR | Zbl

[36] Meinecke I., “Weighted logics for traces”, Computer Science Theory and Applications, 1st Internat. Computer Science Symposium in Russia. CSR 2006, Lect. Notes Comput. Sci., 3967, 2006, 235–246 | MR | Zbl

[37] Ésik Z., Kuich W., “On iteration semiring-semimodule pairs”, Semigroup Forum, 75 (2007), 1 | DOI | MR | Zbl

[38] Balbes R., Dwinger P., Distributive lattices, University of Missouri Press, Columbia, 1975, 294 pp. | MR