From polynomial invariants to linear loops. (English) Zbl 07760785
Dickenstein, Alicia (ed.) et al., Proceedings of the 48th international symposium on symbolic and algebraic computation, ISSAC, Tromsø, Norway, July 24–27, 2023. New York, NY: Association for Computing Machinery (ACM). 398-406 (2023).
MSC:
| 68W30 | Symbolic computation and algebraic computation |
Software:
DependenciesReferences:
| [1] | Bruno Buchberger. 2006. Bruno Buchberger’s PhD thesis 1965: An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal. J. Symb. Comput. 41, 3-4 (2006), 475-511. · Zbl 1158.01307 |
| [2] | Keith D. Cooper, L. Taylor Simpson, and Christopher A. Vick. 2001. Operator Strength Reduction. ACM Trans. Program. Lang. Syst. 23, 5 (2001), 603-625. |
| [3] | David A. Cox, John B. Little, and Donal O’Shea. 2015. Ideals, varieties, and algorithms (fourth ed.). Springer, Cham. xvi+646 pages. https://doi.org/10.1007/978-3-319-16721-3 An introduction to computational algebraic geometry and commutative algebra. · Zbl 1335.13001 |
| [4] | David A. Cox, John B. Little, and Henry K. Schenck. 2011. Toric varieties. Graduate Studies in Mathematics, Vol. 124. American Mathematical Society, Providence, RI. xxiv+841 pages. https://doi.org/10.1090/gsm/124 · Zbl 1223.14001 |
| [5] | Martin Davis. 1972. On the Number of Solutions of Diophantine Equations. Proc. Amer. Math. Soc. 35, 2 (1972), 552-554. http://www.jstor.org/stable/2037646 · Zbl 0275.02042 |
| [6] | Steven de Oliveira, Saddek Bensalem, and Virgile Prevosto. 2016. Polynomial Invariants by Linear Algebra. In Proc. of ATVA. 479-494. · Zbl 1398.68099 |
| [7] | Persi Diaconis, David Eisenbud, and Bernd Sturmfels. 1998. Lattice walks and primary decomposition. In Mathematical essays in honor of Gian-Carlo Rota (Cambridge, MA, 1996). Progr. Math., Vol. 161. Birkhäuser Boston, Boston, MA, 173-193. · Zbl 0962.05010 |
| [8] | David Eisenbud and Bernd Sturmfels. 1996. Binomial ideals. Duke Math. J. 84, 1 (1996), 1-45. https://doi.org/10.1215/S0012-7094-96-08401-X · Zbl 0873.13021 |
| [9] | G. Everest, A. van der Poorten, I. Shparlinski, and T. Ward. 2003. Recurrence sequences. Math. Surveys Monogr., Vol. 104. Amer. Math. Soc., Providence, RI. xiv+318 pages. https://doi.org/10.1090/surv/104 · Zbl 1033.11006 |
| [10] | Francesco Galuppi and Mima Stanojkovski. 2021. Toric varieties from cyclic matrix semigroups. Rend. Istit. Mat. Univ. Trieste (2021). https://doi.org/10.13137/2464-8728/33099 · Zbl 1490.14088 |
| [11] | Dima Grigoriev, Alexandru Iosif, Hamid Rahkooy, Thomas Sturm, and Andreas Weber. 2019. Efficiently and Effectively Recognizing Toricity of Steady State Varieties. Mathematics in Computer Science 15 (2019), 199 - 232. · Zbl 1495.14095 |
| [12] | Jürgen Herzog, Takayuki Hibi, and Hidefumi Ohsugi. 2018. Binomial ideals. Graduate Texts in Mathematics, Vol. 279. Springer, Cham. xix+321 pages. https://doi.org/10.1007/978-3-319-95349-6 · Zbl 1403.13004 |
| [13] | E. Hrushovski, J. Ouaknine, A. Pouly, and J. Worrell. 2020. On Strongest Algebraic Program Invariants. J. of ACM (2020). To appear. · Zbl 1497.68113 |
| [14] | Andreas Humenberger, Daneshvar Amrollahi, Nikolaj Bjørner, and Laura Kovács. 2022. Algebra-Based Reasoning for Loop Synthesis. Form. Asp. Comput. 34, 1, Article 4 (jul 2022), 31 pages. https://doi.org/10.1145/3527458 · Zbl 1522.68155 |
| [15] | Andreas Humenberger, Maximilian Jaroschek, and Laura Kovács. 2018. Invariant Generation for Multi-Path Loops with Polynomial Assignments. In Proc. of VMCAI. 226-246. · Zbl 1446.68031 |
| [16] | Dejan Jovanovic and Leonardo de Moura. 2012. Solving non-linear arithmetic. ACM Commun. Comput. Algebra 46, 3/4 (2012), 104-105. · Zbl 1358.68257 |
| [17] | Thomas Kahle, Johannes Rauh, and Seth Sullivant. 2014. Positive margins and primary decomposition. J. Commut. Algebra 6, 2 (2014), 173-208. https://doi.org/10.1216/JCA-2014-6-2-173 · Zbl 1375.13047 |
| [18] | Lukas Katthän, Mateusz Michalek, and Ezra Miller. 2019. When is a Polynomial Ideal Binomial After an Ambient Automorphism?Found. Comput. Math. 19, 6 (2019), 1363-1385. https://doi.org/10.1007/s10208-018-9405-0 · Zbl 1429.13010 |
| [19] | Manuel Kauers and Peter Paule. 2011. The Concrete Tetrahedron - Symbolic Sums, Recurrence Equations, Generating Functions, Asymptotic Estimates. Springer. · Zbl 1225.00001 |
| [20] | Manuel Kauers and Burkhard Zimmermann. 2008. Computing the algebraic relations of C-finite sequences and multisequences. Journal of Symbolic Computation 43, 11 (2008), 787-803. https://doi.org/10.1016/j.jsc.2008.03.002 · Zbl 1163.11084 |
| [21] | Deepanjan Kesh and Shashank K. Mehta. 2009. Generalized Reduction to Compute Toric Ideals. In Algorithms and Computation, Yingfei Dong, Ding-Zhu Du, and Oscar Ibarra (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 483-492. · Zbl 1273.68419 |
| [22] | Zachary Kincaid, John Cyphert, Jason Breck, and Thomas W. Reps. 2018. Non-Linear Reasoning for Invariant Synthesis. In Proc. of POPL. 54:1-54:33. |
| [23] | Laura Kovács. 2008. Reasoning Algebraically About P-Solvable Loops. In Proc. of TACAS. 249-264. · Zbl 1134.68600 |
| [24] | Joël Ouaknine and James Worrell. 2015. On Linear Recurrence Sequences and Loop Termination. ACM SIGLOG News 2, 2 (apr 2015), 4-13. https://doi.org/10.1145/2766189.2766191 |
| [25] | Enric Rodríguez-Carbonell and Deepak Kapur. 2004. Automatic Generation of Polynomial Loop Invariants: Algebraic Foundations. In Proc. of ISSAC. 266-273. · Zbl 1108.13310 |
| [26] | Joseph H. Silverman and John T. Tate. 2015. Rational Points on Elliptic Curves (2nd ed.). Springer Publishing Company, Incorporated. · Zbl 1346.11001 |
| [27] | Bernd Sturmfels. 1996. Gröbner bases and convex polytopes. University Lecture Series, Vol. 8. American Mathematical Society, Providence, RI. xii+162 pages. https://doi.org/10.1090/ulect/008 · Zbl 0856.13020 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
