×

zbMATH — the first resource for mathematics

Deriving generic bounds for time-series constraints based on regular expressions characteristics. (English) Zbl 1396.90047
Summary: We introduce the concept of regular expression characteristics as a unified way to concisely express bounds on time-series constraints. This allows us not only to define time-series constraints in a compositional way, but also to deal with their combinatorial aspect in a compositional way, without developing ad-hoc bounds for each time-series constraint separately.
MSC:
90C10 Integer programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alur, R., D’Antoni, L., Deshmukh, J. V., Raghothaman, M., & Yuan, Y. (2013). Regular functions and cost register automata. In 28th annual ACM/IEEE symposium on logic in computer science, LICS 2013 (pp. 13-22). New Orleans: IEEE Computer Society. · Zbl 1366.68046
[2] Alur, R., Fisman, D., & Raghothaman, M. (2016). Regular programming for quantitative properties of data streams. In Thiemann, P (Ed.) Programming languages and systems - 25th European symposium on programming, ESOP 2016, held as part of the European joint conferences on theory and practice of software, ETAPS 2016, Eindhoven, The Netherlands, April 2-8, 2016, Proceedings. Lecture notes in computer science (Vol. 9632, pp. 15-40). Eindhoven: Springer. · Zbl 1335.68041
[3] Arafailova, E., Beldiceanu, N., Carlsson, M., Flener, P., Francisco Rodríguez, M.A., Pearson, J., & Simonis, H. (2016). Systematic derivation of bounds and glue constraints for time-series constraints. In Rueher, M. (Ed.) CP 2016. LNCS (Vol. 9892, pp. 13-29). Cham: Springer. · Zbl 1397.68161
[4] Arafailova, E., Beldiceanu, N., Douence, R., Carlsson, M., Flener, P., Rodríguez, M.A.F., Pearson, J., & Simonis, H. (2016). Global constraint catalog, volume ii, time-series constraints. CoRR 1609.08925. · Zbl 1341.68123
[5] Arafailova, E., Beldiceanu, N., Douence, R., Flener, P., Francisco Rodríguez, M.A., Pearson, J., & Simonis, H. (2016). Time-series constraints: improvements and application in CP and MIP contexts. In Quimper, C.G. (Ed.) CP-AI-OR 2016. LNCS (Vol. 9676, pp. 18-34). Cham: Springer. · Zbl 06598653
[6] Beldiceanu, N; Carlsson, M; Douence, R; Simonis, H, Using finite transducers for describing and synthesising structural time-series constraints, Constraints, 21, 22-40, (2016) · Zbl 1397.68161
[7] Beldiceanu, N., Carlsson, M., Flener, P., Francisco Rodríguez, M. A., & Pearson, J. (2014). Linking prefixes and suffixes for constraints encoded using automata with accumulators. In O’Sullivan, B (Ed.) CP 2014. LNCS (Vol. 8656, pp. 142-157). Cham: Springer.
[8] Beldiceanu, N., Carlsson, M., & Petit, T. (2004). Deriving filtering algorithms from constraint checkers. In Wallace, M. (Ed.) CP 2004. LNCS (Vol. 3258, pp. 107-122). Berlin, Heidelberg: Springer. · Zbl 1152.68539
[9] Beldiceanu, N., Ifrim, G., Lenoir, A., & Simonis, H. (2013). Describing and generating solutions for the EDF unit commitment problem with the ModelSeeker. In Schulte, C. (Ed.) CP 2013. LNCS (Vol. 8124, pp. 733-748). Berlin, Heidelberg: Springer.
[10] Colcombet, T; Daviaud, L, Approximate comparison of functions computed by distance automata, Theory on Computer System, 58, 579-613, (2016) · Zbl 1341.68123
[11] Crochemore, M., Hancart, C., & Lecroq, T. (2007). Algorithms on strings. Cambridge: Cambridge University Press. · Zbl 1137.68060
[12] Demassey, S; Pesant, G; Rousseau, LM, A cost-regular based hybrid column generation approach, Constraints, 11, 315-333, (2006) · Zbl 1117.90066
[13] Hopcroft, J. E., Motwani, R., & Ullman, J. D. (2007). Introduction to automata theory, languages, and computation, 3rd Edn. Boston: Addison-Wesley. · Zbl 0980.68066
[14] Ishihara, Y., Moroto, T., Shimizu, S., Hashimoto, K., & Fujiwara, T. (2009). A tractable subclass of dtds for xpath satisfiability with sibling axes. In Philippa, G., & Floris, G. (Eds.) Database programming languages: 12th international symposium, DBPL 2009s. LNCS (Vol. 5708, pp. 68-83). Berlin, Heidelberg: Springer.
[15] Pesant, G. (2004). A regular language membership constraint for finite sequences of variables. In Wallace, M. (Ed.) CP 2004. LNCS (Vol. 3258, pp. 482-495). Berlin, Heidelberg: Springer. · Zbl 1152.68573
[16] Schützenberger, MP, On the definition of a family of automata, Information and Control, 4, 245-270, (1961) · Zbl 0104.00702
[17] Simonis, H., Davern, P., Feldman, J., Mehta, D., Quesada, L., & Carlsson, M. (2010). A generic visualization platform for CP. In Cohen, D. (Ed.) Principles and practice of constraint programming - CP 2010 - 16th international conference, CP 2010, St. Andrews, Scotland, UK, September 6-10, 2010. Proceedings. Lecture notes in computer science (Vol. 6308, pp. 460-474). Berlin, Heidelberg: Springer, DOI https://doi.org/10.1007/978-3-642-15396-9_37. · Zbl 1341.68123
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.