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

DOI10.1016/J.IPL.2005.04.004zbMATH Open1184.68634arXiv0812.1951OpenAlexW2123615615MaRDI QIDQ1044697FDOQ1044697

Authors: Alain Finkel, Jérôme Leroux 

Publication date: 18 December 2009

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

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.

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

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

zbMATH Keywords

approximation algorithmssymbolic representationpolyhedral convex setpresburger arithmetic

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Cites Work

• Title not available (Why is that?)
• Semigroups, Presburger formulas, and languages
• Logic and \(p\)-recognizable sets of integers
• Title not available (Why is that?)
• Efficient Symbolic Representations for Arithmetic Constraints in Verification
• Diophantine equations, Presburger arithmetic and finite automata

Cited In (6)

• Title not available (Why is that?)
• 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

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)