Entry VanderZanden:1996:IAS from toplas.bib

Last update: Tue May 1 02:05:46 MDT 2012                Valid HTML 3.2!

Index sections

Top | Symbols | 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{VanderZanden:1996:IAS,
  author =       "Brad {Vander Zanden}",
  title =        "An incremental algorithm for satisfying hierarchies of
                 multiway dataflow constraints",
  journal =      j-TOPLAS,
  volume =       "18",
  number =       "1",
  pages =        "30--72",
  month =        jan,
  year =         "1996",
  CODEN =        "ATPSDT",
  ISSN =         "0164-0925 (print), 1558-4593 (electronic)",
  ISSN-L =       "0164-0925",
  bibdate =      "Tue Aug 13 11:46:35 MDT 1996",
  bibsource =    "http://www.acm.org/pubs/toc/;
                 http://www.math.utah.edu/pub/tex/bib/toplas.bib",
  note =         "See corrigendum \cite{VanderZanden:1996:CIA}.",
  URL =          "http://www.acm.org/pubs/toc/Abstracts/0164-0925/225543.html",
  abstract =     "One-way dataflow constraints have gained popularity in
                 many types of interactive systems because of their
                 simplicity, efficiency, and manageability. Although it
                 is widely acknowledged that multiway dataflow
                 constraint could make it easier to specify certain
                 relationships in these applications, concerns about
                 their predictability and efficiency have impeded their
                 acceptance. Constraint hierarchies have been developed
                 to address the predictability problem, and incremental
                 algorithms have been developed to address the
                 efficiency problem. However, existing incremental
                 algorithms for satisfying constraint hierarchies
                 encounter two difficulties: (1) they are incapable of
                 guaranteeing an acyclic solution if a constraint
                 hierarchy has one or more cyclic solutions and (2) they
                 require worst-case exponential time to satisfy systems
                 of multioutput constraints. This article surmounts
                 these difficulties by presenting an incremental
                 algorithm called QuickPlan that satisfies in worst-case
                 $O(N^2)$ time any hierarchy of multiway, multioutput
                 dataflow constraint that has at least one acyclic
                 solution, where $N$ is the number of constraints. With
                 benchmarks and real problems that can be solved
                 efficiently using existing algorithms, its performance
                 is competitive or superior. With benchmarks and real
                 problems that cannot be solved using existing
                 algorithms or that cannot be solved efficiently,
                 QuickPlan finds solutions and does so efficiently,
                 typically in $O(N)$ time or less. QuickPlan is based on
                 the strategy of propagation of degrees of freedom. The
                 only restriction it imposes is that every constraint
                 method must use all of the variables in the constraint
                 as either an input or an output variable. This
                 requirement is met in every constraint-based,
                 interactive application that we have developed or
                 seen.",
  acknowledgement = ack-nhfb,
  fjournal =     "ACM Transactions on Programming Languages and
                 Systems",
  keywords =     "algorithms; design; languages",
  subject =      "{\bf D.2.2}: Software, SOFTWARE ENGINEERING, Tools and
                 Techniques, User interfaces. {\bf D.2.6}: Software,
                 SOFTWARE ENGINEERING, Programming Environments. {\bf
                 I.1.3}: Computing Methodologies, ALGEBRAIC
                 MANIPULATION, Languages and Systems, Evaluation
                 strategies. {\bf I.1.2}: Computing Methodologies,
                 ALGEBRAIC MANIPULATION, Algorithms, Nonalgebraic
                 algorithms.",
}

Related entries