In this paper, we present an algorithm for solving directly linear Diophantine systems of both equations and inequations. Here directly means without adding slack variables for encoding inequalities as equalities. This algorithm is an extension of the algorithm due to Contejean and Devie (1994) for solving linear Diophantine systems of equations, which is itself a generalization of the algorithm of Fortenbacher (Clausen and Fortenbacher, 1989) for solving a single linear Diophantine equation. All the nice properties of the algorithm of Contejean and Devie are still satisfied by the new algorithm: it is complete, i.e. provides a (finite) description of the set of solutions, it can be implemented with a bounded stack, and it admits an incremental version. All of these characteristics enable its easy integration in the CLP paradigm. [References: 30]
展开▼
机译:在本文中,我们提出了一种直接求解方程和不等式的线性Diophantine系统的算法。这里直接意味着不添加用于将不等式编码为等式的松弛变量。该算法是Contejean和Devie(1994)用于求解线性Diophantine方程组的算法的扩展,它本身是Fortenbacher(Clausen and Fortenbacher,1989)用于求解单个线性Diophantine方程的算法的推广。新算法仍然满足Contejean和Devie算法的所有优良特性:它是完整的,即提供(一组)有限的解决方案描述,可以用有界堆栈实现,并且允许增量版。所有这些特征使其易于集成到CLP范例中。 [参考:30]
展开▼