کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
426782 686270 2013 21 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Regular languages and partial commutations
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Regular languages and partial commutations
چکیده انگلیسی

The closure of a regular language under a [partial] commutation I   has been extensively studied. We present new advances on two problems of this area: (1) When is the closure of a regular language under [partial] commutation still regular? (2) Are there any robust classes of languages closed under [partial] commutation? We show that the class Pol(G)Pol(G) of polynomials of group languages is closed under commutation, and under partial commutation when the complement of I   in A2A2 is a transitive relation. We also give a sufficient graph theoretic condition on I   to ensure that the closure of a language of Pol(G)Pol(G) under I  -commutation is regular. We exhibit a very robust class of languages WW which is closed under commutation. This class contains Pol(G)Pol(G), is decidable and can be defined as the largest positive variety of languages not containing (ab)⁎(ab)⁎. It is also closed under intersection, union, shuffle, concatenation, quotients, length-decreasing morphisms and inverses of morphisms. If I   is transitive, we show that the closure of a language of WW under I-commutation is regular. The proofs are nontrivial and combine several advanced techniques, including combinatorial Ramsey type arguments, algebraic properties of the syntactic monoid, finiteness conditions on semigroups and properties of insertion systems.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 230, September 2013, Pages 76–96
نویسندگان
, , ,