Logical definability on infinite traces | SpringerLink
Skip to main content
Springer Nature Link
Log in

Logical definability on infinite traces

  • Conference paper
  • First Online:
Automata, Languages and Programming (ICALP 1993)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 700))

Included in the following conference series:

  • 141 Accesses

Abstract

The main results of the present paper are the equivalence of monadic second order logic and recognizability for real trace languages, and that first order definable, star-free, and aperiodic real trace languages form the same class of languages. This generalizes results on infinite words [Tho90a, for an overview] and on finite traces [Tho90b, GRS91] to infinite traces. It closes the last gap in the different characterizations of recognizable infinitary trace languages.

This research has been supported by the EBRA working group No. 6317 ASMICS2.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. A. Arnold. A syntactic congruence for rational Ω-languages. Theoretical Computer Science, 39:333–335, 1985.

    Google Scholar 

  2. J.R. Büchi. On a decision method in restricted second order arithmetic. In E. Nagel et al., editor, Proc. Internat. Congr. on Logic, Methodology and Philosophy of Science, pages 1–11. Stanford Univ. Press, Stanford, CA, 1960.

    Google Scholar 

  3. V. Diekert and W. Ebinger, editors. Infinite Traces. Proceedings of a workshop of the ESPRIT Basic Research Action No 3166: Algebraic and Syntactic Methods in Computer Science (ASMICS), Tübingen, Germany, 1992, number 4/92. Universität Stuttgart, Fakultät Informatik, 1992.

    Google Scholar 

  4. V. Diekert. On the concatenation of infinite traces. In Choffrut C. et al., editors, Proc. 8th STACS, Hamburg 1991, LNCS 480, pages 105–117. Springer, 1991.

    Google Scholar 

  5. V. Diekert and A. Muscholl. Deterministic asynchronous automata for infinite traces. In P. Enjalbert, A. Finkel, and K. W. Wagner, editors, Proc. 10th STACS, Würzburg 1993, LNCS 665, pages 617–628. Springer, 1993.

    Google Scholar 

  6. W. Ebinger. On logical definability of Ω-trace languages. In Volker Diekert and Werner Ebinger, editors, Proceedings ASMICS Workshop Infinite Traces, Tübingen, Bericht 4/92, pages 106–122. Universität Stuttgart, Fakultät Informatik, 1992.

    Google Scholar 

  7. P. Gastin. Recognizable and rational trace languages of finite and infinite traces. In Choffrut C. et al., editors, Proc. 8th STACS, Hamburg 1991, LNCS 480, pages 89–104. Springer, 1991.

    Google Scholar 

  8. P. Gastin and A. Petit. Asynchronous automata for infinite traces. In W. Kuich, editor, Proc. 19th ICALP, Vienna (Austria) 1992, LNCS 623, pages 583–594. Springer, 1992.

    Google Scholar 

  9. P. Gastin, A. Petit, and W. Zielonka. A Kleene theorem for infinite trace languages. In J. Leach Albert et al., editors, Proc. 18th ICALP, Madrid (Spain) 1991, LNCS 510, pages 254–266. Springer, 1991.

    Google Scholar 

  10. G. Guaiana, A. Restivo, and S. Salemi. On aperiodic trace languages. In Choffrut C. et al., editors, Proc. 8th STACS, Hamburg 1991, LNCS 480, pages 76–88. Springer, 1991.

    Google Scholar 

  11. Y. Métivier. Une condition suffisante de reconnaissabilité dans un monoÏde partiellement commutatif. R.A.I.R.O. — Informatique Théorique et Applications, 20:121–127, 1986.

    Google Scholar 

  12. E. Ochmanski. Regular behaviour of concurrent systems. Bulletin of the European Association for Theoretical Computer Science (EATCS), 27:56–67, Oct 1985.

    Google Scholar 

  13. D. Perrin. Words over a partially commutative alphabet. Report no. 84–59, LITP Université de Paris VII, 1984. Also appeared in A. Apostolico, editor, Combinatorial Algorithms on Words, Springer NATO-ASI Series, Vol. F12, p.329–340, 1986.

    Google Scholar 

  14. D. Perrin. Recent results on automata and infinite words. In M. P. Chytil and V. Koubek, editors, Proc. 11th MFCS, Praha (CSFR) 1984, LNCS 176, pages 134–148. Springer, 1984.

    Google Scholar 

  15. D. Perrin and J.-E. Pin. First-order logic and star-free sets. Journal of Computer and System Sciences, 32:393–406, 1986.

    Google Scholar 

  16. M. P. Schützenberger. On finite monoids having only trivial subgroups. Information and Control, 8:190–194, 1965.

    Google Scholar 

  17. W. Thomas. Automata on infinite objects. In Jan van Leeuwen, editor, Handbook of Theoretical Computer Science, chapter 4, pages 133–191. Elsevier Science Publishers B. V., 1990.

    Google Scholar 

  18. W. Thomas. On logical definability of trace languages. In V. Diekert, editor, Proceedings of a workshop of the ESPRIT Basic Research Action No 3166: Algebraic and Syntactic Methods in Computer Science (ASMICS), Kochel am See, Bavaria, FRG (1989), Report TUM-I9002, Technical University of Munich, pages 172–182, 1990.

    Google Scholar 

  19. W. Thomas and W. Zielonka. Logical definability of trace languages. unpublished manuscript, 1991.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institut für Informatik, Universität Stuttgart, Breitwiesenstr. 20-22, D 70565, Stuttgart

    Werner Ebinger & Anca Muscholl

Authors
  1. Werner Ebinger
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Anca Muscholl
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Andrzej Lingas Rolf Karlsson Svante Carlsson

Rights and permissions

Reprints and permissions

Copyright information

© 1993 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Ebinger, W., Muscholl, A. (1993). Logical definability on infinite traces. In: Lingas, A., Karlsson, R., Carlsson, S. (eds) Automata, Languages and Programming. ICALP 1993. Lecture Notes in Computer Science, vol 700. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-56939-1_84

Download citation

  • DOI: https://doi.org/10.1007/3-540-56939-1_84

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-56939-8

  • Online ISBN: 978-3-540-47826-3

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation