Publication

A Complete Invariant Generation Approach for P-solvable Loops

2010
Conference Papers

Abstract

We present an algorithm for generating all polynomial invariants of P-solvable loops with assignments and nested conditionals. We prove termination of our algorithm. The proof relies on showing that the dimensions of the prime ideals from the minimal decomposition of the ideals generated at an iteration of our algorithm either remain the same or decrease at the next iteration of the algorithm. Our experimental results report that our method takes less iterations and/or time than other polynomial invariant generation techniques.

Official source

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

2010
Conference Papers

Abstract

Official source

Related concepts (32)

Prime ideal

In algebra, a prime ideal is a subset of a ring that shares many important properties of a prime number in the ring of integers. The prime ideals for the integers are the sets that contain all the multiples of a given prime number, together with the zero ideal. Primitive ideals are prime, and prime ideals are both primary and semiprime. An ideal P of a commutative ring R is prime if it has the following two properties: If a and b are two elements of R such that their product ab is an element of P, then a is in P or b is in P, P is not the whole ring R.

Ideal (ring theory)

In mathematics, and more specifically in ring theory, an ideal of a ring is a special subset of its elements. Ideals generalize certain subsets of the integers, such as the even numbers or the multiples of 3. Addition and subtraction of even numbers preserves evenness, and multiplying an even number by any integer (even or odd) results in an even number; these closure and absorption properties are the defining properties of an ideal.

Maximal ideal

In mathematics, more specifically in ring theory, a maximal ideal is an ideal that is maximal (with respect to set inclusion) amongst all proper ideals. In other words, I is a maximal ideal of a ring R if there are no other ideals contained between I and R. Maximal ideals are important because the quotients of rings by maximal ideals are simple rings, and in the special case of unital commutative rings they are also fields.