nach oben

Erschienen in:

2021 | OriginalPaper | Buchkapitel

MDDs Boost Equation Solving on Discrete Dynamical Systems

verfasst von : Enrico Formenti, Jean-Charles Régin, Sara Riva

Erschienen in: Integration of Constraint Programming, Artificial Intelligence, and Operations Research

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Discrete dynamical systems (DDS) are a model to represent complex phenomena appearing in many different domains. In the finite case, they can be identified with a particular class of graphs called dynamics graphs. In [9] polynomial equations over dynamics graphs have been introduced. A polynomial equation represents a hypothesis on the fine structure of the system. Finding the solutions of such equations validate or invalidate the hypothesis.

This paper proposes new algorithms that enumerate all the solutions of polynomial equations with constant right-hand term outperforming the current state-of-art methods [10]. The boost in performance of our algorithms comes essentially from a clever usage of Multi-valued decision diagrams.

These results are an important step forward in the analysis of complex dynamics graphs as those appearing, for instance, in biological regulatory networks or in systems biology.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel A Pipe Routing Hybrid Approach Based on A-Star Search and Linear Programming

Nächstes Kapitel Two Deadline Reduction Algorithms for Scheduling Dependent Tasks on Parallel Processors

Akers, S.B.: Binary decision diagrams. IEEE Trans. Comput. 27(06) ,509–516 (1978)

Amilhastre, J., Fargier, H., Niveau, A., Pralet, C.: Compiling CSPs: a complexity map of (non-deterministic) multivalued decision diagrams. Int. J. Artif. Intell. Tools 23(04), 1460015 (2014)CrossRef

Andersen, H.R.: An introduction to binary decision diagrams. Lecture notes, available online, IT University of Copenhagen, p. 5 (1997)

Bergman, D., Cire, A.A., van Hoeve, W.: MDD propagation for sequence constraints. J. Artif. Intell. Res. 50, 697–722 (2014)MathSciNetCrossRef

Bergman, D., Cire, A.A., Van Hoeve, W.J., Hooker, J.: Decision diagrams for optimization, vol. 1. Springer, Berlin (2016). https://doi.org/10.1007/978-3-319-42849-9

Berndt, R., Bazan, P., Hielscher, K.S., German, R., Lukasiewycz, M.: Multi-valued decision diagrams for the verification of consistency in automotive product data. In: 2012 12th International Conference on Quality Software, pp. 189–192. IEEE (2012)

Cheng, K.C., Yap, R.H.: An MDD-based generalized arc consistency algorithm for positive and negative table constraints and some global constraints. Constraints 15(2), 265–304 (2010)MathSciNetCrossRef

Darwiche, A., Marquis, P.: A knowledge compilation map. J. Artif. Intell. Res. 17, 229–264 (2002)MathSciNetCrossRef

Dennunzio, A., Dorigatti, V., Formenti, E., Manzoni, L., Porreca, A.E.: Polynomial equations over finite, discrete-time dynamical systems. In: Mauri, G., El Yacoubi, S., Dennunzio, A., Nishinari, K., Manzoni, L. (eds.) ACRI 2018. LNCS, vol. 11115, pp. 298–306. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-99813-8_27CrossRef

10.

Dennunzio, A., Formenti, E., Margara, L., Montmirail, V., Riva, S.: Solving equations on discrete dynamical systems. In: Cazzaniga, P., Besozzi, D., Merelli, I., Manzoni, L. (eds.) Computational Intelligence Methods for Bioinformatics and Biostatistics, pp. 119–132. Springer International Publishing, Cham (2020)CrossRef

11.

Martello, S., Toth, P.: Knapsack Problems: Algorithms and Computer Implementations. Wiley, New York, NY, USA (1990)MATH

12.

Nakahara, H., Jinguji, A., Sato, S., Sasao, T.: A random forest using a multi-valued decision diagram on an FPGA. In: 2017 IEEE 47th International Symposium on Multiple-Valued Logic (ISMVL), pp. 266–271. IEEE (2017)

13.

Naldi, A., Thieffry, D., Chaouiya, C.: Decision diagrams for the representation and analysis of logical models of genetic networks. In: Calder, M., Gilmore, S. (eds.) CMSB 2007. LNCS, vol. 4695, pp. 233–247. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-75140-3_16CrossRef

14.

Perez, G., Régin, J.C.: Efficient operations on MDDs for building constraint programming models. In: IJCAI (2015)

15.

Zaitseva, E., Levashenko, V., Kostolny, J., Kvassay, M.: A multi-valued decision diagram for estimation of multi-state system. In: Eurocon 2013, pp. 645–650. IEEE (2013)

16.

Zhang, L., Xing, L., Liu, A., Mao, K.: Multivalued decision diagrams-based trust level analysis for social networks. IEEE Access 7, 180620–180629 (2019)CrossRef

Titel: MDDs Boost Equation Solving on Discrete Dynamical Systems
verfasst von: Enrico Formenti
Jean-Charles Régin
Sara Riva
Verlag: Springer International Publishing
Buch: Integration of Constraint Programming, Artificial Intelligence, and Operations Research
Print ISBN: 978-3-030-78229-0

Electronic ISBN: 978-3-030-78230-6

Copyright-Jahr: 2021
DOI: https://doi.org/10.1007/978-3-030-78230-6_13

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner