Entry Crampton:2013:PCK from tissec.bib

Last update: Sun Oct 15 02:58:48 MDT 2017                Valid HTML 3.2!

Index sections

Top | Symbols | Numbers | Math | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z

BibTeX entry

@Article{Crampton:2013:PCK,
  author =       "Jason Crampton and Gregory Gutin and Anders Yeo",
  title =        "On the Parameterized Complexity and Kernelization of
                 the Workflow Satisfiability Problem",
  journal =      j-TISSEC,
  volume =       "16",
  number =       "1",
  pages =        "4:1--4:??",
  month =        jun,
  year =         "2013",
  CODEN =        "ATISBQ",
  DOI =          "https://doi.org/10.1145/2487222.2487226",
  ISSN =         "1094-9224 (print), 1557-7406 (electronic)",
  ISSN-L =       "1094-9224",
  bibdate =      "Fri Jun 14 19:25:26 MDT 2013",
  bibsource =    "http://portal.acm.org/;
                 http://www.math.utah.edu/pub/tex/bib/tissec.bib",
  abstract =     "A workflow specification defines a set of steps and
                 the order in which these steps must be executed.
                 Security requirements may impose constraints on which
                 groups of users are permitted to perform subsets of
                 these steps. A workflow specification is said to be
                 satisfiable if there exists an assignment of users to
                 workflow steps that satisfies all the constraints. An
                 algorithm for determining whether such an assignment
                 exists is important, both as a static analysis tool for
                 workflow specifications and for the construction of
                 runtime reference monitors for workflow management
                 systems. Finding such an assignment is a hard problem
                 in general, but work by Wang and Li [2010] using the
                 theory of parameterized complexity suggests that
                 efficient algorithms exist under reasonable assumptions
                 about workflow specifications. In this article, we
                 improve the complexity bounds for the workflow
                 satisfiability problem. We also generalize and extend
                 the types of constraints that may be defined in a
                 workflow specification and prove that the
                 satisfiability problem remains fixed-parameter
                 tractable for such constraints. Finally, we consider
                 preprocessing for the problem and prove that in an
                 important special case, in polynomial time, we can
                 reduce the given input into an equivalent one where the
                 number of users is at most the number of steps. We also
                 show that no such reduction exists for two natural
                 extensions of this case, which bounds the number of
                 users by a polynomial in the number of steps, provided
                 a widely accepted complexity-theoretical assumption
                 holds.",
  acknowledgement = ack-nhfb,
  articleno =    "4",
  fjournal =     "ACM Transactions on Information and System Security",
  journal-URL =  "http://portal.acm.org/browse_dl.cfm?idx=J789",
}

Related entries