Splicing representations of strictly locally testable languages

✍ Scribed by Tom Head

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 711 KB
• Volume: 87
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(98)00053-5

✦ Synopsis

The relationship between the family SH of simple splicing languages, which was recently introduced by Mateescu et al. and the family X7' of strictly locally testable languages is clarified by establishing an ascending hierarchy of families {SiH: i > -1) of splicing languages for which SH = SI H and the union of the families is the family XT. A procedure is given which, for an arbitrary regular language L, determines whether L is in SLT and, when L is in SLT, specifies constructively the smallest family in the hierarchy to which L belongs. Examples are given of sets of restriction enzymes for which the action on DNA molecules is naturally represented by splicing systems of the types discussed.