The convex hull of a regular set of integer vectors is polyhedral and effectively computable

DOI10.1016/J.IPL.2005.04.004MaRDI QIDQ1044697zbMATH OpenOpenAlexFDO

Authors Alain Finkel, Jérôme Leroux

Publication date 18 December 2009

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0812.1951

zbMATH Keywords

approximation algorithmssymbolic representationpolyhedral convex setpresburger arithmetic

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Abstract: Number Decision Diagrams (NDD) provide a natural finite symbolic representation for regular set of integer vectors encoded as strings of digit vectors (least or most significant digit first). The convex hull of the set of vectors represented by a NDD is proved to be an effectively computable convex polyhedron.

Recommendations

• Implementation and Application of Automata
• Computing Convex Hulls by Automata Iteration
• COMPUTING CONVEX HULLS BY AUTOMATA ITERATION
• Counting the solutions of Presburger equations without enumerating them.
• scientific article; zbMATH DE number 1949644

Cites work

• scientific article; zbMATH DE number 1979550 (Why is no real title available?)
• scientific article; zbMATH DE number 1538036 (Why is no real title available?)
• Diophantine equations, Presburger arithmetic and finite automata
• Efficient Symbolic Representations for Arithmetic Constraints in Verification
• Logic and p-recognizable sets of integers
• Semigroups, Presburger formulas, and languages

Cited in

(6)

• scientific article; zbMATH DE number 1949644 (Why is no real title available?)
• Convex Hull of Arithmetic Automata
• Counting the solutions of Presburger equations without enumerating them.
• COMPUTING CONVEX HULLS BY AUTOMATA ITERATION
• Computing Convex Hulls by Automata Iteration
• Implementation and Application of Automata

Describes a project that uses

Uses Software

• FAST

This page was built for publication: The convex hull of a regular set of integer vectors is polyhedral and effectively computable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1044697)