7 papers
Computational Complexity of Edge Coverage Problem for Constrained Control Flow Graphs
Jakub Ruszil, Artur Polański, Adam Roman +1
The article studies edge coverage for control flow graphs extended with explicit constraints. Achieving a given level of white-box coverage for a given code is a classic problem in…
Efficient Prime Paths Generation
Jakub Zelek, Jakub Ruszil, Adam Roman +1
Prime path coverage is a powerful structural testing criterion, but generating all prime paths in a directed graph remains computationally challenging due to the potentially expone…
Studying homing and synchronizing sequences for Timed Finite State Machines with output delays
Evgenii Vinarskii, Jakub Ruszil, Adam Roman +1
The paper introduces final state identification (synchronizing and homing) sequences for Timed Finite State Machines (TFSMs) with output delays and investigates their properties. W…
Careful Synchronization of One-Cluster Automata
Jakub Ruszil
In this paper we investigate careful synchronization of one-cluster partial automata. First we prove that in general case the shortest carefully synchronizing word for such automat…
Asymmetric Cryptosystem Using Careful Synchronization
Jakub Ruszil
We present public-private key cryptosystem which utilizes the fact that checking whether a partial automaton is carefully synchronizing is -complete, even in the case of a…
Approximation algorithm for finding short synchronizing words in weighted automata
Jakub Ruszil
In this paper we are dealing with the issue of finding possibly short synchronizing words in automata with weight assigned to each letter in the alphabet . First we discuss some…
On synchronization of partial automata
Jakub Ruszil
A goal of this paper is to introduce the new construction of an automaton with shortest synchronizing word of length , where and is the n…