Wyniki wyszukiwania - BazTech

1

Zestawienie i porównanie automatów probabilistycznych i kwantowych

Siedlecka-Lamch O.

Studia i Materiały / Europejska Uczelnia Informatyczno-Ekonomiczna w Warszawie

|

2017

|

Nr 1(13)

77--83

PL

Większość systemów informatycznych można modelować z wykorzystaniem różnego rodzaju automatów skończonych: deterministycznych, niedeterministycznych, probabilistycznych itp. Automaty te można badać pod kątem osiągalności określonych stanów i dzięki temu sprawdzać, czy system może znaleźć się w stanie krytycznym, błędnym, niechcianym. Mamy również możliwość dokonania operacji minimalizacji automatów. Praktycznie ogranicza się to do znalezienia stanów nadmiarowych i nieosiągalnych – dzięki czemu mamy również sposobność zminimalizować oryginalny, modelowany system, zaoszczędzić na dokonywanych operacjach, pamięci, a nawet sprzęcie.

EN

Most IT systems can be modeled with the use of various types of finite automata: deterministic, non-deterministic, probabilistic, etc. These automatons can be tested for reachability of certain states and thus we can check whether the system can be in a critical, erroneous or unwanted state. We also have the ability to perform the operation of automata minimization. Practically, this is limited to finding redundant and unreachable states – so we also have the opportunity to minimize the original, modeled system, save on operations amount, memory, and even hardware.

2

Bisimulation relation for selected types of probabilistic and quantum automata

Siedlecka-Lamch O.

Scientific Issues of Jan Długosz University in Częstochowa. Mathematics

|

2011

|

Vol. 16

135--140

EN

The first step to make transitional systems more efficient is to minimize the number of their states. A bisimulation relation is a mathematical tool that helps in searching for equivalent systems, what is useful in the minimization of algorithms. For two transition systems bisimulation is a binary relation associating systems which behave in the same way in the sense that one system simulates the other and viceversa. The definition for classical systems is clear and simple, but what happens with nondeterministic, probabilistic and quantum systems? This will be the main topic of this article.

3

On the Size of Unary Probabilistic and Nondeterministic Automata

Bianchi M.P., Mereghetti C., Palano B., Pighizzini G.

Fundamenta Informaticae

|

2011

|

Vol. 112, nr 2/3

119-135

EN

We investigate and compare the descriptional power of unary probabilistic and nondeterministic automata (pfa's and nfa's, respectively). We show the existence of a family of languages hard for pfa’s in the following sense: For any positive integer d, there exists a unary d-cyclic language such that any pfa accepting it requires d states, as the smallest deterministic automaton. On the other hand, we prove that there exist infinitely many languages having pfa’s which from one side do not match a known optimal state lower bound and, on the other side, they are smaller than nfa’s which, in turn, are smaller than deterministic automata.

4

SAT-based Reachability Checking for Timed Automata with Diagonal Constraints

Zbrzezny A.

Fundamenta Informaticae

|

2005

|

Vol. 67, nr 1-3

303--322

EN

This paper deals with the problem of checking reachability for timed automata with diagonal constraints. Such automata are needed in many applications e.g. to model scheduling problems. We introduce a new discretization for timed automata which enables SAT based reachability analysis for timed automata for which comparisons between two clocks are allowed. In our earlier papers SAT based reachability analysis was restricted to the so called diagonal-free timed automata, where only comparisons between clocks and constants are allowed.