A structural characterization of reflexive splicing languages has been recently given in [P. Bonizzoni, C. De Felice, R. Zizza, The structure of reflexive regular splicing languages via Schützenberger constants, Theoretical Computer Science 334 (2005) 71–98] and [P. Bonizzoni, G. Mauri, Regular splicing languages and subclasses, Theoretical Computer Science 340 (2005) 349–363] 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 the notion of label-equivalence that induces a finite refinement of the syntactic monoid of a regular language L. A finite set of representatives for label-equivalent classes of constant words in L is defined and it is proved that such a finite set provides the splice sites of splicing rules generating language L.
Citazione: | Bonizzoni, P. (2010). Constants and label-equivalence: A decision procedure for reflexive regular splicing languages. THEORETICAL COMPUTER SCIENCE, 411(6), 865-877. |
Tipo: | Articolo in rivista - Articolo scientifico |
Carattere della pubblicazione: | Scientifica |
Titolo: | Constants and label-equivalence: A decision procedure for reflexive regular splicing languages |
Autori: | Bonizzoni, P |
Autori: | |
Data di pubblicazione: | 2010 |
Lingua: | English |
Rivista: | THEORETICAL COMPUTER SCIENCE |
Digital Object Identifier (DOI): | 10.1016/j.tcs.2009.06.038 |
Appare nelle tipologie: | 01 - Articolo su rivista |