可在www.sciencedirect.com在线获取理论计算机科学电子笔记307（2014）3-15www.elsevier.com/locate/entcs多面体双重描述中约束/生成元的有效去除吉安卢卡·阿马托1意大利基耶蒂-佩斯卡拉大学经济研究系Enea Za Pastanella3意大利帕尔马大学数学与计算机科学系摘要我们提出了一种算法，用于消除约束（分别为，生成器）从双描述框架中表示的凸多面体。新算法不是从头开始重新计算双重表示，而是试图更好地利用双重描述对中可用的信息，以便来利用已经完成的计算工作。初步的实验评估表明，可以获得显着的效率提高。特别地，可以定义一种组合算法，该算法基于合适的盈利能力算法动态地选择是否应用新算法关键词：凸多面体，双重描述，增量计算1引言凸多面体域[11]已被广泛应用于硬件/软件系统[7]的静态分析和验证，导致许多运算符的指定，这些运算符旨在计算（或以安全的方式近似当考虑双重描述（DD）框架时，这些操作符可以在大多数情况下实现（相交，凸多面体壳，时间流逝，投影，。. .）通过向可用的描述添加一些新的约束或一些新的生成器，从而直接利用Chernova的转换过程的增量性质在其他情况下（例如，可逆的图像和原像），它是1电子邮件：gamato@unich.it2电子邮件：fscozzari@unich.it3电子邮件：enea. unipr.ithttp://dx.doi.org/10.1016/j.entcs.2014.08.0021571-0661/© 2014 Elsevier B. V.保留所有权利。4G. Amato等人/理论计算机科学电子笔记307（2014）31.p++甚至可以直接和有效地修改约束和生成器表示，以便完全保留已经完成的计算工作。然而，在某些情况下，多面体上的运算符是通过删除某些约束或生成元来定义的，因此其他表示的信息内容不再是最新的，并且不容易恢复。通常的方法是简单地丢弃另一个表示，如果以后需要，从头开始重新计算。在本文中，我们提出并实验评估一种新的算法，用于删除约束（或发电机），这是为了更好地利用信息已经在输入DD对。本文的结构如下：第2节，除了回顾一些概念和符号，简要介绍了DD方法;第3节介绍了约束删除操作，定义了新算法，并显示了它与可执行规范的等价性;第4节提供了一个实验评估，并提出了新算法与基于概率算法的旧算法的集成;我们在第5节结束时讨论了约束/生成元删除的潜在应用以及删除操作对NNC多面体的扩展。2预赛两个向量a1，a2∈Rn的标积记为aTa2。针对每个向量a∈Rn，标量b∈R，其中a0，线性非严格不等式约束c=（aTx≥b）定义了Rn的一个拓扑闭的α-半空间。拓扑上封闭的凸多面体（简称多面体）由线性非严格不等式约束的有限系统定义。如果一个多面体P包含在两个半空间c=（aTx≥b）和c−=（−aTx≥ −b）中，那么我们说c是P的奇异约束，记为c∈eq（P）。 我们写con（C）来表示多面体由有限约束系统C描述的P_nR_n。形式上，我们定义P= con（C）：=.p ∈ Rn<$c=（aTx≥ b）∈C：aTp≥ b<$.一个向量r∈Rn使得r/=0是一个非空多面体P <$Rn的射线，如果对每个点p∈P和每个非负标量ρ∈R+，它保持p+ρr∈ P。空多面体没有光线。如果r和−r都是P的射线，那么我们说r是P的奇异射线（或线），并写r∈lines（P）。根据Minkowski和Weyl定理[18]，集合P <$Rn是多面体当且仅当存在基数yr和p的有限集合R，P<$Rn，分别满足0∈/R，.- 是 的.ΣΣi=1P = gen（R，P）：= Rρ + P π ∈ Rn. ρ ∈ Rr，π ∈ Rp， πi= 1.当P ≠时，我们说P由生成系统G=（R，P）描述：R和P的向量分别是P的射线和点由于Motzkin等人的双重描述方法。[17]，通过利用对偶原理，允许结合上述两种方法G. Amato等人/理论计算机科学电子笔记307（2014）35.转换过程从另一个开始计算每个表示。若P= con（C）= gen（G），则称（C，G）是多面体的DD对P. 如果C和G都是最小的，则DD对是最小形式的，即， 它们不包含冗余元件。4在多面体P的极小形式的DD对（C，G）中，每个非奇异约束c =（aTx≥b）∈ C定义P的一个刻面，由F：={p∈ P|aTp = b}。我们说非奇异约束c，cJ∈ C在P中相邻，记为相邻P（c，cJ），如果对应的小平面相邻。在[3]中定义了面之间的相邻性转换过程，表示为（Cout，Gout）←转换（Cin），将输入约束系统Cin映射到最小形式的输出DD对（Cout，Gout）：从表示整个向量空间的初始DD对（Cuniv，Guniv）开始，该过程递增地添加Cin中的每个约束，如上所述。我们将写（Cmin，Gmin）<$simplify（C，G）来表示简化步骤，它通过从输入DD对（C，G）中删除冗余来执行最小形式当将生成器添加到DD对时，用于增量约束添加的算法（和转换过程）可以适于处理对偶情况2.1多面体的低层编码在DD框架中，Rn中的多面体一般通过均匀化映射到Rn+1中的多面体锥：已知的约束项与额外的空间维数ε相关联，并添加正性约束pos=（ε≥0）均匀化允许更统一地处理约束和生成器（例如，多面体的所有点都成为圆锥的射线）。基于Cherelova算法[8，9，10]的转换过程的基本步骤基于具有约束c的射线的标量积的符号（G0中的那些是约束c的饱和子），射线G的集合被划分成三个分量G+、G0、G-;新的生成器系统被计算为GJ：=G+<$G0<$G <$，其中G：=. （aTr+）r−−（aTr−）r+r+∈ G+，r−∈ G−，相邻P（r+，r−）<$.利用对偶性，从约束的邻接性定义出发，得到了射线的邻接性定义。实现采用不同的策略来计算邻接关系和检测冗余：一种常见的方法是系统地维护饱和信息[13，15，19]。在下文中，为了简化说明，我们将根据多面体来指定和描述算法，使得到多面体锥的映射和正性约束的特殊处理将是透明的。4实际实现通常基于更强的极小概念，特别考虑奇异约束和生成器（即，等式和线）。6G. Amato等人/理论计算机科学电子笔记307（2014）33DD方法的约束/生成器移除在本节中，我们提出了一个新的算法，用于从最小形式的DD对中删除一组约束。注意，通过利用多面体表示的对偶性质，相同的算法可以容易地适应于移除一组生成元的情况首先要注意的是，从多面体中移除奇异约束并没有一个定义明确的概念，如下面的例子所示。例3.1考虑多面体P={0}<$R2（二维向量空间的原点）。这个多面体可以用约束系统C1={x= 0，y = 0}和C2={x= 0，x +y= 0}来描述，它们都是极小形式的。根据所选择的句法表示，去除约束x= 0导致计算两个不同的多面体。为了避免上述问题，在下文中，我们将仅考虑去除非奇异约束，即， 我们将假设最小形式的输入DD对中的所有等式约束保持不变。请注意，在许多实际情况下，这样的假设是明确合理的;例如，对于多面体上的加宽操作，已经提出了标准加宽的变体，其中每当多面体的α维数发生变化时，都使用更精确的多面体凸包[4]。直接的方法（见算法1），以实现约束re-moval需要计算的生成器系统从一组Ckept的约束，还没有被删除，使用的转换过程由Chernova。在基于增量算法的同时，该方法从头开始重新计算新的发电机系统，完全忽略输入DD对的发电机系统分量在下文中，我们将算法1称为朴素算法。算法1朴素地移除一组约束要求：一个DD对（Cin，Gin）以最小形式定义Pin;要求：一个约束集Crem Cin，使得Crem eq（Pin）= C。确保：最小形式的DD对（Cout，Gout）定义为Pout= con（Cin\Crem）。开始← Cin\C rem（Cout，Gout）←conversion（Ckept）端新算法的目标是尽可能地利用输入DD对中编码的信息，以便利用已经完成的计算工作。出于这个原因，在下文中我们将其称为增量算法。为了了解这种增量算法应该如何工作，让我们考虑图1左侧的两个多面体作为简单的例子。首先考虑多面体P1，它是一个多面体，其DD对由G. Amato等人/理论计算机科学电子笔记307（2014）37yDC BHGOP1一E FP2XyDOP3P4XFig. 1.删除约束的示例四个约束和四个顶点。假设我们需要移除对应于面BC的约束，以便获得三角形OAD。当根据生成元进行推理时，BC的移除对应于顶点D的添加（这也导致顶点B和C变得冗余）。特别地，顶点D是通过组合定义面OC和AB的约束而获得的生成器，这些约束是与被移除的约束相邻的约束;而且，生成器D违反了被移除的约束。现在考虑平面P2，假设我们需要去除对应于小平面GH的约束;通过这样做，我们得到由两个顶点（E和F）和两条射线（沿着方向EH和FG）描述的无界多面体。当根据生成器进行推理时，我们需要添加这两条射线（这也会导致顶点H和G变得冗余）。如前所述，这两条光线可以被视为源自与被移除的约束相邻的约束（小平面EH和F G）;而且，它们违反了被移除的约束。在讨论图1中的示例时所做的观察导致了Al出租m2的出现。首先在Cadj中选择与至少一个被移除的约束相邻的那些约束：这些约束被添加到奇异约束以形成约束系统C conv，其被馈送到Cherkova然后，我们将违反被移除的约束的生成器添加到G中：5这些被添加到输入生成器表示G中以获得输出多面体的生成器表示。最后，DD对被放置在最小形式的过程下面的结果说明了这两种算法的等价性。定理3.2（算法2正确）算法1和算法2计算的DD对表示同一个多面体锥。与算法1相比，算法2也需要应用转换过程，但这适用于可能较小的描述（C转换）：根据输入，这可能会导致显著的效率增益，尽管存在导致效率损失的极端情况。请注意，调用“simplify”的成本5在图1中，对于P1，由（Cconv，Gconv）描述的多面体（P2）在右手侧示出为P3（分别地，P4）;Gadd中的生成器突出显示。8G. Amato等人/理论计算机科学电子笔记307（2014）3Cadj←c∈ C保持布拉奇∈Crem. （c，c）中的相邻P算法2增量删除一组约束要求：与算法1相同。确保：与算法1相同。开始Ceq← Cineq（Pin）Ckept←. Cin\Crem.JJCconv←CeqCadj（Cconv，Gconv）←转换（Cconv）Gadd← {g ∈ Gconv|c∈ Crem.g违反c}（Cout，Gout）←simplify（Ckept，GinGadd）端值得强调的是，在描述新算法时，我们的主要目标是提供一个可执行的过程规范，用于删除约束，从而更好地利用输入DD对中已有的信息。也许，这样的规范可以进一步优化速度。例如，对过程的最后调用相反，专门的实现方式可以区分Gin中的生成器，因为已知没有使所移除的约束饱和的那些生成器不是冗余的。目前正在研究的进一步优化的另一个机会是基于以下观察。当使用算法2去除许多约束时，所有相邻的约束被合并到单个约束系统Cconv中，并从头开始转换以获得Gconv。一个全面的增量- 谈话方法更愿意为每个被移除约束计算相邻约束的单独子系统并执行许多转换。先验地，不清楚上述两个选项中的哪一个可能更有效：一方面，完全增量方法处理较小的子系统;另一方面，由于一些相邻的约束将出现在多个子系统中，因此一些计算将无用地重复多次，并且总体转换成本可能更高。一个有趣的折衷方案是将待移除的约束集划分为仅具有几个共同的相邻约束的较小子集4实验评价在表1和表2中，我们报告了初步实验评估的部分结果，旨在比较增量算法与朴素算法的效率。6我们考虑了ppl lcdd工具的一些例子，它是帕尔马多面体库的一部分[6]。原始的ppl lcdd工具将约束作为输入（分别为，生成器）表示并产生对偶生成器（分别，约束）表示，从而6测试是在配备Intel Core i7- 3632 QM CPU、16 GB RAM和运行GNU/Linux的笔记本电脑上进行的。G. Amato等人/理论计算机科学电子笔记307（2014）39删除约束单纯性复合物增量补偿测试大小REM坐SP时间conv添加坐SP时间ccc6.ext21115102G2G2G14.5万美元十四万九千150Kt/Ot/ot/o16557715105K8M42M46828K81K0.0000.1000.652cut32-16.ext36815102G2G2G126K88K100Kt/ot/ot/O16497115107K53M2G63954K263K0.0000.84025.076cyclic14-8.ext240151022M23M26M72K75K85K0.6280.6280.76082339115542K63K980K3116K26K0.0000.0040.040reg600-5-m.ext2360151024M24M25M3M3M3M2.9002.8922.932611192415374千388K423K5K10K37K0.0520.0480.060cyclic17-8.ine171510二十八万五千17K562K275720.0080.0000.004171381651129720K50K1845K3K1570.0120.0040.000kkd38-6.ine38151028M13M4M48K29K14K0.6120.2800.09689924460K46K30K1372552850.0000.0000.000mit31-20.ine311510131M小行星767K7K22K4K8061.2600.0240.00431272236511231131234M3M26K141K38K4K1.5920.0680.036sampleh8.ine6615102.66亿190M116M263K212K156K6.7245.0523.03226464926619403361190M258M190M34K278K378K1.3203.6362.832trunc10.ine112151067M67M63M193K型191K型188千1.6681.6561.596215710211981242764K15M62M6K56K313K0.0120.2921.580表1删除约束：朴素vs增量解决面/顶点枚举问题。对于我们的实验，我们修改了工具，以便在计算DD对之后，它删除了一些约束（分别为，在表1中，我们考虑了去除1、5和10个约束的情况。出于空间原因，我们省略了所有较小的测试以及几个测试，这些测试是其他测试的微小变化（通常是对偶）;我们还省略了大多数较大的测试，因为它们的计算成本远远超过了所选择的超时阈值。前两列（'test' 和'size' ）报告基准的名称和输入表示的大小。因此，名为“ccc6.ext”的测试用于由211个约束描述的输入多面体（当在实现级别计算约束时，我们包括正性约束）。对于每个测试，我们有三行，对应于删除的约束的不同数量，在列'rem'中报告。接下来的三列是对朴素算法的测量：除了计时（以秒为单位），我们还在列'sat'中报告饱和包含测试的数量，在列'sp'中报告标量积的数量。10G. Amato等人/理论计算机科学电子笔记307（2014）3元素K、M和G代表103、106和109;当使用这些缩放元素时，数字向上舍入（即，我们提供上限）。每次调用G. Amato等人/理论计算机科学电子笔记307（2014）311拆卸发电机单纯性复合物增量补偿测试大小REM坐SP时间conv添加坐SP时间ccc6.ext321510438K67K8K3K2K6900.0080.0040.00031272240522150770K十六万九千20K16K9K3K0.0160.0040.000cut32-16.ext321510773K126K13K4K2K8390.0120.0040.000312722415293692M321K35K18K11K4K0.0240.0080.000cyclic14-8.ext14151021K1681231472320.0000.0000.00013948410649K5842702K222820.0040.0000.000reg600-5-m.ext600151015M15M15M713K小行星704K692K1.0161.0080.97217548916691196M6M6M10K46K81K0.0720.0880.096cyclic17-8.ine9351510小行星741M730M730M930K909K915Kt/Ot/ot/o8396935278K3M55M3K24K178K0.0000.0801.644kkd38-6.ine2521510小行星629K622K614K32K31K31K0.0720.0680.06861316411103K7K8K2K3K3K0.0000.0040.004mit31-20.ine1855315103G3G3G118K118K118Kt/Ot/ot/o1971302330354千41M1G57K120K242K0.0320.756t/Osampleh8.ine138651510915M913M917M1M1M1Mt/ot/ot/O9275311551130K四四十七万29M14K210K801K0.0200.0801.248trunc10.ine29015102G390M小行星394713K220K270K18.0002.5082.7241019191341716K39K182K41111K11K0.0000.0040.008表2删除生成器：简单vs增量在删除算法中，超时设置为30秒的CPU时间;如果超时过期，我们将在'time'列中报告接下来的五列报告了在增量算法上采取的措施。除了上面描述的'sat'，'sp'和'time'列之外显著的时间改进（超过0.2秒）使用下划线突出显示表2显示了移除1、5和10个发生器时相同测试获得的结果。读者需要注意的是，在这种情况下，有些列必须进行双重解释;即，所报告的测量值允许进行一些观察：• 朴素删除算法虽然在许多测试中表现得相当好，但有时会导致高计算成本，导致表1中的6个超时和表2中的9个超时;• 由于我们删除了相对较少的约束或生成器，因此增量算法通常执行得更好：12G. Amato等人/理论计算机科学电子笔记307（2014）3Cadj←c∈ C保持布拉奇∈Crem. （c，c）中的相邻P一次，在表2中;• 偶尔存在增量算法比原始算法慢的情况（例如，参见表1中的测试“cyclic 17 -8.ine”和“mit 31 -20.ine”的行）;这是因为从输入多面体中移除的约束与几乎所有保留的约束相邻，如通过比较列“conv”中的值可以看出的C conv的基数）与“size”和“rem”的区别（即，（thecardinali tyofCkept）.显然，上述观察结果适用于所考虑的测试，这些测试并不意味着完全代表在其他特定应用中可以找到的用于删除约束（或生成器）的典型模式。特别是，大多数被考虑的测试的特点是两个表示中的一个比另一个小得多：这通常会导致两个转换中的一个需要更长的计算时间。4.1计算策略的动态选择上述观察表明，通过将朴素算法和增量算法组合成第三种算法，可以获得效率上的有趣平衡对于去除约束的情况，组合算法被示为算法3：它使用帮助函数盈利能力测试通常比较约束系统Cconv和Ckept的大小，如果Cconv不够小，则回到原始计算。由于盈利性检查是基于输入描述和中间结果的，我们将算法3称为约束去除的内省算法。算法3内省移除一组约束要求：与算法1相同。确保：与算法1相同。开始Ceq← Cineq（Pin）Ckept←. Cin\Crem.JJCconv←CeqCadj如果pr（Cconv，Ckept），则（Cconv，Gconv）←转换（Cconv）Gadd← {g ∈ Gconv|c∈ Crem.g违反c}（Cout，Gout）←simplify（Ckept，GinGadd）其他//回退到朴素计算（Cout，Gout）←conversion（Ckept）end if端G. Amato等人/理论计算机科学电子笔记307（2014）313删除约束单纯性复合物内省的比较测试大小REM坐SP时间conv添加坐SP时间ccc6.ext21115102G2G2G14.5万美元十四万九千150Kt/Ot/ot/o16557715105K8M42M46828K81K0.0000.1000.656cut32-16.ext36815102G2G2G126K88K100Kt/ot/ot/O16497115107K53M2G63954K263K0.0000.83224.968cyclic14-8.ext240151022M23M26M72K75K85K0.6320.6640.78482339115542K63K980K3116K26K0.0000.0040.040reg600-5-m.ext2360151024M24M25M3M3M3M2.9442.8883.008611192415374千388K423K5K10K37K0.0480.0480.060cyclic17-8.ine171510二十八万五千17K562K275720.0080.0000.00017138---286K17K1612K275720.0120.0040.000kkd38-6.ine38151028M13M4M48K29K14K0.6240.2800.09289924460K46K30K1372552850.0000.0000.000mit31-20.ine311510131M小行星767K7K22K4K8061.4040.0200.004312722---131M小行星767K8K22K4K8060.9520.0360.020sampleh8.ine6615102.66亿190M116M263K212K156K6.9365.2483.052264649266--190M190M116M34K212K156K1.4084.8162.744trunc10.ine112151067M67M63M193K型191K型188千1.6521.6801.608215710211--764K67M63M6K191K型188千0.0161.6681.588表3天真与内省：消除限制在表3中，我们显示了通过内省算法获得的结果，该算法用于去除表1的相同测试的约束，并具有以下试验性算法：可优化（Cconv ，C保持）：=.#Cconv1≤2# C 保持平衡由于盈利能力检查可以有效地实现，当回退到朴素算法时，内省算法引起的开销非常小（回退到通过以粗体显示列'conv'的值而列'add'根本没有值来报告注意，在一些情况下（例如，当在测试“sampleh8.ine”和“trunc10.ine”中移除多于一个约束时），逻辑学导致实际上不需要的回退，可能阻止更显著的效率增益。因此，很明显，利润率算法的实现应该针对手头的具体应用进行调整，并且通常不能确保减少14G. Amato等人/理论计算机科学电子笔记307（2014）3计算时间。G. Amato等人/理论计算机科学电子笔记307（2014）315.Σ结合朴素算法和增量算法的另一种方法是利用多个处理单元的可用性，并在不同的线程中运行这两种算法，只要两者中的任何一个终止，就立即停止5讨论标准加宽[11，14]可能是最知名的操作， 凸多面体的域，其实现是基于去除约束。使用加宽“F”，单调算子“F”（抽象语义函数）的后定点可以作为递增迭代序列的极限获得，计算如下：Pi+1：= Pi<$PiF（Pi）。因此，加宽是用于保留DD对的约束去除算法的应用的良好候选，例如本文中提出的算法，因为在计算下一个参数P i +1时使用P i的两种表示：在计算第二个参数中的凸多面体外壳""时使用生成器;在计算加宽本身时使用约束。当使用[2]这样的框架时，这些好处更加相关，其中每个程序点都可能是一个加宽点，[1]，其中加宽与缩小交织在一起，每个循环可能会被分析多次。除了标准的加宽之外，通过查阅现有的文献，可以发现约束或生成器移除的这些都可以被认为是本文中提出的算法的潜在应用，并可能是进一步调查的主题，以评估新算法的盈利能力所考虑的上下文。Min′e[16]考虑了推断程序属性成立的条件的问题所提出的方法被建模为一个多面体分析计算下近似的向后语义的程序。在此设置中，约束移除用于实现向后递归测试的安全欠近似。类似地，为了确保欠近似的收敛性，[16]定义了一个较低的加宽，它类似于计算过近似时使用的标准通过利用多面体表示的对偶性，这种新的加宽可以通过从多面体中移除一些生成元来轻松实现，因此可以从更有效的生成元移除算法Fhrese [12]说明了两种技术，旨在管理多面体计算中约束描述的复杂性。第一种技术旨在限制用于表示约束的任意精度整数系数中使用的位数;为此，首先识别具有巨大系数的约束，然后在多面体描述中用具有较小系数的其他约束替换该替换步骤可以通过组合递减控制来实现16G. Amato等人/理论计算机科学电子笔记307（2014）3.Σ本文提出的一种新的约束消除算法，与通常的增量约束相加，从而得到一个同时具有两种最新表示的多面体。第二种技术是一种更直接的技术，因为它通过删除不太重要的约束来限制多面体表示中的约束数量。约束选择的几个变化提出（体积，松弛，角度），然后应用在两个可选的程序：一个建设过程，其中最重要的约束被添加到宇宙多面体;和解构过程，其中最不重要的约束从起始多面体中删除取决于获得的约束的最终数量，递减约束去除算法可能变得相对于递增约束添加具有竞争力。本文只考虑拓扑闭多面体。不一定闭合（NNC）多面体可以通过允许约束描述中的严格不等式来指定（分别为，生成器描述中的闭合点[5]）。当试图在NNC多面体的域上正确定义约束或生成元移除算子时，应该注意一些问题。首先，DD对必须完全最小化，如[5]中所提出的，以去除各种冗余。然而，完全最小化是不够的，如以下示例所示例5.1考虑由约束系统C={ 0≤x≤ 1， 0≤y≤ 1，x +y 2}定义的NNC多面体P <$R2。注意，P也可以由约束系统CJ={ 0≤x≤ 1， 0≤y≤ 1，x + 2y 3}定义，并且C和CJ都是最小形式。根据所选择的句法表示，去除约束x≤1导致不同的NNC多面体的计算。为了避免上述问题，一种可能性是指定从NNC多面体中移除非严格约束是通过首先将约束收紧为严格约束然后移除严格约束来获得的。在上面的例子中，我们首先添加严格约束x<1（这样约束x+y<2和x+ 2y 3就变得多余，并从输入DD对中丢弃），然后将其删除，从而获得NNC多面体PJ= con{ 0≤x， 0≤y≤1}。 生成器删除可以设计一个双重示例：在这种情况下，解决方法是在删除闭包点之前将其转换为点。我们计划将本文中提出的算法扩展到NNC多面体的情况下，基于这些修改的规范。确认Enea Za Zanella的工作得到了Istituto Nazionale di Alta Matematica的GruppoNazionale per il Calcolo Scienti Fico的支持。引用[1] 阿马托湾，巴西-地和F. Scozzari，局部扩大和缩小，在：F。Logozzo和M. Fahndrich，editors，StaticAnalysis ， 20th International Symposium ， SAS 2013 ， Lecture Notes in Computer Science7936（2013），pp. 25比42G. Amato等人/理论计算机科学电子笔记307（2014）317[2] 阿皮尼斯，K.，H. Seidl和V. Vojdani，如何结合非单调方程组的加宽和缩小，在：H.- J. Bohem和C.Flanagan ， editors ， Proceedings of the 34th ACM SIGPLAN Conference on Programming LanguageDesign and Implementation（2013），pp.377-386.[3] Bachem ， A.和 M.Groúotschel ， Charaterizationofadjacencyoffacesofpolyhedra ，MathematicalProgramming Study 14（1981），pp. 1-22[4] 巴尼亚拉河P. M.希尔，E. Ricci和E. Za Zaganella，Precise widening operators for convex polyhedra，Science of Computer Programming58（2005），pp.28比56[5] 巴尼亚拉河P. M. Hill和E. Za Zaghanella，不一定闭合凸多面体和双重描述方法，计算的形式方面17（2005），pp.222-257[6] 巴尼亚拉 河P. M. Hill和E. Za Zaghanella，The Parma Polyhedra Library：Toward a complete set ofnumerical abstractions for the analysis and verification of hardware and software systems，Science ofComputer Programming72（2008），pp.3-21[7] 巴尼亚拉河P. M. Hill和E. Za Zananella，多面体计算在硬件和软件系统分析和验证中的应用，理论计算机科学410（2009），pp. 4672- 4691[8] Chernovova，N.五、Algorithm for finding a general formula for the non-negative solutions of thesystem of linear equations ， U.S.S.R. Computational Mathematics and Mathematical Physics4（1964），pp. 151比158[9] Chernovova ， N. 五 、 Algorithm for finding a general formula for the non-negative solutions of thesystem of linear inequalities ， U.S.S.R. Computational Mathematics and Mathematical Physics5（1965），pp. 228- 233。[10] Chernovova，N.五、发现线性规划问题所有解的集合的算法，苏联计算数学和数学物理8（1968），pp.282-293。[11] Cousot，P. and N. Halbwachs，自动发现程序变量之间的线性约束，在：第五届年度ACM编程语言原理研讨会会议记录（1978年），pp。84比96[12] Frehse，G.，PHAVer：混合动力系统过去HyTech的验证，在：M。莫拉里和L. Thiele，editors，Hybrid Systems：Computation and Control：Proceedings of the 8th InternationalWorkshop（HSCC 2005），Lecture Notes in Computer Science3414（2005），pp.258-273。[13] 福田， K. 和 A. 普罗登， 双 描述方法 重新审视， 在： M. 德扎R. 欧拉和Y. Manoussakis ， editors ， Combinatorics and Computer Science ， 8th Franco-Japanese and 4thFranco-Chinese Conference ， Brest ， France ， July 3-5 ， 1995 ， Selected Papers ， Lecture Notes inComputer Science1120（1996），pp. 91-111[14] Hal bwa chs，N.，Grenoble大学第三个信息周期方案，Grenoble，法国（1979年）。[15] Le Verge，H.，关于Chernova算法的说明[16] 小姐， 一、推断 充足的 条件 与 巴克瓦研发公司 波列赫德拉勒 在应用程序下， 第四届数值和符号抽象域国际研讨会论文集（NSAD'1 2 ） ， 理 论 计 算 机 科 学 电 子 笔 记 （ E N T C S ） 2 8 7 （ 2 0 1 2 ） ，p p . 八九比一百[17] Motzkin，T.美国，H. Rai loua，G. L. Thompson和R. M. Thrall，双重描述方法，在：H。W. Kuhn和A.W.塔克，编辑，贡献的理论游戏51比73[18] Stoer，J. and C. Witzgall，[19] Zolotykh，N.是的，新修改的双重描述方法构造的骨架多面体锥，计算数学和数学物理52（2012），页。146比156
我的内容管理
展开
