Search

Start Over Creator Fábera, Vít

2. Regular grammar transformation inspired by the graph distance using GA

Creator:
Fábera, Vít, Zelenka , Jan, Jáneš, Vlastimil, and Jánešová , Mária
Format:
bez média and svazek
Type:
model:article and TEXT
Subject:
Finite state machine, automata, graph, graph distance, regular grammar distance, and genetic algorithm
Language:
English
Description:
This paper introduces a method how to transform one regular grammar to the second one. The transformation is based on regular grammar distance computation. Regular grammars are equivalent to finite states machines and they are represented by oriented graphs or by transition matrices, respectively. Thus, the regular grammar distance is defined analogously to the distance between two graphs. The distance is measured as the minimal count of elementary operations over the grammar which transform the first grammar to the second one. The distance is computed by searching an optimal mapping of non-terminal symbols of both grammars. The computation itself is done by the genetic algorithm because the exhaustive evaluation of mapping leads to combinatorial explosion. Transformation steps are derived from differences in matrices. Differences are identified during the computation of the distance.
Rights:
http://creativecommons.org/publicdomain/mark/1.0/ and policy:public