Invariant Inference with Provable Complexity from the Monotone Theory

Yotam M.Y. Feldman, Sharon Shoham

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء

ملخص

Invariant inference algorithms such as interpolation-based inference and IC3/PDR show that it is feasible, in practice, to find inductive invariants for many interesting systems, but non-trivial upper bounds on the computational complexity of such algorithms are scarce, and limited to simple syntactic forms of invariants. In this paper we achieve invariant inference algorithms, in the domain of propositional transition systems, with provable upper bounds on the number of SAT calls. We do this by building on the monotone theory, developed by Bshouty for exact learning Boolean formulas. We prove results for two invariant inference frameworks: (i) model-based interpolation, where we show an algorithm that, under certain conditions about reachability, efficiently infers invariants when they have both short CNF and DNF representations (transcending previous results about monotone invariants); and (ii) abstract interpretation in a domain based on the monotone theory that was previously studied in relation to property-directed reachability, where we propose an efficient implementation of the best abstract transformer, leading to overall complexity bounds on the number of SAT calls. These results build on a novel procedure for computing least monotone overapproximations.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفStatic Analysis - 29th International Symposium, SAS 2022, Proceedings
المحررونGagandeep Singh, Caterina Urban
ناشرSpringer Science and Business Media Deutschland GmbH
الصفحات201-226
عدد الصفحات26
رقم المعيار الدولي للكتب (المطبوع)9783031223075
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2022
الحدث29th International Static Analysis Symposium, SAS 2022 - Auckland, نيوزلندا
المدة: ٥ ديسمبر ٢٠٢٢٧ ديسمبر ٢٠٢٢

سلسلة المنشورات

الاسمLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
مستوى الصوت13790 LNCS

!!Conference

!!Conference29th International Static Analysis Symposium, SAS 2022
الدولة/الإقليمنيوزلندا
المدينةAuckland
المدة٥/١٢/٢٢٧/١٢/٢٢

All Science Journal Classification (ASJC) codes

  • !!Theoretical Computer Science
  • !!General Computer Science

بصمة

أدرس بدقة موضوعات البحث “Invariant Inference with Provable Complexity from the Monotone Theory'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا