ausblenden:
Schlagwörter:
Computer Science, Programming Languages, cs.PL,Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Logic in Computer Science, cs.LO
Zusammenfassung:
Known algorithms for manipulating octagons do not preserve their sparsity,
leading typically to quadratic or cubic time and space complexities even if no
relation among variables is known when they are all bounded. In this paper, we
present new algorithms, which use and return octagons represented as weakly
closed difference bound matrices, preserve the sparsity of their input and have
better performance in the case their inputs are sparse. We prove that these
algorithms are as precise as the known ones.
