Abstract
We characterize aperiodic distributed behaviours, modelled as Mazurkiewicz traces in terms of a very natural cascade product of the gossip automaton with a counter-free asynchronous automaton. The characterization strengthens the fundamental results of Schutzenberger and, McNaughton and Papert and implies that star-free, equivalently, first-order-definable trace languages admit counter-free asynchronous acceptors modulo the gossip automaton.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Adsul, B.: Complete Local Logics for Reasoning about Traces, Ph.D. Thesis, Indian Institute of Technology – Bombay, Mumbai, India (2004)
Arbib, M.A. (ed.): Algebraic Theory of Machines, Languages and Semigroups. Academic Press, New York (1968)
Droste, M., Kuske, D.: Languages and Logical Definability in Concurrency Monoids. In: Kleine Büning, H. (ed.) CSL 1995. LNCS, vol. 1092, pp. 233–251. Springer, Heidelberg (1996)
Diekert, V., Rozenberg, G. (eds.): The Book of Traces. World Scientific, Singapore (1995)
Ebinger, W., Muscholl, A.: Logical Definability on Infinite Traces. In: Lingas, A., Carlsson, S., Karlsson, R. (eds.) ICALP 1993. LNCS, vol. 700, pp. 335–346. Springer, Heidelberg (1993)
Guaiana, G., Restivo, A., Salemi, S.: Star-free Trace Languages. Theoretical Computer Science 97, 301–311 (1992)
Mazurkiewicz, A.: Concurrent Program Schemes and Their Interpretations, Report DAIMI-PB-78, Comp Sci Dept. Aarhus University, Denmark (1978)
McNaughton, R., Papert, S.: Counter-free Automata. MIT Press, Cambridge (1971)
Mukund, M., Sohoni, M.: Gossiping, Asynchronous Automata and Zielonka’s Theorem, Report TCS-94-2, Chennai Mathematical Institute. Chennai, India (1994)
Mukund, M., Sohoni, M.: Keeping Track of the Latest Gossip in a Distributed System. Distributed Computing 10(3), 137–148 (1997)
Schutzenberger, M.P.: On Finite Monoids Having Only Trivial Subgroups. Information and Control 48, 190–194 (1965)
Thomas, W.: Languages, Automata and Logic. In: Handbook of Formal Languages, vol. 3, pp. 389–456. Springer, New York (1997)
Zielonka, W.: Notes on Finite Asynchronous Automata. RAIRO Inform. Théor. Appl. 21, 99–135 (1987)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Adsul, B., Sohoni, M. (2004). Asynchronous Automata-Theoretic Characterization of Aperiodic Trace Languages. In: Lodaya, K., Mahajan, M. (eds) FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science. FSTTCS 2004. Lecture Notes in Computer Science, vol 3328. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30538-5_8
Download citation
DOI: https://doi.org/10.1007/978-3-540-30538-5_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-24058-7
Online ISBN: 978-3-540-30538-5
eBook Packages: Computer ScienceComputer Science (R0)