Blog
About

0
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: not found

      On the High Complexity of Petri Nets $$ \omega $$ -Languages

      Read this article at

      ScienceOpenPublisherPMC
      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          We prove that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\omega $$\end{document} -languages of (non-deterministic) Petri nets and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\omega $$\end{document} -languages of (non-deterministic) Turing machines have the same topological complexity: the Borel and Wadge hierarchies of the class of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\omega $$\end{document} -languages of (non-deterministic) Petri nets are equal to the Borel and Wadge hierarchies of the class of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\omega $$\end{document} -languages of (non-deterministic) Turing machines. We also show that it is highly undecidable to determine the topological complexity of a Petri net \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\omega $$\end{document} -language. Moreover, we infer from the proofs of the above results that the equivalence and the inclusion problems for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\omega $$\end{document} -languages of Petri nets are \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varPi _2^1$$\end{document} -complete, hence also highly undecidable.

          Related collections

          Author and article information

          Contributors
          janicki@mcmaster.ca
          N.Sidorova@TUE.nl
          chatain@lsv.fr
          Olivier.Finkel@math.univ-paris-diderot.fr
          Journal
          978-3-030-51831-8
          10.1007/978-3-030-51831-8
          Application and Theory of Petri Nets and Concurrency
          Application and Theory of Petri Nets and Concurrency
          41st International Conference, PETRI NETS 2020, Paris, France, June 24–25, 2020, Proceedings
          978-3-030-51830-1
          978-3-030-51831-8
          02 June 2020
          : 12152
          : 69-88
          Affiliations
          [8 ]GRID grid.25073.33, ISNI 0000 0004 1936 8227, McMaster University, ; Hamilton, ON Canada
          [9 ]GRID grid.6852.9, ISNI 0000 0004 0398 8763, Eindhoven University of Technology, ; Eindhoven, The Netherlands
          [10 ]GRID grid.464035.0, ISNI 0000 0001 2063 800X, LSV, CNRS & ENS Paris-Saclay, ; Cachan, France
          GRID grid.462500.5, ISNI 0000 0001 1011 2151, Institut de Mathématiques de Jussieu - Paris Rive Gauche CNRS et Université Paris 7, ; Paris, France
          Article
          4
          10.1007/978-3-030-51831-8_4
          7324243
          © Springer Nature Switzerland AG 2020

          This article is made available via the PMC Open Access Subset for unrestricted research re-use and secondary analysis in any form or by any means with acknowledgement of the original source. These permissions are granted for the duration of the World Health Organization (WHO) declaration of COVID-19 as a global pandemic.

          Categories
          Article
          Custom metadata
          © Springer Nature Switzerland AG 2020

          Comments

          Comment on this article