Abstract | ||
---|---|---|
To a given language L , we associate the sets ins(L) (resp. del(L) ) consisting of words with the following property: their insertion into (deletion from) any word of L yields words which also belong to L . Properties of these sets and of languages which are insertion (deletion) closed are obtained. Of special interest is the case when the language is ins-closed (del-closed) and finitely generated. Then the minimal set of generators turns out to be a maximal prefix and suffix code, which is regular if L is regular. In addition, we study the insertion-base of a language and languages which have the property that both they and their complements are ins-closed. |
Year | DOI | Venue |
---|---|---|
1997 | 10.1016/S0304-3975(96)00307-6 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
deletion closure | Journal | 183 |
Issue | ISSN | Citations |
1 | Theoretical Computer Science | 10 |
PageRank | References | Authors |
1.17 | 2 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Masami Ito | 1 | 299 | 66.19 |
Lila Kari | 2 | 1123 | 124.45 |
Gabriel Thierrin | 3 | 263 | 34.89 |