Publication

Complete Program Synthesis for Linear Arithmetic

2010
Student Projects

Abstract

Synthesis of programs or their fragments is a way to write programs by providing only their meaning without worrying about the implementation details. It avoids the drawback of writing sequential code, which might be difficult to check, error-prone or tedious. Our contribution is to provide complete program synthesis algorithms with unbounded data types in decidable theories. We present synthesis algorithms for Linear Rational Arithmetic, Linear Integer Arithmetic and Parametrized Linear Integer Arithmetic. Our implementation and the associated Scala compiler plug-in have been used to implement Boolean Algebra for Presburger Arithmetic synthesis.

Official source

https://infoscience.epfl.ch/entities/publication/d4b4c92a-c475-4710-87a4-df5f2cb8afca

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

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
Student Projects

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/d4b4c92a-c475-4710-87a4-df5f2cb8afca

About this result

Related concepts (32)

Modular arithmetic

In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book Disquisitiones Arithmeticae, published in 1801. A familiar use of modular arithmetic is in the 12-hour clock, in which the day is divided into two 12-hour periods. If the time is 7:00 now, then 8 hours later it will be 3:00.

Presburger arithmetic

Presburger arithmetic is the first-order theory of the natural numbers with addition, named in honor of Mojżesz Presburger, who introduced it in 1929. The signature of Presburger arithmetic contains only the addition operation and equality, omitting the multiplication operation entirely. The axioms include a schema of induction. Presburger arithmetic is much weaker than Peano arithmetic, which includes both addition and multiplication operations. Unlike Peano arithmetic, Presburger arithmetic is a decidable theory.

Implementation

Implementation is the realization of an application, execution of a plan, idea, model, design, specification, standard, algorithm, policy, or the administration or management of a process or objective. In computer science, an implementation is a realization of a technical specification or algorithm as a program, software component, or other computer system through computer programming and deployment. Many implementations may exist for a given specification or standard.

Related publications (3)

Complete Program Synthesis for Linear Arithmetic

Chat with Graph Search

Correct Transformation of High-Level Models into Time-Triggered Implementations

Heuristic NPN classification for large functions using AIGs and LEXSAT

On Sound Compilation of Reals