No Access

ON WEIGHTED BÜCHI AUTOMATA WITH ORDER-COMPLETE WEIGHTS

MANFRED DROSTE

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

Search for more papers by this author

and

ULRIKE PÜSCHMANN

Institut für Algebra, Technische Universität Dresden, 01062 Dresden, Germany

Search for more papers by this author

https://doi.org/10.1142/S0218196707003585Cited by:7 (Source: Crossref)

Abstract

We investigate Büchi automata with weights for the transitions. Assuming that the weights are taken in a suitable ordered semiring, we show how to define the behaviors of these automata on infinite words. Our main result shows that the formal power series arising in this way are precisely the ones which can be constructed using ω-rational operations. This extends the classical Kleene–Schützenberger result for weighted finite automata to the case of infinite words and generalizes Büchi's theorem on languages of infinite words. We also derive versions of our main result for non-complete semirings and for other automata models.

Keywords:

AMSC: 68Q45, 06F25, 13J25

References

S. Abramsky and S. Vickers, Math. Struct. Comput. Science 3, 161 (1993). Crossref, Google Scholar
F. Baccelli et al. , Synchronization and Linearity ( Wiley , 1992 ) , http://www-rocq.inria.fr/metalau/cohen/SED/book-online.html . Google Scholar
B. Bérard et al. , Systems and Software Specification ( Springer , 2001 ) . Crossref, Google Scholar
J. Berstel and C. Reutenauer , Rational Series and Their Languages , EATCS Texts and Monographs in Computer Science ( Springer , Berlin , 1988 ) . Crossref, Google Scholar
G. Birkhoff , Lattice Theory , American Mathematical Society Colloquium Publications 25 ( American Mathematical Society , 1993 ) . Google Scholar
B. Borchardt, The Theory of Recognizable Tree Series, Ph.D. thesis, Technische Universität Dresden (2004) . Google Scholar
J. R. Büchi, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 6, 66 (1960). Crossref, Google Scholar
A. Buchsbaum, R. Giancarlo and J. Westbrook, Siam J. Comput. 30, 1502 (2000). Crossref, Web of Science, Google Scholar
R. G. Bukharaev , Theorie der stochastischen Automaten ( B. G. Teubner , 1995 ) . Crossref, Google Scholar
K. Culik II and J. Kari, Comput. Graph. 17(3), 305 (1993). Crossref, Web of Science, Google Scholar
R. A. Cuninghame-Green, Advances in Imaging and Electron Physics 90, ed. P. Hawkes (Academic Press, 1995) pp. 1–121. Google Scholar
B. A. Davey and H. A. Priestley , Introduction to Lattices and Order , Cambridge Mathematical Textbooks ( University Press , Cambridge , 1990 ) . Google Scholar
M. Droste and P. Gastin, Aperiodic and star-free formal power series in partially commuting variables, Formal Power Series and Algebraic Combinatorics, 12th Int. Conf. Theor. Comput. Syst., eds. D. Krob, A. A. Mikhalev and A. V. Mikhalev (2000) pp. 158–169. Google Scholar
M. Droste and D. Kuske, Theor. Comput. Sci. 366, 199 (2006). Crossref, Web of Science, Google Scholar
S. Eilenberg , Automata, Languages, and Machines A ( Academic Press, Inc. , San Diego , 1974 ) . Google Scholar
Z. Ésik and W. Kuich, J. Automata, Languages and Combinatorics 10(2–3), 203 (2005). Google Scholar
S. Gaubert et al. , 26ème École de Printemps d'Informatique Théorique ( Noirmoutier , 1998 ) . Google Scholar
J. S. Golan , Semirings and Their Applictions ( Kluwer Academic Publishers , Dordrecht, Boston, London , 1999 ) . Crossref, Google Scholar
G. Grätzer , General Lattice Theory ( Birkhäuser , Basel, Stuttgart , 1978 ) . Crossref, Google Scholar
U. Hafner, Low bit-rate image and video controlling with weighted finite automata, PhD thesis, Universität Würzburg (1997) . Google Scholar
Z. Jiang, B. Litow and O. de Vel, Similarity enrichment in image compression through weighted finite automata, COCOON 2000, Lecture Notes in Computer Science 1858 (Springer, 2000) pp. 447–456. Google Scholar
F. Katritzke, Refinements of data compression using weighted finite automata, PhD thesis, Universität Siegen (2001) . Google Scholar
S. C. Kleene, Automata Studies, eds. C. E. Shannon and J. McCarthy (Princeton University Press, Princeton, NJ, 1956) pp. 3–41. Google Scholar
W. Kuich, Handbook of Formal Languages 1, eds. G. Rozenberg and A. Salomaa (Springer, Berlin, 1997) pp. 609–677. Crossref, Google Scholar
W. Kuich and A. Salomaa , Semirings, Automata, Languages , EATCS Texts and Monographs in Computer Science ( Springer , Berlin , 1986 ) . Crossref, Google Scholar
M. Mohri, Comput. Linguist. 23, 269 (1997). Web of Science, Google Scholar
M. Mohri, F. Pereira and M. Riley, Theor. Comput. Sci. 231, 17 (2000). Crossref, Web of Science, Google Scholar
J. Mordeson and D. Malik , Fuzzy Automata and Languages ( Chapman & Hall/CRC , 2002 ) . Crossref, Google Scholar
C. J. Mulvey, Supplemento ai Rendiconti del Circolo Matematico di Palermo II(12), 99 (1986). Google Scholar
D. Perrin and J.-E. Pin , Infinite Words ( Elsevier , 2004 ) . Google Scholar
U. Püschmann, Zu Kostenfunktionen von Büchi-Automaten, Diplomarbeit, Technische Universität Dresden (2003); available online at http://www.math.tu-dresden.de/up/diplom.ps . Google Scholar
G. Rahonis, Fuzzy Sets Syst. 153, 275 (2005). Crossref, Web of Science, Google Scholar
K. I. Rosenthal , Quantales and Their Applications , Pitman Research Notes in Mathematics Series 234 ( Longman , 1990 ) . Google Scholar
A. Salomaa and M. Soittola , Automata-Theoretic Aspects of Formal Power Series , EATCS Texts and Monographs in Computer Science ( Springer , New York , 1978 ) . Crossref, Google Scholar
M. P. Schützenberger, Inform. Contr. 4, 245 (1961). Crossref, Google Scholar
W. Thomas, Handbook of Theoretical Computer Science Formal Models and Semantics, ed. J. van Leeuwen (Elsevier Science Publishers B. V., Amsterdam, 1990) pp. 133–191. Google Scholar
G. Tischler, Refinement of near random access video coding with weighted finite automata, CIAA 2006, Lecture Notes in Computer Science 4094 (Springer, 2006) pp. 46–57. Google Scholar