English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We prove that $\omega$-languages of (non-deterministic) Petri nets and$\omega$-languages of (non-deterministic) Turing machines have the sametopological complexity: the Borel and Wadge hierarchies of the class of$\omega$-languages of (non-deterministic) Petri nets are equal to the Borel andWadge hierarchies of the class of $\omega$-languages of (non-deterministic)Turing machines. We also show that it is highly undecidable to determine thetopological complexity of a Petri net $\omega$-language. Moreover, we inferfrom the proofs of the above results that the equivalence and the inclusionproblems for $\omega$-languages of Petri nets are $\Pi_2^1$-complete, hencealso highly undecidable.  Additionally, we show that the situation is quite the opposite whenconsidering unambiguous Petri nets, which have the semantic property that atmost one accepting run exists on every input. We provide a procedure ofdeterminising them into deterministic Muller counter machines with countercopying. As a consequence, we entail that the $\omega$-languages recognisableby unambiguous Petri nets are $\Delta^0_3$ sets.

On the expressive power of non-deterministic and unambiguous Petri nets over infinite words