About: PSPACE-Completeness of the Soundness Problem of Safe Asymmetric-Choice Workflow Nets

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: PSPACE-Completeness of the Soundness Problem of Safe Asymmetric-Choice Workflow Nets Goto Sponge NotDistinct Permalink

An Entity of Type : schema:ScholarlyArticle, within Data Space : wasabi.inria.fr associated with source document(s)

Attributes	Values
type	Academic Article research paper schema:ScholarlyArticle
isDefinedBy	Covid-on-the-Web dataset
has title	PSPACE-Completeness of the Soundness Problem of Safe Asymmetric-Choice Workflow Nets
Creator	Liu, Guanjun
topic	covid:84ffee51edef2a634fc3a61cf9bd4ef50f3766c7#this
Source	PMC
abstract	Asymmetric-choice workflow nets (ACWF-nets) are an important subclass of workflow nets (WF-nets) that can model and analyse business processes of many systems, especially the interactions among multiple processes. Soundness of WF-nets is a basic property guaranteeing that these business processes are deadlock-/livelock-free and each designed action has a potential chance to be executed. Aalst et al. proved that the soundness problem is decidable for general WF-nets and proposed a polynomial algorithm to check the soundness for free-choice workflow nets (FCWF-nets) that are a special subclass of ACWF-nets. Tiplea et al. proved that for safe acyclic WF-nets the soundness problem is co-NP-complete, and we proved that for safe WF-nets the soundness problem is PSPACE-complete. We also proved that for safe ACWF-nets the soundness problem is co-NP-hard, but this paper sharpens this result by proving that for safe ACWF-nets this problem is PSPACE-complete actually. This paper provides a polynomial-time reduction from the acceptance problem of linear bounded automata (LBA) to the soundness problem of safe ACWF-nets. The kernel of the reduction is to guarantee that an LBA with an input string does not accept the input string if and only if the constructed safe ACWF-net is sound. Based on our reduction, we easily prove that the liveness problem of safe AC-nets is also PSPACE-complete, but the best result on this problem was NP-hardness provided by Ohta and Tsuji. Therefore, we also strengthen their result.
has issue date	2020-06-02(xsd:dateTime)
bibo:doi	10.1007/978-3-030-51831-8_10
has license	no-cc
sha1sum (hex)	84ffee51edef2a634fc3a61cf9bd4ef50f3766c7
schema:url	https://doi.org/10.1007/978-3-030-51831-8_10
resource representing a document's title	PSPACE-Completeness of the Soundness Problem of Safe Asymmetric-Choice Workflow Nets
has PubMed Central identifier	PMC7324217
schema:publication	Application and Theory of Petri Nets and Concurrency
resource representing a document's body	covid:84ffee51edef2a634fc3a61cf9bd4ef50f3766c7#body_text
is http://vocab.deri.ie/void#inDataset of	https://covidontheweb.inria.fr:4443/about/id/http/ns.inria.fr/covid19/84ffee51edef2a634fc3a61cf9bd4ef50f3766c7
is schema:about of	named entity 'Nets' named entity 'DOES NOT' named entity 'PROPOSED' named entity 'ACYCLIC' named entity 'GENERAL' named entity 'THEIR' named entity 'LBA' named entity 'BOUNDED' named entity 'RESULT' named entity 'ACCEPTANCE' named entity 'algorithm' named entity 'special' named entity 'nets' named entity 'multiple' named entity 'Soundness' named entity 'acceptance' named entity 'decidable' named entity 'co-NP-complete' named entity 'multiple processes' named entity 'ACWF' named entity 'kernel' named entity 'Aalst' named entity 'LBA' named entity 'polynomial algorithm' named entity 'polynomial-time reduction' named entity 'liveness' named entity 'PSPACE-complete' named entity 'Aalst' named entity 'liveness' named entity 'reduction' named entity 'ACWF' named entity 'LBA' named entity 'algorithm' named entity 'computing' named entity 'Petri nets' named entity 'LBA' named entity 'ACWF' named entity 'self-loop' named entity 'LBA' named entity 'PSPACE' named entity 'LBA' named entity 'Aalst' named entity 'LBA' named entity '1, 2' named entity 'LBA' named entity 'LBA' named entity 'LBA' named entity 'LBA' named entity 'reachability problem' named entity 'LBA' named entity 'ACWF' named entity 'LBA' named entity 'PSPACE-complete' named entity 'LBA' named entity 'Petri net' named entity 'LBA' named entity 'Petri nets' named entity 'Petri nets' named entity 'ordered set' named entity 'ACWF' named entity 'Petri nets' named entity 'LBA' named entity 'LBA' named entity 'directed path' named entity 'ACWF' named entity 'liveness' named entity 'PSPACE-complete' named entity 'LBA' named entity 'LBA' named entity 'short-circuit' named entity 'Petri nets' named entity 'computing' named entity 'LBA' named entity 'LBA' named entity 'PSPACE-complete' named entity 'LBA' named entity 'Turing machine' named entity 'PSPACE-complete' named entity 'business process management' named entity 'reachability' named entity 'LBA'

Faceted Search & Find service v1.13.91 as of Mar 24 2020

Alternative Linked Data Documents: Sponger | ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3229 as of Jul 10 2020, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (94 GB total memory)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software