Paper Info
Title
A decision procedure for reflexive regular splicing languages
Abstract
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.
Year
DOI
Venue
2006
10.1007/11779148_29
Developments in Language Theory
Keywords
Field
DocType
language l.,decision procedure,splicing rule,syntactic monoid,reflexive regular splicing language,reflexive iff splice site,formal language theory,regular splicing language,finite set,reflexive splicing language,splicing operation,regular language,formal language
Discrete mathematics,Finite set,Formal language,Computer science,Monoid,Philosophy of language,RNA splicing,Syntactic monoid,Parsing,Regular language
Conference
Volume
ISSN
ISBN
4036
0302-9743
3-540-35428-X
Citations 
PageRank 
References 
2
0.43
11
Authors
2
Name
Order
Citations
PageRank
Paola Bonizzoni11078.86
Giancarlo Mauri22106297.38