Please use this identifier to cite or link to this item:
|Title:||Space-time tradeoffs for the regular constraint||Authors:||Cheng, K.C.K.
|Issue Date:||2012||Citation:||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.
checked on Feb 19, 2020
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.