Document Open Access Logo

Boolean Algebras from Trace Automata

Author Alexandre Mansard

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2019.48.pdf
  • Filesize: 0.67 MB
  • 15 pages

Document Identifiers

Author Details

Alexandre Mansard
  • LIM, University of La Réunion, France

Cite As Get BibTex

Alexandre Mansard. Boolean Algebras from Trace Automata. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 48:1-48:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.FSTTCS.2019.48

Abstract

We consider trace automata. Their vertices are Mazurkiewicz traces and they accept finite words. Considering the length of a trace as the length of its Foata normal form, we define the operations of level-length synchronization and of superposition of trace automata. We show that if a family F of trace automata is closed under these operations, then for any deterministic automaton H in F, the word languages accepted by the deterministic automata of F that are length-reducible to H form a Boolean algebra. We show that the family of trace suffix automata with level-regular contexts and the subfamily of vector addition systems satisfy these closure properties. In particular, this yields various Boolean algebras of word languages accepted by deterministic vector addition systems.

Subject Classification

ACM Subject Classification
  • Theory of computation → Formal languages and automata theory
Keywords
  • Boolean algebras
  • traces
  • automata
  • synchronization
  • pushdown automata
  • vector addition systems

Metrics

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

References

  1. R. Alur and P. Madhusudan. Visibly pushdown languages. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004, pages 202-211, 2004. URL: https://doi.org/10.1145/1007352.1007390.
  2. D. Caucal. On the Regular Structure of Prefix Rewriting. Theor. Comput. Sci., 106(1):61-86, 1992. URL: https://doi.org/10.1016/0304-3975(92)90278-N.
  3. D. Caucal. On Infinite Transition Graphs Having a Decidable Monadic Theory. In Automata, Languages and Programming, 23rd International Colloquium, ICALP96, Paderborn, Germany, 8-12 July 1996, Proceedings, pages 194-205, 1996. URL: https://doi.org/10.1007/3-540-61440-0_128.
  4. D. Caucal. On the transition graphs of turing machines. Theor. Comput. Sci., 296(2):195-223, 2003. URL: https://doi.org/10.1016/S0304-3975(02)00655-2.
  5. D. Caucal. Boolean algebras of unambiguous context-free languages. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2008, December 9-11, 2008, Bangalore, India, pages 83-94, 2008. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2008.1743.
  6. D. Caucal and C. Rispal. Recognizability for Automata. In Developments in Language Theory - 22nd International Conference, DLT 2018, Tokyo, Japan, September 10-14, 2018, Proceedings, pages 206-218, 2018. URL: https://doi.org/10.1007/978-3-319-98654-8_17.
  7. D. Caucal and C. Rispal. Boolean Algebras by Length Recognizability. In Tiziana Margaria, Susanne Graf, and Kim G. Larsen, editors, Models, Mindsets, Meta: The What, the How, and the Why Not? Essays Dedicated to Bernhard Steffen on the Occasion of His 60th Birthday, pages 169-185. Springer International Publishing, Cham, 2019. URL: https://doi.org/10.1007/978-3-030-22348-9_11.
  8. N. Chomsky. Three models for the description of languages. IRE Transactions on Information Theory, 2(3):113-124, September 1956. URL: https://doi.org/10.1109/TIT.1956.1056813.
  9. S. Crespi-reghizzi and D. Mandrioli. Petri nets and szilard languages. Information and Control, 33(2):177-192, 1977. URL: https://doi.org/10.1016/S0019-9958(77)90558-7.
  10. V. Diekert and G. Rozenberg. The Book of Traces. WORLD SCIENTIFIC, 1995. URL: https://doi.org/10.1142/2563.
  11. S. Eilenberg. Automata, Languages, and Machines. Academic Press, Inc., Orlando, FL, USA, 1974. Google Scholar
  12. M. Hack. Decidability questions for Petri nets. PhD thesis, MIT, Dept. Electrical Engineering, Cambridge, Mass., USA, 1975. Google Scholar
  13. B. Hodgson. On Direct Products of Automaton Decidable Theories. Theor. Comput. Sci., 19:331-335, 1982. URL: https://doi.org/10.1016/0304-3975(82)90042-1.
  14. J. Leroux, V. Penelle, and G. Sutre. On the Context-Freeness Problem for Vector Addition Systems. In 28th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2013, New Orleans, LA, USA, June 25-28, 2013, pages 43-52, 2013. URL: https://doi.org/10.1109/LICS.2013.9.
  15. C. Löding. Model-Checking Infinite Systems Generated by Ground Tree Rewriting. In Foundations of Software Science and Computation Structures, 5th International Conference, FOSSACS 2002. Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2002 Grenoble, France, April 8-12, 2002, Proceedings, pages 280-294, 2002. URL: https://doi.org/10.1007/3-540-45931-6_20.
  16. A. Mansard. Unfolding of Finite Concurrent Automata. In Proceedings 11th Interaction and Concurrency Experience, ICE 2018, Madrid, Spain, June 20-21, 2018., pages 68-84, 2018. URL: https://doi.org/10.4204/EPTCS.279.8.
  17. K. Mehlhorn. Pebbling Mountain Ranges and its Application of DCFL-Recognition. In Automata, Languages and Programming, 7th Colloquium, Noordweijkerhout, The Netherlands, July 14-18, 1980, Proceedings, pages 422-435, 1980. URL: https://doi.org/10.1007/3-540-10003-2_89.
  18. D. Nowotka and J. Srba. Height-Deterministic Pushdown Automata. In Mathematical Foundations of Computer Science 2007, 32nd International Symposium, MFCS 2007, Ceský Krumlov, Czech Republic, August 26-31, 2007, Proceedings, pages 125-134, 2007. URL: https://doi.org/10.1007/978-3-540-74456-6_13.
  19. J. L. Peterson. Petri Net Theory and the Modeling of Systems. Prentice Hall PTR, Upper Saddle River, NJ, USA, 1981. Google Scholar
  20. C. Rispal. The synchronized graphs trace the context-sensitive languages. Electr. Notes Theor. Comput. Sci., 68(6):55-70, 2002. URL: https://doi.org/10.1016/S1571-0661(04)80533-4.
  21. S. R. Schwer. The context-freeness of the languages associated with vector addition systems is decidable. Theoretical Computer Science, 98(2):199-247, 1992. URL: https://doi.org/10.1016/0304-3975(92)90002-W.
  22. R. Valk and G. Vidal-Naquet. Petri nets and regular languages. Journal of Computer and System Sciences, 23(3):299-325, 1981. URL: https://doi.org/10.1016/0022-0000(81)90067-2.
  23. G. Winskel and M. Nielsen. Models for Concurrency. In S. Abramsky, Dov M. Gabbay, and T. S. E. Maibaum, editors, Handbook of Logic in Computer Science (Vol. 4), pages 1-148. Oxford University Press, Inc., New York, NY, USA, 1995. URL: http://dl.acm.org/citation.cfm?id=218623.218630.
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