Regular grammar transformation inspired by the graph distance using GA

Title:

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

Identifier:

https://cdk.lib.cas.cz/client/handle/uuid:27bc9f9b-cc99-4348-8b6f-f9641b680cdc
uuid:27bc9f9b-cc99-4348-8b6f-f9641b680cdc
doi:10.14311/NNW.2011.21.018

Subject:

Finite state machine, automata, graph, graph distance, regular grammar distance, and genetic algorithm

Type:

model:article and TEXT

Format:

bez média and svazek

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.

Language:

English

Rights:

http://creativecommons.org/publicdomain/mark/1.0/
policy:public

Source:

Neural network world: international journal on neural and mass-parallel computing and information systems | 2011 Volume:21 | Number:4

Harvested from:

CDK

Metadata only:

false