Abstrakt. Convex polyhedra fångar linjära samband mellan variabler. De används i statisk analys och optimerar sammanställning. Deras höga uttrycksfullhet används dock knappt för att verifiera på grund av deras kostnader, ofta oöverkomliga när antalet berörda variabler ökar. Vårt mål i den här artikeln är att sänka denna kostnad. Oavsett den valda representationen av polyhedra - som begränsningar, som generatorer eller som båda - dyra operationer är oundvikliga. Denna kostnad beror främst på fyra operationer: omvandling mellan representationer, baserat på Chernikova algoritm, för bibliotek i dubbel beskrivning; konvex skrov, projektion och minimering, i begränsningar-endast representation av polyhedra. Bibliotek som drivs över generatorer ådrar sig exponentiella kostnader på fall som är vanliga i programanalys. I Verimag Polyhedra Library undveks denna kostnad genom en begränsningsbar representation och att reducera alla operationer till variabla projektioner, klassiskt utförda av Fourier-Motzkin eliminering. Eftersom Fourier-Motzkin genererar många överflödiga begränsningar, minimering var dock mycket dyrt. I den här artikeln undviker vi denna fallgrop genom att uttrycka projektion som ett parametriskt linjärt programmeringsproblem. Detta förbättrar effektiviteten dramatiskt, främst eftersom det undviker efterbehandling minimering. Vi visar hur vårt nya tillvägagångssätt kan vara upp till storleksordningar snabbare än det tidigare tillvägagångssättet som implementerades i Verimag Polyhedra Library som endast använder begränsningar och Fourier-Motzkin eliminering, och på samma sätt som den konventionella dubbla beskrivningen, som genomförs i välkända bibliotek. Nyckelord: Polyhedra, Parametric Linear Programming, Projection Static analysators etablera giltigheten av påståenden i program genom att upptäcka induktiva invarianter som medför dem. Analyzers baserade på abstrakt tolkning anser invarianter inom en abstrakt domän [5]. Varianter på numeriskt värde
Den nuvarande versionen av VPL är baserad på en parametrisk linjär programmeringslösare implementerad i godtycklig precision aritmetik i OCaml REF.
Scalable Minimizing-Operators on Polyhedra via Parametric Linear Programming
{'venue': 'SAS', 'journal': None, 'mag_field_of_study': ['Computer Science']}