Paper published in a journal (Scientific congresses and symposiums)
An Automata-Theoretic Approach to Presburger Arithmetic Constraints
Wolper, Pierre; Boigelot, Bernard
1995In Lecture Notes in Computer Science, 983, p. 21-32
 

Files


Full Text
WB95.pdf
Author preprint (159.25 kB)
Download

The original publication is available at www.springerlink.com


All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
automata; Presburger arithmetic
Abstract :
[en] This paper introduces a finite-automata based representation of Presburger arithmetic definable sets of integer vectors. The representation consists of concurrent automata operating on the binary encodings of the elements of the represented sets. This representation has several advantages. First, being automata-based it is operational in nature and hence leads directly to algorithms, for instance all usual operations on sets of integer vectors translate naturally to operations on automata. Second, the use of concurrent automata makes it compact. Third, it is insensitive to the representation size of integers. Our representation can be used whenever arithmetic constraints are needed. To illustrate its possibilities we show that it can handle integer programming optimally, and that it leads to a new original algorithm for the satisfiability of arithmetic inequalities.
Disciplines :
Computer science
Author, co-author :
Wolper, Pierre  ;  Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Informatique
Boigelot, Bernard  ;  Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Informatique
Language :
English
Title :
An Automata-Theoretic Approach to Presburger Arithmetic Constraints
Publication date :
1995
Event name :
Static Analysis, Second International Symposium (SAS'95)
Event place :
Glasgow, United Kingdom
By request :
Yes
Audience :
International
Journal title :
Lecture Notes in Computer Science
ISSN :
0302-9743
eISSN :
1611-3349
Publisher :
Springer, Berlin, Germany
Volume :
983
Pages :
21-32
Funders :
F.R.S.-FNRS - Fonds de la Recherche Scientifique [BE]
Available on ORBi :
since 03 November 2010

Statistics


Number of views
83 (7 by ULiège)
Number of downloads
714 (7 by ULiège)

Scopus citations®
 
64
Scopus citations®
without self-citations
46
OpenCitations
 
42

Bibliography


Similar publications



Contact ORBi