Computing Convex Hulls by Automata Iteration

Cantin, François; Legay, Axel; Wolper, Pierre

doi:10.1007/978-3-540-70844-5_12

Download

Paper published in a journal (Scientific congresses and symposiums)

Computing Convex Hulls by Automata Iteration

Cantin, François; Legay, Axel; Wolper, Pierre

2008 • In Lecture Notes in Computer Science, 5148, p. 112-121

Peer reviewed

Permalink
https://hdl.handle.net/2268/1158

DOI
10.1007/978-3-540-70844-5_12

Files (2)Send to Details Statistics Bibliography Similar publications

Files

Full Text

proceedings.pdf

Author postprint (416.65 kB)

The original publication is available at www.springerlink.com

Download

Full Text Parts

springer-fulltext.pdf

Publisher postprint (444.91 kB)

The original publication is available at www.springerlink.com

Request a copy

All documents in ORBi are protected by a user license.

Send to

RIS BibTex APA Chicago Permalink X Linkedin

Details

Keywords :

Convex-hull; finite automata

Abstract :

[en] This paper considers the problem of computing the real convex hull of a finite set of n-dimensional integer vectors. The starting point is a finite-automaton representation of the initial set of vectors. The proposed method consists in computing a sequence of automata representing approximations of the convex hull and using extrapolation techniques to compute the limit of this sequence. The convex hull can then be directly computed from this limit in the form of an automatonbased representation of the corresponding set of real vectors. The technique is quite general and has been implemented. Also, our result fits in a wider scheme whose objective is to improve the techniques for converting automata-based representation of constraints to formulas.

Disciplines :

Computer science

Author, co-author :

Cantin, François ; Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Réseaux informatiques

Legay, Axel ; Université de Liège - ULiège > Dept. d'electricté, électronique et informatique > informatique

Wolper, Pierre ; Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Informatique (parallélisme et banques de données)

Language :

English

Title :

Computing Convex Hulls by Automata Iteration

Publication date :

July 2008

Event name :

13th International Conference on the Implementation and Applications of Automata, CIAA 2008

Event place :

San Francisco, United States - California

Event date :

July 21-24, 2008.

Audience :

International

Journal title :

Lecture Notes in Computer Science

ISSN :

0302-9743

eISSN :

1611-3349

Publisher :

Springer, Berlin, Germany

Volume :

5148

Pages :

112-121

Peer reviewed :

Peer reviewed

Additional URL :

http://www.springerlink.com/content/d25223l0nh07g6j6/?p=097ae8f595334ba6996a241de5bdde58&o=0

Available on ORBi :

since 26 November 2008

Statistics

Number of views

174 (42 by ULiège)

Number of downloads

171 (26 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

OpenAlex citations

Bibliography

Bartzis, C., Bultan, T.: Construction of efficient bdds for bounded arithmetic constraints. In: Garavel, H., Hatcliff, J. (eds.) TACAS 2003. LNCS, vol. 2619, pp. 394-408. Springer, Heidelberg (2003)
Boigelot, B.: Symbolic Methods for Exploring Infinite State Spaces. Collection des publications de la Faculté des Sciences Appliquées, Liège (1999)
Boigelot, B., Herbreteau, F.: The power of hybrid acceleration. In: Ball, T., Jones, R.B. (eds.) CAV 2006. LNCS, vol. 4144, pp. 438-451. Springer, Heidelberg (2006)
Boigelot, B., Jodogne, S., Wolper, P.: An effective decision procedure for linear arithmetic over the integers and reals. ACM Transactions on Computational Logic 6(3), 614-633 (2005)
Boigelot, B., Legay, A., Wolper, P.: Omega-regular model checking. In: Jensen, K., Podelski, A. (eds.) TACAS 2004. LNCS, vol. 2988, pp. 561-575. Springer, Heidelberg (2004)
Boigelot, B., Rassart, S., Wolper, P.: On the expressiveness of real and integer arithmetic automata. In: Larsen, K.G., Skyum, S., Winskel, G. (eds.) ICALP 1998. LNCS, vol. 1443, pp. 152-163. Springer, Heidelberg (1998)
Boigelot, B., Wolper, P.: Representing arithmetic constraints with finite automata: An overview. In: Stuckey, P.J. (ed.) ICLP 2002. LNCS, vol. 2401, pp. 1-19. Springer, Heidelberg (2002)
Bouajjani, A., Jonsson, B., Nilsson, M., Touili, T.: Regular model checking. In: Emerson, E.A., Sistla, A.P. (eds.) CAV 2000. LNCS, vol. 1855, pp. 403-418. Springer, Heidelberg (2000)
Boudet, A., Comon, H.: Diophantine equations, presburger arithmetic and finite automata. In: Proc of ICALP. LNCS, vol. 1159, pp. 30-43. Springer, Heidelberg (1996)
Cantin, F.: Techniques d'extrapolation d'automates: Application au calcul de la fermeture convexe. Master's thesis, University of Liège, Belgium (2007)
Cantin, F., Legay, A., Wolper, P.: Computing convex hulls by automata iteration. Technical report, University of Liège (2008), http://www.montefiore.ulg.ac.be/∼legay/papers/ciaa08rep.pdf
Chazelle, B.: An optimal convex hull algorithm in any fixed dimension. Discrete & Computational Geometry 10, 377-409 (1993)
Eisinger, J., Klaedtke, F.: Don't care words with an application to the automata-based approach for real addition. In: Ball, T., Jones, R.B. (eds.) CAV 2006. LNCS, vol. 4144, pp. 67-80. Springer, Heidelberg (2006)
Finkel, A., Leroux, J.: The convex hull of a regular set of integer vectors is polyhedral and effectively computable. IPL (96-1), 30-35 (2005)
The Liège Automata-based Symbolic Handler (LASH), http://www.montefiore.ulg.ac.be/∼boigelot/research/lash/
Latour, L.: From automata to formulas: Convex integer polyhedra. In: Proc. of LICS, pp. 120-129. IEEE Computer Society, Los Alamitos (2004)
Leroux, J.: Algorithmique de la vérification des systèmes à compteurs. Approximation et accélération. Implémentation de l'outil FAST. PhD thesis, Cachan (2004)
Leroux, J.: A polynomial time presburger criterion and synthesis for number decision diagrams. In: Proc of LICS, pp. 147-156. IEEE Computer Society, Los Alami-tos (2005)
Leroux, J., Sutre, G.: Flat counter automata almost everywhere! In: Peled, D.A., Tsay, Y.-K. (eds.) ATVA 2005. LNCS, vol. 3707, pp. 489-503. Springer, Heidelberg (2005)
Löding, C.: Efficient minimization of deterministic weak automata. IPL (79-3), 105-109 (2001)
Muller, D.E., Saoudi, A., Schupp, P.E.: Alternating automata, the weak monadic theory of the tree and its complexity. In: Proc of ICALP, Rennes, pp. 275-283. Springer, Heidelberg (1986)
Safra, S.: Exponential determinization for ω-automata with strong-fairness acceptance condition. In: Proc. of POPL, Victoria (May 1992)
The T(O)RMC toolset, http://www.montefiore.ulg.ac.be/∼legay/TORMC/ index-tormc.html
Vardi, M.: The büchi complementation saga. In: Thomas, W., Weil, P. (eds.) STACS 2007. LNCS, vol. 4393, pp. 12-22. Springer, Heidelberg (2007)