Computing Convex Hulls by Automata Iteration

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

doi:10.1142/S0129054109006796

Download

Article (Scientific journals)

Computing Convex Hulls by Automata Iteration

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

2009 • In International Journal of Foundations of Computer Science, 20 (4), p. 647-667

Peer Reviewed verified by ORBi

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

DOI
10.1142/S0129054109006796

Files (1)Send to Details Statistics Bibliography Similar publications

Files

Full Text

CLW-IJFCS09.pdf

Author postprint (255.38 kB)

Download

All documents in ORBi are protected by a user license.

Send to

RIS BibTex APA Chicago Permalink X Linkedin

Details

Keywords :

convex hull; Bühi automata; (omega)-regular model checking

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 automaton-based representation of the corresponding set of real vectors. The technique is quite general and has been implemented.

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 > Electricté, électronique et informatique

Wolper, Pierre ; Université de Liège - ULiège > Services administratifs généraux > Vice-Recteur à la Recherche - Informatique (parallélisme et banques de données)

Language :

English

Title :

Computing Convex Hulls by Automata Iteration

Publication date :

2009

Journal title :

International Journal of Foundations of Computer Science

ISSN :

0129-0541

Publisher :

World Scientific Publishing Company

Volume :

Issue :

Pages :

647-667

Peer reviewed :

Peer Reviewed verified by ORBi

Available on ORBi :

since 16 November 2009

Statistics

Number of views

136 (25 by ULiège)

Number of downloads

177 (6 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

Bibliography

Bartzis, C., Bultan, T., Construction of efficient bdds for bounded arithmetic constraints (2003) LNCS, 2619, pp. 394-408. , Proc of TACAS, of, Springer
Boigelot, B., Symbolic Methods for Exploring Infinite State Spaces (1999) Collection des publications de la Faculté des Sciences Appliquées de l'Université de Liège, , Liège, Belgium
Boigelot, B., Herbreteau, F., The power of hybrid acceleration (2006) LNCS, 4144, pp. 438-451. , Proc of CAV, of, Springer
Boigelot, B., Jodogne, S., Wolper, P., An effective decision procedure for linear arithmetic over the integers and reals (2005) ACM Transactions on Computational Logic, 6 (3), pp. 614-633
Boigelot, B., Legay, A., Wolper, P., Omega-regular model checking (2004) LNCS, 2988, pp. 561-575. , Proc of TACAS, of, Springer
Boigelot, B., Rassart, S., Wolper, P., On the expressiveness of real and integer arithmetic automata (extended abstract) (1998) LNCS, 1443, pp. 152-163. , Proc of ICALP, of, Springer
Boigelot, B., Wolper, P., Representing arithmetic constraints with finite automata: An overview (2002) LNCS, 2401, pp. 1-19. , Proc of ICLP, of, Springer
Bouajjani, A., Jonsson, B., Nilsson, M., Touili, T., Regular model checking (2000) LNCS, 1855, pp. 403-418. , Proc of CAV, of, Springer-Verlag
Boudet, A., Comon, H., Diophantine equations, Presburger arithmetic and finite automata (1996) LNCS, 1059, pp. 30-43. , Proc of ICALP, of, Springer
Cantin, F., (2007) Techniques d'extrapolation d'automates: Application au calcul de la fermeture convexe, , Master's thesis, University of Liège, Belgium
Chazelle, B., An optimal convex hull algorithm in any fixed dimension (1993) Discrete & Computational Geometry, 10, pp. 377-409
Eisinger, J., Klaedtke, F., Don't care words with an application to the automatabased approach for real addition (2006) LNCS, 4144, pp. 67-80. , Proc of CAV, of, Springer
Finkel, A., Leroux, J., The convex hull of a regular set of integer vectors is polyhedral and effectively computable (2005) Information Processing Letter, 96 (1), pp. 30-35
Halbwachs, N., Proy, Y., Roumanoff, P., Verification of real-time systems using linear relation analysis (1997) Formal Methods in System Design, 11 (2), pp. 157-185
Krein, M., Milman, D., On the extreme points of regularly convex sets (1940) Studia athematica, 9, pp. 133-138
Kupferman, O., Vardi, M., Weak alternating automata are not that weak (1997) Proc. 5th Israeli Symposium on Theory of Computing and Systems, pp. 147-158. , Ramat-Gan, Israel, IEEE Computer Society Press
The Liège Automata-based Symbolic Handler (LASH), , http://www.montefiore.ulg.ac.be/∼boigelot/research/lash, Available at
Latour, L., From automata to formulas: Convex integer polyhedra (2004) Proc of LICS, pp. 120-129. , IEEE Computer Society
Legay, A., Generic Techniques for the Verification of Infinite-state Systems (2007) Collection des publications de la Faculté des Sciences Appliquées de l'Université de Liège, , http://www.montefiore.ulg.ac.be/∼legay/papers/index, Liège, Belgium, Available at
Legay, A., T(O)RMC: A tool for (omega)-regular model checking (2008) LNCS, pp. 548-551. , Proc of CAV08, Springer
J. Leroux. Algorithmique de la vérification des systèmes à compteurs. Approximation et accélération. Implémentation de l'outil FAST. PhD thesis, LSV Cachan, France, 2004
Leroux, J., A polynomial time presburger criterion and synthesis for number decision diagrams (2005) Proc of LICS, pp. 147-156. , IEEE Computer Society
Leroux, J., Convex hull of arithmetic automata (2008) LNCS, pp. 47-61. , Proc of SAS08, Springer
Leroux, J., Sutre, G., (2005) Proc of ATVA, volume 3707 of LNCS, pp. 489-503. , Flat counter automata almost everywhere! In, Springer
Löding, C., Efficient minimization of deterministic weak ω-automata (2001) Information Processing Letters, 79 (3), pp. 105-109
Minkowski, H., Geometrie der zahlen. (1914) Bulletin of American Mathematical Society, 21 (3), pp. 131-132
Miyano, S., Hayashi, T., Alternating finite automata on omega-words (1984) Theoretical Computer Science, 32, pp. 321-330
Muller, D.E., Saoudi, A., Schupp, P.E., Alternating automata, the weak monadic theory of the tree and its complexity (1986) Proc of ICALP, pp. 275-283. , Rennes, Springer-Verlag
http://www.montefiore.ulg.ac.be/∼legay/TORMC/index-tormc.html, The T(O)RMC toolset. Available at
Vardi, M., The Büchi complementation saga (2007) LNCS, 4393, pp. 12-22. , Proc of STACS, of, Springer
Wolper, P., Boigelot, B., On the construction of automata from linear arithmetic constraints (2000) LNCS, 1785, pp. 1-19. , Proc of TACAS, of, Springer