%0 Journal Article %1 droste/pueschmann:2007 %A Droste, Manfred %A Püschmann, Ulrike %D 2007 %J International Journal of Algebra and Computation %K 2005 büchiautomata completesemiring formalpowerseries myown ordercomplete weightedautomata %N 2 %P 235--260 %T On Weighted Büchi Automata with Order-Complete Weights %U http://www.worldscinet.com/ijac/17/preserved-docs/1702/S0218196707003585.pdf %V 17 %X 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.

@article{droste/pueschmann:2007, 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.}, added-at = {2009-10-22T13:28:24.000+0200}, author = {Droste, Manfred and P{\"{u}}schmann, Ulrike}, biburl = {https://www.bibsonomy.org/bibtex/2ea2413700d0d28b182fa718f0130942d/ulpsch}, interhash = {aa7564e9a02c9e88a556e8d20110b502}, intrahash = {ea2413700d0d28b182fa718f0130942d}, journal = {International Journal of Algebra and Computation}, keywords = {2005 büchiautomata completesemiring formalpowerseries myown ordercomplete weightedautomata}, number = 2, pages = {235--260}, timestamp = {2012-01-16T16:24:43.000+0100}, title = {On Weighted B\"{u}chi Automata with Order-Complete Weights}, url = {http://www.worldscinet.com/ijac/17/preserved-docs/1702/S0218196707003585.pdf}, volume = 17, year = 2007 }