Abstract
We study a quantitative model of traces, i.e. trace series which assign to every trace an element from a semiring. We show the coincidence of recognizable trace series with those which are definable by restricted formulas from a weighted logics over traces. We use a translation technique from formulas over words to those over traces, and vice versa. This way, we show also the equivalence of aperiodic and first-order definable trace series.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Berstel, J., Reutenauer, C.: Rational Series and Their Languages. EATCS Monographs on Theoret. Comp. Sc., vol. 12. Springer, Heidelberg (1988)
Bollig, B.: On the expressiveness of asynchronous cellular automata. In: Liśkiewicz, M., Reischuk, R. (eds.) FCT 2005. LNCS, vol. 3623, pp. 528–539. Springer, Heidelberg (2005)
Bollig, B., Leucker, M.: Message-passing automata are expressively equivalent to EMSO logic. Theoret. Comp. Sc (to appear, 2006)
Büchi, J.R.: Weak second-order arithmetic and finite automata. Z. Math. Logik Grundlagen Math. (6), 66–92 (1960)
Diekert, V., Métivier, Y.: Partial commutation and traces. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, Beyond Words, ch. 8, vol. 3, pp. 457–534. Springer, Heidelberg (1997)
Diekert, V., Rozenberg, G. (eds.): The Book of Traces. World Scientific, Singapore (1995)
Droste, M., Gastin, P.: The Kleene-Schützenberger theorem for formal power series in partially commuting variables. Information and Computation 153, 47–80 (1999)
Droste, M., Gastin, P.: On aperiodic and star-free formal power series in partially commuting variables. In: Formal Power Series and Algebraic Combinatorics (Moscow 2000), pp. 158–169. Springer, Berlin (2000)
Droste, M., Gastin, P.: Weighted automata and weighted logics. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 513–525. Springer, Heidelberg (2005)
Droste, M., Vogler, H.: Weighted tree automata and weighted logics (submitted, 2005)
Ebinger, W., Muscholl, A.: Logical definability on infinite traces. Theoret. Comp. Sc. (154), 67–84 (1996)
C.C. Elgot. Decision problems of finite automata design and related arithmetics. Trans. Amer. Math. Soc., (98):21–52, 1961.
Golan, J.S.: Semirings and their Applications. Kluwer Academic Publishers, Dordrecht (1999)
Hebisch, U., Weinert, H.J.: Semirings: Algebraic Theory and Application. World Scientific, Singapore (1999)
Kuich, W., Salomaa, A.: Semirings, Automata, Languages. EATCS Monographs on Theoret. Comp. Sc, vol. 5. Springer, Heidelberg (1986)
Kuske, D.: Weighted asynchronous cellular automata. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol. 3884, pp. 684–695. Springer, Heidelberg (2006)
Kuske, D., Meinecke, I.: Branching automata with costs – a way of reflecting parallelism in costs. Theoret. Comp. Sc. 328, 53–75 (2004)
Mäurer, I.: Weighted picture automata and weighted logics. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol. 3884, pp. 313–324. Springer, Heidelberg (2006)
Mazurkiewicz, A.: Trace theory. In: Brauer, W., Reisig, W., Rozenberg, G. (eds.) APN 1986. LNCS, vol. 255, pp. 279–324. Springer, Heidelberg (1987)
Meinecke, I.: Weighted Branching Automata – Combining Concurrency and Weights. Dissertation, Technische Universität Dresden, Germany (December 2004)
Meinecke, I.: The Hadamard product of sequential-parallel series. J. of Automata, Languages and Combinatorics 10(2) (toappear, 2005)
Salomaa, A., Soittola, M.: Automata-Theoretic Aspects of Formal Power Series. In: Texts and Monographs in Computer Science, Springer, Heidelberg (1978)
Schützenberger, M.P.: On the definition of a family of automata. Information and Control 4, 245–270 (1961)
Thomas, W.: On logical definability of trace languages. In: Diekert, V. (ed.) Proceedings of a workshop of the ESPRIT BRA No 3166: Algebraic and Syntactic Methods in Computer Science (ASMICS) 1989, Technical University of Munich, pp. 172–182 (1990)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Meinecke, I. (2006). Weighted Logics for Traces. In: Grigoriev, D., Harrison, J., Hirsch, E.A. (eds) Computer Science – Theory and Applications. CSR 2006. Lecture Notes in Computer Science, vol 3967. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11753728_25
Download citation
DOI: https://doi.org/10.1007/11753728_25
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-34166-6
Online ISBN: 978-3-540-34168-0
eBook Packages: Computer ScienceComputer Science (R0)