Using finite transducers for describing and synthesising structural time-series constraints

详细信息    查看全文

• 作者：Nicolas Beldiceanu ; Mats Carlsson ; Rémi Douence ; Helmut Simonis
• 关键词：Global constraint ; Time series ; Global constraint catalogue ; Constraint synthesis ; Finite transducer
• 刊名：Constraints
• 出版年：2016
• 出版时间：January 2016
• 年：2016
• 卷：21
• 期：1
• 页码：22-40
• 全文大小：1,450 KB
• 参考文献：1.Abney, S. (1996). Partial parsing via finite-state cascades. Natural Language Engineering, 2(4), 337–344.CrossRef
  2.Beldiceanu, N., Carlsson, M., Debruyne, R., & Petit, T. (2005). Reformulation of global constraints based on constraints checkers. Constraints, 10(4), 339–362.MATH MathSciNet CrossRef
  3.Beldiceanu, N., Carlsson, M., Demassey, S., & Petit, T. (2007). Global constraint catalogue: Past, present and future. Constraints, 12(1), 21–62.MATH MathSciNet CrossRef
  4.Beldiceanu, N., Carlsson, M., Flener, P., & Pearson, J. (2013). On the reification of global constraints. Constraints, 18(1), 1–6.MathSciNet CrossRef
  5.Beldiceanu, N., Carlsson, M., Flener, P., Rodríguez, M.A.F., & Pearson, J. (2014). Linking prefixes and suffixes for constraints encoded using automata with accumulators. In B. O’Sullivan (Ed.), Principles and practice of constraint programming (CP 2014), LNCS, (Vol. 8656 pp. 142–157): Springer.
  6.Beldiceanu, N., Carlsson, M., & Rampon, J.X. Global constraint catalog, 2nd edition (revision a). Tech. Rep. T2012-03, Swedish Institute of Computer Science (2012), current version available at, http://​sofdem.​github.​io/​gccat/​ .
  7.Beldiceanu, N., Flener, P., Monette, J.N., Pearson, J., & Simonis, H. (2014). Toward sustainable development in constraint programming. Constraints, 19 (2), 139–149.CrossRef
  8.Beldiceanu, N., Ifrim, G., Lenoir, A., & Simonis, H. (2013). Describing and generating solutions for the EDF unit commitment problem with the ModelSeeker. In C. Schulte (Ed.), Principles and practice of constraint programming (CP 2013), LNCS, (Vol. 8124 pp. 733–748): Springer.
  9.Beldiceanu, N., & Simonis, H. (2011). A constraint seeker: Finding and ranking global constraints from examples. In J. Lee (Ed.), Principles and Practice of Constraint Programming (CP 2011), LNCS, (Vol. 6876 pp. 12–26): Springer.
  10.Beldiceanu, N., & Simonis, H. (2012). A model seeker: Extracting global constraint models from positive examples. In M. Milano (Ed.), Principles and Practice of Constraint Programming - 18th International Conference, CP 2012, Quebec City, QC, Canada, October 8-12, 2012. Proceedings. Lecture Notes in Computer Science, (Vol. 7514 pp. 141–157): Springer. doi:10.​1007/​978-3-642-33558-7_​13 .
  11.Berstel, J. (1979). Transductions and context-free languages: Teubner.
  12.Carlsson, M., & et al. SICStus Prolog User’s Manual. Swedish Institute of Computer Science, 4.3.1 edn. (November 2014), current version available at, https://​sicstus.​sics.​se/​sicstus/​docs/​latest4/​pdf/​sicstus.​pdf .
  13.Fu, T. (2011). A review on time series data mining. Engineering Applications of Artificial Intelligence, 24(1), 164–181. http://​www.​sciencedirect.​com/​science/​article/​pii/​S095219761000172​7 .CrossRef
  14.Fung, D.S.C. (2006). Methods for the estimation of missing values in time series. Master’s thesis. Perth: Edith Cowan University.
  15.Gent, I.P., Jefferson, C., Linton, S., Miguel, I., & Nightingale, P. (2014). Generating custom propagators for arbitrary constraints. Artificial Intelligence, 211, 1–33.MATH MathSciNet CrossRef
  16.Goldin, D.Q., & Kanellakis, P.C. (1995). On similarity queries for time-series data: Constraint specification and implementation. In U. Montanari, & F. Rossi (Eds.), Principles and Practice of Constraint Programming (CP 1995), LNCS, (Vol. 976 pp. 137–153): Springer.
  17.Guns, T., Nijssen, S., & De Raedt, L. (2011). Itemset mining: A constraint programming perspective. Artificial Intelligence, 175(12–13), 1951–1983.MATH MathSciNet CrossRef
  18.Harvey, A. (1991). Forecasting, structural time series models and the Kalman filter: Cambridge University Press.
  19.Laurière, J.L. Constraint propagation or automatic programming. Tech. Rep. 19, IBP-Laforia (1996), in French, available at, https://​www.​lri.​fr/​sebag/​Slides/​Lauriere/​Rabbit.​pdf .
  20.Liao, T.W. (2005). Clustering of time series data - a survey. Pattern Recognition, 38(11), 1857–1874. doi:10.​1016/​j.​patcog.​2005.​01.​025 .MATH CrossRef
  21.Nhon, D.T., & Wilkinson, L. (2013). TimeExplorer: Similarity search time series by their signatures. In G. Bebis, R. Boyle, B. Parvin, D. Koracin, B. Li, F. Porikli, V.B. Zordan, J.T. Klosowski, S. Coquillart, X. Luo, M. Chen, & D. Gotz (Eds.), 9th International Symposium on Advances in Visual Computing (ISVC 2013), LNCS, (Vol. 8033 pp. 280–289): Springer.
  22.Perng, C.S., Wang, H., Zhang, S.R., & Parker, D.S. (2000). Landmarks: A new model for similarity-based pattern querying in time series databases. In 16th International Conference on Data Engineering (ICDE 2000) (pp. 33–42): IEEE.
  23.Ratanamahatana, C., Lin, J., Gunopulos, D., Keogh, E., Vlachos, M., & Das, G. (2010). Mining time series data. In O. Maimon, & L. Rokach (Eds.), Data mining and knowledge discovery handbook (pp. 1049–1077). US: Springer. doi:10.​1007/​978-0-387-09823-4_​56 .
  24.Sakarovitch, J. (2009). Elements of language theory: Cambridge University Press.
  25.Smith, D.R., & Westfold, S.J. Toward the synthesis of constraint solvers. Tech. Rep. TR-1311, Kestrel Institute (2013), available at, http://​www.​kestrel.​edu/​home/​people/​smith/​pub/​CW-report.​pdf .
  26.Veanes, M., Hooimeijer, P., Livshits, B., Molnar, D., & Bjørner, N. (2012). Symbolic finite state transducers: algorithms and applications. In J. Field, & M. Hicks (Eds.), Proceedings of the 39th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2012, Philadelphia, Pennsylvania, USA (pp. 137–150): ACM.
  
• 作者单位：Nicolas Beldiceanu (1)
  Mats Carlsson (2)
  Rémi Douence (3)
  Helmut Simonis (4)
  
  1. TASC (CNRS/INRIA), Mines Nantes, FR, 44307, Nantes, France
  2. SICS, P.O. Box 1263, SE, 164 29, Kista, Sweden
  3. ASCOLA (CNRS/INRIA), Mines Nantes, FR, 44307, Nantes, France
  4. Insight Centre for Data Analytics, University College Cork, Cork, Ireland
  
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Optimization
  Computing Methodologies
  Operation Research and Decision Theory
  
• 出版者：Springer Netherlands
• ISSN：1572-9354

文摘

We describe a large family of constraints for structural time series by means of function composition. These constraints are on aggregations of features of patterns that occur in a time series, such as the number of its peaks, or the range of its steepest ascent. The patterns and features are usually linked to physical properties of the time series generator, which are important to capture in a constraint model of the system, i.e. a conjunction of constraints that produces similar time series. We formalise the patterns using finite transducers, whose output alphabet corresponds to semantic values that precisely describe the steps for identifying the occurrences of a pattern. Based on that description, we automatically synthesise automata with accumulators, as well as constraint checkers. The description scheme not only unifies the structure of the existing 30 time-series constraints in the Global Constraint Catalogue, but also leads to over 600 new constraints, with more than 100,000 lines of synthesised code. Keywords Global constraint Time series Global constraint catalogue Constraint synthesis Finite transducer