Conservative Extensions of Regular Languages
Béatrice Bouchou, Denio Duarte, Mírian Halfeld Ferrari, Dominique A. Laurent, Martin Alejandro Musicante · 2005
Given a regular expression E and a word w belonging to the language associated to E (i.e. w /spl isin/ L(E)), we consider the following problem: Let the word w' be obtained from w by adding or removing one symbol. In this case, we are interested in building new regular expressions E' such are similar to E and such that L(E) /spl cup/ {w'} /spl sube/ L(E'). The new regular expressions are computed by an algorithm called GREC that performs changes on a finite state automaton accepting L(E), in order to derive the new regular expressions E'. Our method consists in proposing different choices, permitting the evolution of the data belonging to an application. As the final choice depends on the intended semantics for the data, it is left to an advised user.