Please use this identifier to cite or link to this item: https://doi.org/10.1007/978-3-642-33558-7_18
Title: Space-time tradeoffs for the regular constraint
Authors: Cheng, K.C.K.
Xia, W.
Yap, R.H.C. 
Issue Date: 2012
Source: Cheng, K.C.K.,Xia, W.,Yap, R.H.C. (2012). Space-time tradeoffs for the regular constraint. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 7514 LNCS : 223-237. ScholarBank@NUS Repository. https://doi.org/10.1007/978-3-642-33558-7_18
Abstract: Many global constraints can be described by a regular expression or a DFA. Originally, the regular constraint, uses a DFA to describe the constraint, however, it can also be used to express a table constraint. Thus, there are many representations for an equivalent constraint. In this paper, we investigate the effect of different representations on natural extensions of the regular constraint focusing on the space-time tradeoffs. We propose a variant of the regular constraint, nfac(X), where X can be an NFA, DFA or MDD. Our nfac algorithm enforces GAC directly on any of the input representations, thus, generalizing the mddc algorithm. We also give an algorithm to directly convert an NFA representation to an MDD for nfac(MDD) or mddc. Our experiments show that the NFA representation not only saves space but also time. When the ratio of the NFA over the MDD or DFA size is small enough, nfac(NFA) is faster. When the size ratio is larger, nfac(NFA) still saves space and is a bit slower. In some problems, the initialization cost of MDD or DFA can also be a significant overhead, unlike NFA which has low initialization cost. We also show that the effect of the early-cutoff optimization is significant in all the representations. © 2012 Springer-Verlag.
Source Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
URI: http://scholarbank.nus.edu.sg/handle/10635/41539
ISBN: 9783642335570
ISSN: 03029743
DOI: 10.1007/978-3-642-33558-7_18
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

84
checked on Dec 9, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.