Paper #1

Paper #1

Generating Minimal Nondeterministic Finite Automata Using a Parallel Algorithm

Tomasz JastrzÄ…b 1, Zbigniew Czech 1 and Wojciech Wieczorek 2

1 Dept. of Algorithmics and Software, Silesian University of Technology, Gliwice, Poland
{Tomasz.Jastrzab, Zbigniew.Czech} @ polsl pl
2 Faculty of Science and Technology, Silesia University in Katowice, Katowice, Poland
Wojciech.Wieczorek @ us edu pl

Abstract: The goal of this paper is to develop a parallel algorithm that, on input of a learning sample, identifies a regular language by means of a nondeterministic finite automaton (NFA). A sample is a pair of finite sets containing positive and negative examples. Given a sample, the minimal NFA that represents the target regular language is sought. We define the task of finding the NFA, which accepts all positive examples and rejects all negative ones, as a constraint satisfaction problem, and then propose a parallel algorithm to solve the problem. The results of preliminary computational experiments on the variety of hexapeptide test samples are reported.

Keywords: parallel algorithm, learning regular languagesusing nondeterministic finite automata, constraint satisfaction and satisfiability problems, grammatical inference