A decision procedure for reflexive regular splicing languages

A structural characterization of reflexive splicing languages has been recently given in [1] and [5] showing surprising connections between long standing notions in formal language theory, the syntactic monoid and Schützenberger constant and the splicing operation. In this paper, we provide a procedure to decide whether a regular language is a reflexive splicing language, based on the above mentioned characterization that is given in terms of a finite set of constants for the language. The procedure relies on a basic result showing how to determine, given a regular language L, a finite set of representatives for constant classes of the syntactic monoid of L. This finite set provides the splice sites of splicing rules generating language L. Indeed, we recall that in [1] it is shown that a regular splicing language is reflexive iff splice sites of the rules are constants for the language. © Springer-Verlag Berlin Heidelberg 2006