کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4952296 1364438 2017 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Unavoidable sets and circular splicing languages
ترجمه فارسی عنوان
مجموعه های اجتناب ناپذیر و زبان های حلقوی دایره ای
کلمات کلیدی
زبان های منظم، سیستم های اسپلایشی دایره ای مجموعه های اجتناب ناپذیر
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Circular splicing systems are a formal model of a generative mechanism of circular words, inspired by a recombinant behaviour of circular DNA. They are defined by a finite alphabet A, an initial set I of circular words, and a set R of rules. In this paper, we focus on the still unknown relations between regular languages and circular splicing systems with a finite initial set and a finite set R of rules represented by a pair of letters ((1,3)-CSSH systems). When R=A×A, it is known that the set of all words corresponding to the splicing language belongs to the class of pure unitary languages, introduced by Ehrenfeucht, Haussler, Rozenberg in 1983. They also provided a characterization of the regular pure unitary languages, based on the notions of unavoidable sets and well quasi-orders. We partially extend these notions and their results in the more general framework of the (1,3)-CSSH systems.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 658, Part A, 7 January 2017, Pages 148-158
نویسندگان
, , ,