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 Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

The workflow satisfiability problem (wsp) is a problem of practical interest that arises whenever tasks need to be performed by authorized users, subject to constraints defined by business rules. We are required to decide whether there exists a plan--an assignment of tasks to authorized users--such that all constraints are satisfied. The wsp is, in fact, the conservative constraint satisfaction problem (i.e., for each variable, here called task, we have a unary authorization constraint) and is, thus, $$\\mathsf {NP}$$NP-complete. It was observed by Wang and Li (ACM Trans Inf Syst Secur 13(4):40, 2010) that the number $$k$$k of tasks is often quite small and so can be used as a parameter, and several subsequent works have studied the parameterized complexity of wsp regarding parameter $$k$$k. We take a more detailed look at the kernelization complexity of wsp( $$\\varGamma $$Γ) when $$\\varGamma $$Γ denotes a finite or infinite set of allowed constraints. Our main result is a dichotomy for the case that all constraints in $$\\varGamma $$Γ are regular: (1) We are able to reduce the number $$n$$n of users to $$n'\\le k$$nź≤k. This entails a kernelization to size poly$$(k)$$(k) for finite $$\\varGamma $$Γ, and, under mild technical conditions, to size poly$$(k+m)$$(k+m) for infinite $$\\varGamma $$Γ, where $$m$$m denotes the number of constraints. (2) Already wsp( $$R$$R) for some $$R\\in \\varGamma $$RźΓ allows no polynomial kernelization in $$k+m$$k+m unless the polynomial hierarchy collapses.

Polynomial Kernels and User Reductions for the Workflow Satisfiability Problem