Special Issue Implementation and Application of Automata (CIAA 2010)No Access

WEIGHTED AUTOMATA AND REGULAR EXPRESSIONS OVER VALUATION MONOIDS

MANFRED DROSTE

Institut für Informatik, Universität Leipzig, PF 100920, 04009 Leipzig, Germany

Search for more papers by this author

and

INGMAR MEINECKE

Institut für Informatik, Universität Leipzig, PF 100920, 04009 Leipzig, Germany

Search for more papers by this author

https://doi.org/10.1142/S0129054111009069Cited by:21 (Source: Crossref)

Abstract

Quantitative aspects of systems like consumption of resources, output of goods, or reliability can be modeled by weighted automata. Recently, objectives like the average cost or the longtime peak power consumption of a system have been modeled by weighted automata which are not semiring weighted anymore. Instead, operations like limit superior, limit average, or discounting are used to determine the behavior of these automata. Here, we introduce a new class of weight structures subsuming a range of these models as well as semirings. Our main result shows that such weighted automata and Kleene-type regular expressions are expressively equivalent both for finite and infinite words.

Dedicated to Werner Kuich on the occasion of his 70th birthday

Keywords:

References

J. Berstel and C. Reutenauer , Rational Series and Their Languages ( Springer , 1988 ) . Crossref, Google Scholar
J. R. Büchi, On a decision method in restricted second order arithmetics, Proc. Intern. Congress on Logic, Methodology and Philosophy of Science (Stanford University Press, 1962) pp. 1–11. Google Scholar
K. Chatterjee, L. Doyen and T. A. Henzinger, Quantitative languages, CSL 20085213, LNCS (Springer, 2008) pp. 385–400. Google Scholar
K. Chatterjee, L. Doyen and T. A. Henzinger, Alternating weighted automata, FCT 20095699, LNCS (Springer, 2009) pp. 3–13. Google Scholar
K. Chatterjee, L. Doyen and T. A. Henzinger, Expressiveness and closure properties for quantitative languages, 24th LICS 2009 (IEEE Comp. Soc. Press, 2009) pp. 199–208. Google Scholar
K. Chatterjee, L. Doyen and T. A. Henzinger, Probabilistic weighted automata, CONCUR 20095710, LNCS (Springer, 2009) pp. 244–258. Google Scholar
M. Droste , W. Kuich and H. Vogler (eds.) , Handbook of Weighted Automata , EATCS Monographs in Theoretical Computer Science ( Springer , 2009 ) . Crossref, Google Scholar
M. Droste and D. Kuske, Theoretical Computer Science 366, 199 (2006), DOI: 10.1016/j.tcs.2006.08.024. Crossref, Web of Science, Google Scholar
M. Droste and I. Meinecke, Describing average- and longtime-behavior by weighted MSO logics, MFCS 20106281, LNCS (Springer, 2010) pp. 537–548. Google Scholar
M. Droste and U. Püschmann, Int. J. of Algebra and Computation 17(2), 235 (2007), DOI: 10.1142/S0218196707003585. Link, Web of Science, Google Scholar
M. Droste and H. Vogler, Kleene and Büchi theorems for weighted automata and multi-valued logics over arbitrary bounded lattices, DLT 20106224, LNCS (Springer, 2010) pp. 160–172. Google Scholar
S. Eilenberg , Automata, Languages, and Machines A ( Academic Press , 1974 ) . Google Scholar
Z. Ésik and W. Kuich, J. of Automata, Languages and Combinatorics 10, 203 (2005). Google Scholar
Z. Ésik and W. Kuich, Finite automata, in Droste et al. [7], chap. 3 . Google Scholar
S. Kleene, Automata Studies, eds. C. Shannon and J. McCarthy (Princeton University Press, 1956) pp. 3–42. Google Scholar
W. Kuich , Handbook of Formal Languages 1 , eds. G. Rozenberg and A. Salomaa ( Springer , 1997 ) . Crossref, Google Scholar
W. Kuich and A. Salomaa , Semirings, Automata, Languages , EATCS Monographs in Theoretical Computer Science ( Springer , 1986 ) . Crossref, Google Scholar
O. Kupferman and Y. Lustig, Lattice automata, 8th VMCAI 20074349, LNCS (Springer, 2007) pp. 199–213. Google Scholar
S. Lombardy and J. Sakarovitch, Theoretical Computer Science 332, 141 (2005), DOI: 10.1016/j.tcs.2004.10.016. Crossref, Web of Science, Google Scholar
G. Rahonis, Fuzzy Sets and Systems 153, 275 (2005), DOI: 10.1016/j.fss.2004.12.003. Crossref, Web of Science, Google Scholar
A. Salomaa and M. Soittola , Automata-Theoretic Aspects of Formal Power Series , Texts and Monographs in Computer Science ( Springer , 1978 ) . Crossref, Google Scholar
M. Schützenberger, Information and Control 4, 245 (1961). Crossref, Google Scholar