What else is decidable about integer arrays?

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F08%3APU78080" target="_blank" >RIV/00216305:26230/08:PU78080 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

What else is decidable about integer arrays?

Original language description

This report is the full version of the corresponding FOSSCAS'08 paper, including full proofs of the achived results. In the work, we introduce a new decidable logic for reasoning about infinite arrays of integers. The logic is in the $exists^* forall^*$ first-order fragment and allows (1) Presburger constraints on existentially quantified variables, (2) difference constraints as well as periodicity constraints on universally quantified indices, and (3) difference constraints on values. In particular,using our logic, one can express constraints on consecutive elements of arrays (e.g., $forall i ~.~ 0 leq i &lt; n rightarrow a[i+1]=a[i]-1$) as well as periodic facts (e.g., $forall i ~.~ i equiv_2 0 rightarrow a[i] = 0$). The decision procedure follows the automata-theoretic approach: we translate formulae into a special class of B&quot;uchi counter automata such that any model of a formula corresponds to an accepting run of an automaton, and vice versa. The emptiness problem fo

Czech name

Co dále je rozhodnutelné o polích?

Czech description

Tato zpráva je úplnou verzí článku publikovaného na FOSSACS'08, zahrnující mj. důkazy. Tento článek zavádí novou logiku nad předem neomezenými poli neomezených celočíselných údajů a ukazuje, že splnitelnost formulí této logiky je rozhodnutelná. Tato logika je $exists^* forall^*$ fragmentem predikátové logiky prvního řádu a umožňuje (1) presburgerovské omezení nad existenčně kvantifikovanými indexy, (2) diferenční omezení i omezení periodicity nad univerzálně kvantifikovanými indexy a (3) diferenční omezení nad hodnotami uloženými v polích. Zavedená rozhodovací procedura, založená na využití teorie automatů, může být uplatněna v rámci nástrojů pro automatickou formální verifikaci programů.

Type

A - Audiovisual production

CEP classification

JC - Computer hardware and software

OECD FORD branch

—

Project

<a href="/en/project/GA102%2F07%2F0322" target="_blank" >GA102/07/0322: Advanced Formal Approaches in the Design and Verification of Computer-Based Systems</a><br>

Continuities

Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year

2008

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

ISBN

—

Place of publication

—

Publisher/client name

—

Version

—

Carrier ID

—