Degree and Dimension Estimates for Invariant Ideals of $$P$$ -Solvable Recurrences

Marc Moreno Maza () and Rong Xiao ()
Additional contact information
Marc Moreno Maza: University of Western Ontario
Rong Xiao: University of Western Ontario

A chapter in Computer Mathematics, 2014, pp 349-373 from Springer

Abstract: Abstract Motivated by the generation of polynomial loop invariants of computer programs, we study $$P$$ -solvable recurrences. While these recurrences may contain non-linear terms, we show that the solutions of any such relation can be obtained by solving a system of linear recurrences. We also study invariant ideals of $$P$$ -solvable recurrences (or equivalently of while loops with no branches). We establish sharp degree and dimension estimates of those invariant ideals.

Keywords: Invariant Ideals; Linear Recurrence; Polynomial Loop Invariants; Sharp Degree; Affine Recurrence (search for similar items in EconPapers)
Date: 2014
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-662-43799-5_25

Ordering information: This item can be ordered from
http://www.springer.com/9783662437995

DOI: 10.1007/978-3-662-43799-5_25

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().