[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Termination of Polynomial Loops

  • Conference paper
  • First Online:
Static Analysis (SAS 2020)

Part of the book series: Lecture Notes in Computer Science ((LNPSE,volume 12389))

Included in the following conference series:

Abstract

We consider the termination problem for triangular weakly non-linear loops (twn-loops) over some ring \(\mathcal {S}\) like \(\mathbb {Z}\), \(\mathbb {Q}\), or \(\mathbb {R}\). Essentially, the guard of such a loop is an arbitrary Boolean formula over (possibly non-linear) polynomial inequations, and the body is a single assignment where each \(x_i\) is a variable, \(c_i \in \mathcal {S}\), and each \(p_i\) is a (possibly non-linear) polynomial over \(\mathcal {S}\) and the variables \(x_{i+1},\ldots ,x_{d}\).

We present a reduction from the question of termination to the existential fragment of the first-order theory of \(\mathcal {S}\) and \(\mathbb {R}\). For loops over \(\mathbb {R}\), our reduction entails decidability of termination. For loops over \(\mathbb {Z}\) and \(\mathbb {Q}\), it proves semi-decidability of non-termination.

Furthermore, we present a transformation to convert certain non-twn-loops into twn-form. Then the original loop terminates iff the transformed loop terminates over a specific subset of \(\mathbb {R}\), which can also be checked via our reduction. This transformation also allows us to prove tight complexity bounds for the termination problem for two important classes of loops which can always be transformed into twn-loops.

Funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) - 389792660 as part of TRR 248, by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) - 235950644 (Project GI 274/6-2), and by the DFG Research Training Group 2236 UnRAVeL.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 47.99
Price includes VAT (United Kingdom)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 59.99
Price includes VAT (United Kingdom)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    We use row- and column-vectors interchangeably to improve readability.

  2. 2.

    Note that negation is syntactic sugar in our setting, as, e.g., \(\lnot (p > 0)\) is equivalent to \(-p \ge 0\). So w.l.o.g. \(\varphi \) is built from atoms, \(\wedge \), and \(\vee \).

  3. 3.

    In this paper “linear” refers to “linear polynomials” and thus includes affine functions.

  4. 4.

    So we have \(\eta (c \cdot p + c' \cdot p') = c \cdot \eta (p) + c' \cdot \eta (p')\), \(\eta (1)=1\), and \(\eta (p \cdot p') = \eta (p)\cdot \eta (p')\) for all \(c,c' \in \mathcal {S}\) and all \(p,p' \in \mathcal {S}[\vec {x}]\).

  5. 5.

    In other words, we have \(\vec {a}' = (\eta (\vec {x})) \, (\vec {a}) \, (\eta ^{-1}(\vec {x}))\), since \((\eta ^{-1}\circ \widetilde{a}\circ \eta )(\vec {x}) = \eta ^{-1}(\eta (\vec {x})[\vec {x}/\vec {a}]) = \eta (\vec {x})[\vec {x}/\vec {a}][\vec {x} / \eta ^{-1}(\vec {x})] = (\eta (\vec {x}))(\vec {a})(\eta ^{-1}(\vec {x}))\).

  6. 6.

    Our definition of poly-exponential expressions slightly generalizes [15, Def. 9] (e.g., we allow polynomials over the variables \(\vec {x}\) instead of just linear combinations).

  7. 7.

    More precisely, the reduction of Lemma 34 and of the following Theorem 36 takes polynomially many steps in the size of the input of the function in (5).

References

  1. Babić, D., Cook, B., Hu, A.J., Rakamaric, Z.: Proving termination of nonlinear command sequences. Formal Aspects Comput. 25(3), 389–403 (2013). https://doi.org/10.1007/s00165-012-0252-5

    Article  MathSciNet  MATH  Google Scholar 

  2. Basu, S., Pollack, R., Roy, M.-F.: Algorithms in Real Algebraic Geometry, Algorithms and Computation in Mathematics, vol. 10. Springer, Heidelberg (2006). https://doi.org/10.1007/3-540-33099-2

    Book  MATH  Google Scholar 

  3. Basu, S., Mishra, B.: Computational and quantitative real algebraic geometry. In: Goodman, J.E., O’Rourke, J., Tóth, C.D. (eds.) Handbook of Discrete and Computational Geometry, 3rd edn. Chapman and Hall/CRC, pp. 969–1002 (2017). https://doi.org/10.1201/9781315119601

  4. Ben-Amram, A.M., Genaim, S.: On multiphase-linear ranking functions. In: Majumdar, R., Kunčak, V. (eds.) CAV 2017. LNCS, vol. 10427, pp. 601–620. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63390-9_32

    Chapter  Google Scholar 

  5. Ben-Amram, A.M., Doménech, J.J., Genaim, S.: Multiphase-linear ranking functions and their relation to recurrent sets. In: Chang, B.-Y.E. (ed.) SAS 2019. LNCS, vol. 11822, pp. 459–480. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-32304-2_22

    Chapter  Google Scholar 

  6. Bozga, M., Iosif, R., Konecný, F.: Deciding conditional termination. Logical Meth. Comput. Sci. 10(3) (2014). https://doi.org/10.2168/LMCS-10(3:8)2014

  7. Bradley, A.R., Manna, Z., Sipma, H.B.: Termination of polynomial programs. In: Cousot, R. (ed.) VMCAI 2005. LNCS, vol. 3385, pp. 113–129. Springer, Heidelberg (2005). https://doi.org/10.1007/978-3-540-30579-8_8

    Chapter  Google Scholar 

  8. Braverman, M.: Termination of integer linear programs. In: Ball, T., Jones, R.B. (eds.) CAV 2006. LNCS, vol. 4144, pp. 372–385. Springer, Heidelberg (2006). https://doi.org/10.1007/11817963_34

    Chapter  Google Scholar 

  9. Brockschmidt, M., Cook, B., Fuhs, C.: Better termination proving through cooperation. In: Sharygina, N., Veith, H. (eds.) CAV 2013. LNCS, vol. 8044, pp. 413–429. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-39799-8_28

    Chapter  Google Scholar 

  10. Chen, H.-Y., Cook, B., Fuhs, C., Nimkar, K., O’Hearn, P.: Proving nontermination via safety. In: Ábrahám, E., Havelund, K. (eds.) TACAS 2014. LNCS, vol. 8413, pp. 156–171. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-54862-8_11

    Chapter  Google Scholar 

  11. Cohen, P.J.: Decision procedures for real and p-adic fields. Commun. Pure Appl. Math. 22(2), 131–151 (1969). https://doi.org/10.1002/cpa.3160220202

    Article  MathSciNet  MATH  Google Scholar 

  12. Dai, L., Xia, B.: Non-termination sets of simple linear loops. In: Roychoudhury, A., D’Souza, M. (eds.) ICTAC 2012. LNCS, vol. 7521, pp. 61–73. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32943-2_5

    Chapter  Google Scholar 

  13. van den Essen, A., Hubbers, E.: Polynomial maps with strongly nilpotent Jacobian matrix and the Jacobian conjecture. Linear Algebra Appl. 247, 121–132 (1996). https://doi.org/10.1016/0024-3795(95)00095-X

    Article  MathSciNet  MATH  Google Scholar 

  14. van den Essen, A.: Polynomial Automorphisms and the Jacobian Conjecture. Springer, Basel (2000). https://doi.org/10.1007/978-3-0348-8440-2

    Book  MATH  Google Scholar 

  15. Frohn, F., Giesl, J.: Termination of triangular integer loops is decidable. In: Dillig, I., Tasiran, S. (eds.) CAV 2019. LNCS, vol. 11562, pp. 426–444. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-25543-5_24

    Chapter  Google Scholar 

  16. Frohn, F., Hark, M., Giesl, J.: On the decidability of termination for polynomial loops. CoRR abs/1910.11588 (2019). https://arxiv.org/abs/1910.11588

  17. Frohn, F., Giesl, J.: Proving non-termination via loop acceleration. In: Barrett, C.W., Yang, J. (eds.) FMCAD 2019, pp. 221–230 (2019). https://doi.org/10.23919/FMCAD.2019

  18. Frohn, F.: A calculus for modular loop acceleration. In: Biere, A., Parkerm D. (eds.) TACAS 2020. LNCS, vol. 12078, pp. 58–76. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45190-5_4

  19. Giesbrecht, M.: Nearly optimal algorithms for canonical matrix forms. SIAM J. Comput. 24(5), 948–969 (1995). https://doi.org/10.1137/S0097539793252687

    Article  MathSciNet  MATH  Google Scholar 

  20. Giesl, J.: Analyzing program termination and complexity automatically with AProVE. J. Autom. Reasoning 58(1), 3–31 (2017). https://doi.org/10.1007/s10817-016-9388-y

    Article  MathSciNet  MATH  Google Scholar 

  21. Giesl, J., Rubio, A., Sternagel, C., Waldmann, J., Yamada, A.: The termination and complexity competition. In: Beyer, D., Huisman, M., Kordon, F., Steffen, B. (eds.) TACAS 2019. LNCS, vol. 11429, pp. 156–166. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17502-3_10

    Chapter  Google Scholar 

  22. Gupta, A., Henzinger, T.A., Majumdar, R., Rybalchenko, A., Xu, R.: Proving non-termination. In: Necula, G.C., Wadler, P. (eds.) POPL 2008, pp. 147–158 (2008). https://doi.org/10.1145/1328438.1328459

  23. Hark, M., Frohn, F., Giesl, J.: Polynomial loops: beyond termination. In: Albert, E., Kovács, L. (eds.) LPAR 2020. EPiC, vol. 73, pp. 279–297 (2020). https://doi.org/10.29007/nxv1

  24. Hosseini, M., Ouaknine, J., Worrell, J.: Termination of linear loops over the integers. In: Baier, C., Chatzigiannakis, I., Flocchini, P., Leonardi, S. (eds.) ICALP 2019. LIPIcs, vol. 132, 118:1–118:13 (2019). https://doi.org/10.4230/LIPIcs.ICALP.2019.118

  25. Humenberger, A., Jaroschek, M., Kovács, L.: Invariant generation for multi-path loops with polynomial assignments. In: Dillig, I., Palsberg, J. (eds.) VMCAI 2018. LNCS, vol. 10747, pp. 226–246. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-73721-8_11

  26. Kauers, M., Paule, P.: The Concrete Tetrahedron – Symbolic Sums, Recurrence Equations, Generating Functions, Asymptotic Estimates. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-7091-0445-3

  27. Kincaid, Z., Cyphert, J., Breck, J., Reps, T.W.: Non-linear reasoning for invariant synthesis. Proc. ACM Program. Lang. 2(POPL), 54:1–54:33 (2018). https://doi.org/10.1145/3158142

    Article  Google Scholar 

  28. Kincaid, Z., Breck, J., Cyphert, J., Reps, T.W.: Closed forms for numerical loops. Proc. ACM Program. Lang. 3(POPL), 55:1–55:29 (2019). https://doi.org/10.1145/3290368

    Article  Google Scholar 

  29. Kovács, L.: Reasoning algebraically about p-solvable loops. In: Ramakrishnan, C.R., Rehof, J. (eds.) TACAS 2008. LNCS, vol. 4963, pp. 249–264. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78800-3_18

    Chapter  Google Scholar 

  30. Larraz, D., Oliveras, A., Rodríguez-Carbonell, E., Rubio, A.: Proving termination of imperative programs using Max-SMT. In: Jobstmann, B., Ray, S. (eds.) FMCAD 2013, pp. 218–225 (2013). https://doi.org/10.1109/FMCAD.2013.6679413

  31. Larraz, D., Nimkar, K., Oliveras, A., Rodríguez-Carbonell, E., Rubio, A.: Proving non-termination Using Max-SMT. In: Biere, A., Bloem, R. (eds.) CAV 2014. LNCS, vol. 8559, pp. 779–796. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-08867-9_52

    Chapter  Google Scholar 

  32. Leike, J., Heizmann, M.: Ranking templates for linear loops. Logical Method Comput. Sci. 11(1) (2015). https://doi.org/10.2168/LMCS-11(1:16)2015

  33. Leike, J., Heizmann, M.: Geometric nontermination arguments. In: Beyer, D., Huisman, M. (eds.) TACAS 2018. LNCS, vol. 10806, pp. 266–283. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-89963-3_16

    Chapter  Google Scholar 

  34. Li, Y.: A recursive decision method for termination of linear programs. In: Zhi, L., Watt, S.M. (eds.) SNC 2014, pp. 97–106 (2014). https://doi.org/10.1145/2631948.2631966

  35. Li, Y.: Termination of single-path polynomial loop programs. In: Sampaio, A., Wang, F. (eds.) ICTAC 2016. LNCS, vol. 9965, pp. 33–50. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-46750-4_3

    Chapter  Google Scholar 

  36. Li, Y.: Termination of semi-algebraic loop programs. In: Larsen, K.G., Sokolsky, O., Wang, J. (eds.) SETTA 2017. LNCS, vol. 10606, pp. 131–146. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-69483-2_8

    Chapter  Google Scholar 

  37. Li, Y.: Witness to non-termination of linear programs. Theoret. Comput. Sci. 681, 75–100 (2017). https://doi.org/10.1016/j.tcs.2017.03

    Article  MathSciNet  MATH  Google Scholar 

  38. Neumann, E., Ouaknine, J., Worrell, J.: On ranking function synthesis and termination for polynomial programs. In: Konnov, I., Kovács, L. (eds.) CONCUR 2020. LIPIcs, vol. 171, pp. 15:1–15:15 (2020). https://doi.org/10.4230/LIPIcs.CONCUR.2020.15

  39. de Oliveira, S., Bensalem, S., Prevosto, V.: Polynomial invariants by linear algebra. In: Artho, C., Legay, A., Peled, D. (eds.) ATVA 2016. LNCS, vol. 9938, pp. 479–494. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-46520-3_30

    Chapter  Google Scholar 

  40. de Oliveira, S., Bensalem, S., Prevosto, V.: Synthesizing invariants by solving solvable loops. In: D’Souza, D., Narayan Kumar, K. (eds.) ATVA 2017. LNCS, vol. 10482, pp. 327–343. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-68167-2_22

    Chapter  Google Scholar 

  41. Ouaknine, J., Pinto, J.S., Worrell, J.: On termination of integer linear loops. In: Indyk, P. (ed.) SODA 2015, pp. 957–969 (2015). https://doi.org/10.1137/19781611973730.65

  42. Pia, A.D., Dey, S.S., Molinaro, M.: Mixed-integer quadratic programming is in NP. Math. Program. 162(1–2), 225–240 (2017). https://doi.org/10.1007/s10107-016-1036-0

    Article  MathSciNet  MATH  Google Scholar 

  43. Podelski, A., Rybalchenko, A.: A complete method for the synthesis of linear ranking functions. In: Steffen, B., Levi, G. (eds.) VMCAI 2004. LNCS, vol. 2937, pp. 239–251. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24622-0_20

    Chapter  Google Scholar 

  44. Renegar, J.: On the computational complexity and geometry of the first-order theory of the reals, part I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals. J. Symbolic Comput. 13(3), 255–300 (1992). https://doi.org/10.1016/S0747-7171(10)80003-3

  45. Robinson, J.: Definability and decision problems in arithmetic. J. Symbolic Logic 14(2), 98–114 (1949). https://doi.org/10.2307/2266510

    Article  MathSciNet  MATH  Google Scholar 

  46. Roch, J.-L., Villard, G.: Fast parallel computation of the Jordan normal form of matrices. Parallel Process. Lett. 06(02), 203–212 (1996). https://doi.org/10.1142/S0129626496000200

    Article  MathSciNet  Google Scholar 

  47. Roche, D.S.: What Can (and Can’t) we Do with Sparse Polynomials?” In: Kauers, M., Indyk, Ovchinnikov, A., Schost, É (eds.) ISSAC 2018, pp. 25–30 (2018). https://doi.org/10.1145/3208976.3209027

  48. Rodríguez-Carbonell, E., Kapur, D.: Automatic generation of polynomial loop invariants: algebraic foundation. In: Gutierrez, J. (ed.) ISSAC 2004, pp. 266–273 (2004). https://doi.org/10.1145/1005285.1005324

  49. Rodríguez-Carbonell, E., Kapur, D.: Generating all polynomial invariants in simple loops. J. Symbolic Comput. 42(4), 443–476 (2007). https://doi.org/10.1016/j.jsc.2007.01.002

    Article  MathSciNet  MATH  Google Scholar 

  50. Schaefer, M.: Complexity of some geometric and topological problems. In: Eppstein, D., Gansner, E.R. (eds.) GD 2009. LNCS, vol. 5849, pp. 334–344. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-11805-0_32

    Chapter  Google Scholar 

  51. Schaefer, M., Štefankovič, D.: Fixed points, Nash equilibria, and the existential theory of the reals. Theory Comput. Syst. 60(2), 172–193 (2017). https://doi.org/10.1007/s00224-015-9662-0

    Article  MathSciNet  MATH  Google Scholar 

  52. Tarski, A.: A decision method for elementary algebra and geometry. In: Caviness, B.F., Johnson, J.R. (eds.) Quantifier Elimination and Cylindrical Algebraic Decomposition. Originally appeared in 1951, University of California Press, Berkeley and Los Angeles, pp. 24–84. Springer, Vienna (1998). https://doi.org/10.1007/978-3-7091-9459-1_3

  53. Tiwari, A.: Termination of linear programs. In: Alur, R., Peled, D.A. (eds.) CAV 2004. LNCS, vol. 3114, pp. 70–82. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-27813-9_6

    Chapter  Google Scholar 

  54. TPDB (Termination Problems Data Base). http://termination-portal.org/wiki/TPDB

  55. Xia, B., Zhang, Z.: Termination of linear programs with nonlinear constraints. J. Symbolic Comput. 45(11), 1234–1249 (2010). https://doi.org/10.1016/j.jsc.2010.06.006

    Article  MathSciNet  MATH  Google Scholar 

  56. Xu, M., Li, Z.: Symbolic termination analysis of solvable loops. J. Symbolic Comput. 50, 28–49 (2013). https://doi.org/10.1016/jjsc.2012.05.005

Download references

Acknowledgments

We thank Alberto Fiori for help with the example loop (13) and Arno van den Essen for useful discussions.

Author information

Authors and Affiliations

  1. Max Planck Institute for Informatics and Saarland Informatics Campus, Saarbrücken, Germany

    Florian Frohn

  2. LuFG Informatik 2, RWTH Aachen University, Aachen, Germany

    Marcel Hark & Jürgen Giesl

Authors
  1. Florian Frohn
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Marcel Hark
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jürgen Giesl
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Marcel Hark .

Editor information

Editors and Affiliations

  1. Inria, IRISA, ENS Rennes, Bruz, France

    David Pichardie

  2. LSV, ENS Paris-Saclay, Gif-sur-Yvette, France

    Mihaela Sighireanu

Rights and permissions

Reprints and permissions

Copyright information

© 2020 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Frohn, F., Hark, M., Giesl, J. (2020). Termination of Polynomial Loops. In: Pichardie, D., Sighireanu, M. (eds) Static Analysis. SAS 2020. Lecture Notes in Computer Science(), vol 12389. Springer, Cham. https://doi.org/10.1007/978-3-030-65474-0_5

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-65474-0_5

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-65473-3

  • Online ISBN: 978-3-030-65474-0

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation