Wyniki wyszukiwania - BazTech

1

A Boolean Encoding of Arithmetic Operations

Zbrzezny A.

Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk

|

2007

|

Nr 999

1-35

EN

In this paper we present algorithms for a~Boolean encoding of four basic arithmetic operations on integer numbers: addition, subtraction, multiplication and division. Integer numbers are encoded in two's complement system as vectors of Boolean formulas and arithmetic operations are faithfully encoded as operations on vectors of Boolean formulas. In addition, we also provide an algorithm for a Boolean encoding of the operations of calculating integer square root and an algorithm for a Boolean encoding of the operation of exponentiation with nonnegative integer exponent.

PL

W pracy przedstawiamy algorytmy realizujące Boolowskie kodowanie czterech podstawowych operacji arytmetycznych: dodawania, odejmowania, mnożenia i dzielenia. Liczby całkowite są kodowane w systemie uzupełnieniowym do 2 jako wektory formuł Boolowskich a operacje arytmetyczne są zakodowane jako operacje na wektorach formuł Boolowskich. Dodatkowo przedstawiamy algorytmy realizujące Boolowskie kodowanie dla operacji obliczania całkowitego pierwiastka kwadratowego oraz dla operacji potęgowania.

2

Reaching the limits for Bounded Model Checking

Woźna B.

Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk

|

2003

|

Nr 958

1-25

EN

The main contribution of the paper consists in showing that the BMC method is feasible for ACTL* (the universal fragment of CTL*) which subsumes both ACTL and LTL. The extension to ACTL* is obtained by redefining the function returning the sufficient number of executions over which an ACTL* formula is checked, and then by combining two known translations to SAT for ACTL and LTL formulas. The proposed translation of ACTL* formulas is essentially different from the existing translations of both ACTL and LTL formulas. Moreover, ACTL* seems to be the largest set of temporal properties which can be verified by means of BMC. We have implemented our new BMC algorithm for discrete timed automata and we have presented a preliminary experimental results, which prove the efficiency of the method. The formal treatment is the basis for the implementation of the technique in the symbolic model checker VerICS.

PL

Osiągnięcie granicy rozszerzalności metody ograniczonej weryfikacji modelowej. Głównym celem tej pracy jest wykazanie, że metoda ograniczonej weryfikacji modelowej (OWM) jest rozszerzalna do własności wyrażalnych w ACTL* (uniwersalnym fragmencie logiki CTL*), języku który zawiera zarówno ACTL i LTL. Rozszerzenie metody OWM do ACTL* polega na przedefiniowaniu funkcji zwracającej wystarczającą liczbę wykonań systemu, w zbiorze których formuła ACTL* jest sprawdzana, a następnie na zdefiniowaniu translacji będącej kombinacją translacji formuł LTL i ACTL. Zaproponowana translacja formuł ACTL* istotnie różni się od tych istniejących dla LTL i ACTL oraz wydaje się, że język ACTL* jest największym zbiorem własności temporalnych, które mogą być weryfikowane za pomocą metody OWM. Nasz nowy algorytm został zaimplementowany dla elementarnych sieci Petriego oraz dla dyskretnych automatów czasowych, a uzyskane wstępne wyniki eksperymentalne dowodzą efektywności naszej metody. Ponadto, zaproponowana translacja i wykonana implementacja będzie bazą dla nowego modułu w symbolicznym weryfikatorze Öerics.

3

SAT-Based Bounded Model Checking for the Universal Fragment of TCTL

Penczek W., Woźna B., Zbrzezny A.

Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk

|

2002

|

Nr 947

1-26

EN

Bounded Model Checking (BMC) based on SAT methods consists in searching for a counterexample of a particular length and to generate a propositional formula that is satisfiable iff such a counterexample exists. Our paper shows how the concept of bounded model checking can be extended to deal with \TACTL\ (the universal fragment of \TCTL ) properties of a network of concurrent Timed Automata.

PL

Ograniczona Weryfikacja Modelowa, bzaująca na metodach SAT, polega na poszukiwaniu kontrprzykładów o długości ograniczonej przez pewną liczbę całkowitą k > 0 oraz generowanie formuły zdaniowej, która jest spełniana wtedy i tylko wtedy, gdy taki kontrprzykład istnieje. Celem tej pracy jest przedstawienie koncepcji ograniczonej weryfikacji modelowej dla automatów czasowych reprezentowanych przez siec współbieżnych i wzajemnie komunikujących się komponentów oraz własności wyrażanych w języku logiki TACTL (uniwersalnego fragmentu TCTL).

4

Checking Reachability Properties for Timed Automata via SAT

Woźna B., Penczek W., Zbrzezny A.

Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk

|

2002

|

Nr 949

1-19

EN

The paper deals with the problem of checking reachability for timed automata. The main idea consists in combining the well-know forward reachability algorithm and the Bounded Model Checking (BMC) method. In order to check reachability of a state satisfying some desired property, first the transition relation of a timed automaton is unfolded to the depth k Î N and encoded as a prepositional formula. Next the desired property is translated to a prepositional formula and the satisfiability of the conjunction of the two above defined formulas is checked. The unfolding of the transition can be terminated when either a state satisfying the property has been found or all the states of the timed automaton have been searched. The efficiency of the method is strongly supported by the experimental results. Keywords : Reachability problem, bounded model checking, translation to SAT, Timed Automata, Augmented Region Graphs, discretization.

PL

Testowanie osiągalności automatów czasowych z wykorzystaniem SAT. Praca opisuje nowe podejście do problemu osiągalności dla automatów czasowych. Główna idea polega na połączeniu znanego algorytmu przeszukującego przestrzeń stanów wszerz metodą BFS oraz metody ograniczonej weryfikacji modelowej. Aby sprawdzić, czy stan spełniający daną własność jest osiągalny w modelu dla rozważanego automatu czasowego postępujemy następująco. Rozwijamy stopniowo relację przejścia dla automatu, aż do głębokości k Î N i kodujemy ją jako formułę zdaniową. Następnie, za pomocą formuły zdaniowej kodowana jest rozważana własność i sprawdzana jest spełnialność koniunkcji obydwu zdefiniowanych formuł zdaniowych. Rozwijanie relacji przejścia może zostać zakończone jeśli poszukiwany stan został znaleziony lub wszystkie stany danego automatu czasowego zostały przeszukane.

5

Bounded Model Cheking for Interpreted Systems

Penczek W., Lomuscio A.

Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk

|

2002

|

Nr 946

1-8

EN

We present an extension of a bounded model checking algorithm to deal with temporal epistemic formulas. We use the algorithm to solve a variant of the bit transmission problem

PL

W pracy przedstawiamy rozszerzenie algorytmu ograniczonej weryfikacji modelowej do temporalnych formuł epistemicznych. Algorytm jest zastosowany do weryfikacji pewnego wariantu problemu transmisji bitów.

6

Branching Time Bounded Model Checking for Elementary Net Systems

Penczek W., Woźna B., Zbrzezny A.

Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk

|

2001

|

Nr 940

1-16

EN

Bounded Model Checking (BMC) has been recently introduced as an efficient verification method for reactive systems. BMC based on SAT methods consists in searching for a counterexample of a particular lenght and generating a propositional formula that is satisfiable iff such a counterexample exists. This new technique has been introduced by E.Clarke et al. for model checking of the linear time temporal logic (LTL). Our paper shows how the concept of bounded model checking can be extended to ACTL (the universal fragment of CTL). The implementation of the algorithm for Elementary Net Systems is described together with the experimental results.

PL

Ograniczona weryfikacja Modelowa, bazująca na metodach SAT, została wprowadzona jako uzupełniająca technika do Symbolicznej Weryfikacji Modelowej opartej na BDD. Podstawową ideą tej metody jest poszukiwanie kontrprzykładów o długości ograniczonej przez pewne całkowite k>0 oraz generowanie formuły zadaniowej, która jest spełnialna wtedy i tylko wtedy, gdy taki kontrprzykład istnieje. Ta nowa technika została po raz pierwszy wprowadzona przez E.Clarka, A.Biera, A. Cimatti'ego i Y.Zhu i zastosowana do weryfikacji modelowej formuł liniowej logiki temporalnej. Celem tej pracy jest przedstawienie koncepcji ograniczonej weryfikacji modelowej dla formuł logiki ACTL (uniwersalnego fragmentu CTL). Ponadto prezentujemy implementację algorytmu BCM dla Sieci Elementarnych wraz z wynikami eksperymentalnymi.