Abstrakt. Vi introducerar begreppet "δ-fullständiga beslutsförfaranden" för att lösa SMT-problem över de verkliga talen, i syfte att hantera ett brett spektrum av icke-linjära funktioner inklusive transcendentala funktioner och lösningar av Lipschitz-kontinuerliga ODE. Med tanke på ett SMT-problem och ett positivt rationellt antal δ avgör ett fullständigt beslutsförfarande antingen att det inte är tillfredsställande eller att "δ-svagheten" av ί är tillfredsställande. Här, den δ-försvagning av  och är en variant av  och som gör det möjligt δ-bundna numeriska perturbationer på  och. Vi bevisar att det finns fullständiga beslutsförfaranden för avgränsade SMT över reals med funktioner som nämns ovan. För funktioner i typ 2 komplexitet klass C, under milda antaganden, är det avgränsade δ-SMT problemet i NP C. Detta står i skarp kontrast till de välkända obeslutbarhet resultat. δ-Complete-beslutsförfaranden kan utnyttja skalbara numeriska metoder för hantering av icke-linjäritet, och vi föreslår att detta begrepp används som ett idealiskt krav för numeriskt styrda beslutsförfaranden. Som ett konkret exempel analyserar vi formellt DPLL ICP-ramverket, som integrerar Interval Constraint Propagation (ICP) i DPLL(T), och fastställer nödvändiga och tillräckliga villkor för dess fullständighet. Vi diskuterar praktiska tillämpningar av δ-fullständiga beslutsförfaranden för korrekturkritiska ansökningar, inklusive formell kontroll och bevisupptagning.
Ett fullständigt beslutsförfarande för verklig aritmetik användes för att kontrollera säkerheten hos icke-linjära hybridsystem i REF.
Delta-Complete Decision Procedures for Satisfiability over the Reals
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}