Document Open Access Logo

Wreath/Cascade Products and Related Decomposition Results for the Concurrent Setting of Mazurkiewicz Traces

Authors Bharat Adsul, Paul Gastin , Saptarshi Sarkar, Pascal Weil

PDF
Thumbnail PDF

File

LIPIcs.CONCUR.2020.19.pdf
  • Filesize: 0.5 MB
  • 17 pages

Document Identifiers

Author Details

Bharat Adsul
  • IIT Bombay, India
Paul Gastin
  • LSV, ENS Paris-Saclay, CNRS, Université Paris-Saclay, France
Saptarshi Sarkar
  • IIT Bombay, India
Pascal Weil
  • Université Bordeaux, LaBRI, CNRS UMR 5800, Talence, France
  • CNRS, ReLaX, IRL 2000, Siruseri, India

Funding

  • Gastin, Paul: Supported by IRL ReLaX.
  • Weil, Pascal: Partially supported by the DeLTA project (ANR-16-CE40- 0007)

Cite As Get BibTex

Bharat Adsul, Paul Gastin, Saptarshi Sarkar, and Pascal Weil. Wreath/Cascade Products and Related Decomposition Results for the Concurrent Setting of Mazurkiewicz Traces. In 31st International Conference on Concurrency Theory (CONCUR 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 171, pp. 19:1-19:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.CONCUR.2020.19

Abstract

We develop a new algebraic framework to reason about languages of Mazurkiewicz traces. This framework supports true concurrency and provides a non-trivial generalization of the wreath product operation to the trace setting. A novel local wreath product principle has been established. The new framework is crucially used to propose a decomposition result for recognizable trace languages, which is an analogue of the Krohn-Rhodes theorem. We prove this decomposition result in the special case of acyclic architectures and apply it to extend Kamp’s theorem to this setting. We also introduce and analyze distributed automata-theoretic operations called local and global cascade products. Finally, we show that aperiodic trace languages can be characterized using global cascade products of localized and distributed two-state reset automata.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed computing models
  • Theory of computation → Algebraic language theory
Keywords
  • Mazurkiewicz traces
  • asynchronous automata
  • wreath product
  • cascade product
  • Krohn Rhodes decomposition theorem
  • local temporal logic over traces

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Bharat Adsul, Paul Gastin, Saptarshi Sarkar, and Pascal Weil. Wreath/cascade products and related decomposition results for the concurrent setting of mazurkiewicz traces (extended version), 2020. URL: http://arxiv.org/abs/2007.07940.
  2. Bharat Adsul and Milind A. Sohoni. Asynchronous automata-theoretic characterization of aperiodic trace languages. In FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science, 24th International Conference, Chennai, India, December 16-18, 2004, Proceedings, pages 84-96, 2004. URL: https://doi.org/10.1007/978-3-540-30538-5_8.
  3. Joëlle Cohen, Dominique Perrin, and Jean-Eric Pin. On the expressive power of temporal logic. Journal of Computer and System Sciences, 46(3):271-294, 1993. Google Scholar
  4. Volker Diekert and Paul Gastin. Pure future local temporal logics are expressively complete for mazurkiewicz traces. Inf. Comput., 204(11):1597-1619, 2006. URL: https://doi.org/10.1016/j.ic.2006.07.002.
  5. Volker Diekert, Manfred Kufleitner, and Benjamin Steinberg. The Krohn-Rhodes theorem and local divisors. Fundam. Inform., 116(1-4):65-77, 2012. URL: https://doi.org/10.3233/FI-2012-669.
  6. Volker Diekert and Grzegorz Rozenberg. The Book of Traces. World Scientific Publishing Co., Inc., USA, 1995. Google Scholar
  7. Samuel Eilenberg. Automata, Languages and Machines, volume B. Academic Press, 1976. Google Scholar
  8. Giovanna Guaiana, Raphaël Meyer, Antoine Petit, and Pascal Weil. An extension of the wreath product principle for finite Mazurkiewicz traces. Information Processing Letters, 67(6):277-282, 1998. URL: https://doi.org/10.1016/S0020-0190(98)00123-9.
  9. Hans Kamp. Tense Logic and the Theory of Linear Order. PhD thesis, UCLA, 1968. Google Scholar
  10. Siddharth Krishna and Anca Muscholl. A quadratic construction for Zielonka automata with acyclic communication structure. Theor. Comput. Sci., 503(C):109-114, September 2013. Google Scholar
  11. Kenneth Krohn and John Rhodes. Algebraic theory of machines I. prime decomposition theorem for finite semigroups and machines. Transactions of The American Mathematical Society, 116, April 1965. URL: https://doi.org/10.2307/1994127.
  12. Antoni Mazurkiewicz. Concurrent program schemes and their interpretations. DAIMI Report Series, 6(78), 1977. URL: https://doi.org/10.7146/dpb.v6i78.7691.
  13. Robert McNaughton and Seymour A. Papert. Counter-Free Automata. M.I.T. Research Monograph Nr 65. The MIT Press, 1971. Google Scholar
  14. Albert R. Meyer. A note on star-free events. J. ACM, 16(2):220-225, April 1969. URL: https://doi.org/10.1145/321510.321513.
  15. Madhavan Mukund. Automata on distributed alphabets. In Deepak D'Souza and Priti Shankar, editors, Modern applications of automata theory, pages 257-288. World Scientific, 2012. Google Scholar
  16. Madhavan Mukund and Milind A. Sohoni. Keeping track of the latest gossip in a distributed system. Distributed Computing, 10(3):137-148, 1997. URL: https://doi.org/10.1007/s004460050031.
  17. Dominique Perrin and Jean-Eric Pin. Infinite words - automata, semigroups, logic and games, volume 141 of Pure and applied mathematics series. Elsevier Morgan Kaufmann, 2004. Google Scholar
  18. Jean-Éric Pin. Mathematical foundations of automata theory, 2019. URL: https://www.irif.fr/~jep/PDF/MPRI/MPRI.pdf.
  19. M.P. Schützenberger. On finite monoids having only trivial subgroups. Information and Control, 8(2):190-194, 1965. URL: https://doi.org/10.1016/S0019-9958(65)90108-7.
  20. Howard Straubing. Finite automata, formal logic, and circuit complexity. Birkhaüser Verlag, Basel, Switzerland, 1994. Google Scholar
  21. Wieslaw Zielonka. Notes on finite asynchronous automata. RAIRO-Theoretical Informatics and Applications, 21(2):99-135, 1987. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact