On complete sets of samples for generalized regular expressions

The language of generalized regular expressions introduced by Brazma and Kinber [4] is a convenient tool for inductive formalization of sample computations. The decidability of the equivalence problem was proved and some other questions were investigated for this language in [4]. The following problem is important for the synthesis and is investigated in this paper: is it possible to specify an arbitrary class of equivalent programs by a finite set of samples. A positive answer to this question is obtained for a stronger equivalence relation when the equivalence implies a similarity of program structures.

Authors

• E.B. Kinber

Keywords

No keywords are indexed for this paper.