On the High Complexity of Petri Nets [Formula: see text]-Languages

We prove that [Formula: see text]-languages of (non-deterministic) Petri nets and [Formula: see text]-languages of (non-deterministic) Turing machines have the same topological complexity: the Borel and Wadge hierarchies of the class of [Formula: see text]-languages of (non-deterministic) Petri nets...

Descripción completa

Detalles Bibliográficos
Autor principal: Finkel, Olivier
Formato: Online Artículo Texto
Lenguaje:English
Publicado: 2020
Materias:
Article
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7324243/
http://dx.doi.org/10.1007/978-3-030-51831-8_4
_version_ 1783551900366405632
author Finkel, Olivier
author_facet Finkel, Olivier
author_sort Finkel, Olivier
collection PubMed
description We prove that [Formula: see text]-languages of (non-deterministic) Petri nets and [Formula: see text]-languages of (non-deterministic) Turing machines have the same topological complexity: the Borel and Wadge hierarchies of the class of [Formula: see text]-languages of (non-deterministic) Petri nets are equal to the Borel and Wadge hierarchies of the class of [Formula: see text]-languages of (non-deterministic) Turing machines. We also show that it is highly undecidable to determine the topological complexity of a Petri net [Formula: see text]-language. Moreover, we infer from the proofs of the above results that the equivalence and the inclusion problems for [Formula: see text]-languages of Petri nets are [Formula: see text]-complete, hence also highly undecidable.
format Online
Article
Text
id pubmed-7324243
institution National Center for Biotechnology Information
language English
publishDate 2020
record_format MEDLINE/PubMed
spelling pubmed-73242432020-06-30 On the High Complexity of Petri Nets [Formula: see text]-Languages Finkel, Olivier Application and Theory of Petri Nets and Concurrency Article We prove that [Formula: see text]-languages of (non-deterministic) Petri nets and [Formula: see text]-languages of (non-deterministic) Turing machines have the same topological complexity: the Borel and Wadge hierarchies of the class of [Formula: see text]-languages of (non-deterministic) Petri nets are equal to the Borel and Wadge hierarchies of the class of [Formula: see text]-languages of (non-deterministic) Turing machines. We also show that it is highly undecidable to determine the topological complexity of a Petri net [Formula: see text]-language. Moreover, we infer from the proofs of the above results that the equivalence and the inclusion problems for [Formula: see text]-languages of Petri nets are [Formula: see text]-complete, hence also highly undecidable. 2020-06-02 /pmc/articles/PMC7324243/ http://dx.doi.org/10.1007/978-3-030-51831-8_4 Text en © 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.
spellingShingle Article
Finkel, Olivier
On the High Complexity of Petri Nets [Formula: see text]-Languages
title On the High Complexity of Petri Nets [Formula: see text]-Languages
title_full On the High Complexity of Petri Nets [Formula: see text]-Languages
title_fullStr On the High Complexity of Petri Nets [Formula: see text]-Languages
title_full_unstemmed On the High Complexity of Petri Nets [Formula: see text]-Languages
title_short On the High Complexity of Petri Nets [Formula: see text]-Languages
title_sort on the high complexity of petri nets [formula: see text]-languages
topic Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7324243/
http://dx.doi.org/10.1007/978-3-030-51831-8_4
work_keys_str_mv AT finkelolivier onthehighcomplexityofpetrinetsformulaseetextlanguages

Ejemplares similares