A Kleene-Schützenberger Theorem for Trace Series over Bounded Lattices

• Autorzy: Huschenbett M.
• Języki publikacji: EN

Abstrakty

EN

We study weighted trace automata with weights in strong bimonoids. Traces form a generalization of words that allow to model concurrency; strong bimonoids are algebraic structures that can be regarded as "semirings without distributivity". A very important example for the latter are bounded lattices, especially non-distributive ones. We show that if both operations of the bimonoid are locally finite, then the classes of recognizable and mc-rational trace series coincide and, in general, are properly contained in the class of c-rational series. Moreover, if, in addition, in the bimonoid the addition is idempotent and the multiplication is commutative, then all three classes coincide.

Słowa kluczowe

EN

weighted automata; concurrency; multi-valued logics; trace; formal power series

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 112, nr 2/3
• Strony: 171--191
• Opis fizyczny: Bibliogr. 21 poz.

Twórcy

autor

Huschenbett M.

• Institut für Theoretische Informatik, TU Ilmenau, Postfach 10 05 65, D-98684 Ilmenau, Germany,

Bibliografia

• [1] J. Berstel and C. Reutenauer. Rational Series and their Languages, volume 12 of EATCS Monographs on Theoretical Computer Science. Springer, 1988.
• [2] G. Birkhoff and J. von Neumann. The logic of quantum mechanics. Annals of Mathematics, 37:823-843, 1936.
• [3] K. Chatterjee, L. Doyen, and T. A. Henzinger. Quantitative languages. In M. Kaminski and S. Martini, editors, Computer Science Logic (CSL 2008), volume 5213 of Lecture Notes in Computer Science, pages 385-400. Springer, 2008.
• [4] K. Chatterjee, L. Doyen, and T. A. Henzinger. Expressiveness and closure properties for quantitative languages. In Logic in Computer Science (LICS 2009), pages 199-208. IEEE Computer Society, 2009.
• [5] V. Diekert and Y. M´etivier. Partial commutation and traces. In G. Rozenberg and A. Salomaa, editors, Handbook of Formal Languages, volume 3, pages 457-533. Springer, 1997.
• [6] V. Diekert and G. Rozenberg, editors. The Book of Traces. World Scienific Publishing, 1995.
• [7] M. Droste and P. Gastin. The Kleene-Schützenberger theorem for formal power series in partially commuting variables. Information and Computation, 153(1):47-80, 1999.
• [8] M. Droste, W. Kuich, and H. Vogler, editors. Handbook of Weighted Automata. Monographs in Theoretical Computer Science. An EATCS Series. Springer, 2009.
• [9] M. Droste, T. Stüber, and H. Vogler. Weighted finite automata over strong bimonoids. Information Sciences, 180(1):156-166, 2010.
• [10] M. Droste and H. Vogler. Kleene and Büchi theorems for weighted automata and multi-valued logics over arbitrary bounded lattices. In Y. Gao, H. Lu, S. Seki, and S. Yu, editors, Developments in Language Theory (DLT 2010), volume 6224 of Lecture Notes in Computer Science, pages 162-172. Springer, 2010.
• [11] Z. Esik and W. Kuich. Finite automata. In Droste et al. [8], chapter 3, pages 69-104.
• [12] I. Fichtner, D. Kuske, and I. Meinecke. Traces, series-parallel posets, and pictures: A weighted study. In Droste et al. [8], chapter 10, pages 397-441.
• [13] M. Huschenbett. A Kleene-Schützenberger theorem for trace series over bounded lattices. In H. Bordihn, R. Freund, T. Hinze, M. Holzer, M. Kutrib, and F. Otto, editors, Non-Classical Models of Automata and Applications (NCMA 2010), volume 263 of [e-mail], pages 99-111. österr. Computer Gesellsch., 2010.
• [14] S. C. Kleene. Representation of events in nerve nets and finite automata. In C. E. Shannon and J. McCarthy, editors, Automata Studies, chapter 1, pages 3-42. Princeton University Press, 1956.
• [15] D. Krob. The equality problem for rational series with multiplicities in the tropical semiring is undecidable. International Journal of Algebra and Computation, 4(3):405-425, 1994.
• [16] O. Kupferman and Y. Lustig. Lattice automata. In B. Cook and A. Podelski, editors, Verification, Model Checking, and Abstract Interpretation (VMCAI 2007), volume 4349 of Lecture Notes in Computer Science, pages 199-213. Springer, 2007.
• [17] D. Kuske. Weighted asynchronous cellular automata. Theoretical Computer Science, 374(1-3):127-148, 2007.
• [18] A. Mazurkiewicz. Concurrent program schemes and their interpretation. Technical Report DIAMA PB 78, Arhus University, 1977.
• [19] I. Meinecke. Weighted logics for traces. In D. Grigoriev, J. Harrison, and A. Hirsch, Edward, editors, Computer Science Symposium in Russia (CSR 2006), volume 3976 of Lecture Notes in Computer Science, pages 235-246. Springer, 2006.
• [20] E. Ochmański. Recognizable trace languages. In Diekert and Rozenberg [6], chapter 6, pages 167-204.
• [21] M. P. Schützenberger. On the definition of a family of automata. Information and Control, 4(2-3):245-270, 1961.