References of "Shallit, Jeffrey"
     in
Bookmark and Share    
Full Text
Peer Reviewed
See detailComposition and orbits of language operations: finiteness and upper bounds
Charlier, Emilie ULg; Domaratzki, Michael; Harju, Tero et al

in International Journal of Computer Mathematics (2013), 90(6), 1171-1196

We consider a set of eight natural operations on formal languages (Kleene closure, positive closure, complement, prefix, suffix, factor, subword, and reversal), and compositions of them. If x and y are ... [more ▼]

We consider a set of eight natural operations on formal languages (Kleene closure, positive closure, complement, prefix, suffix, factor, subword, and reversal), and compositions of them. If x and y are compositions, we say x is equivalent to y if they have the same effect on all languages L. We prove that the number of equivalence classes of these eight operations is finite. This implies that the orbit of any language L under the elements of the monoid is finite and bounded, independently of L. This generalizes previous results about complement, Kleene closure, and positive closure. We also estimate the number of distinct languages generated by various subsets of these operations. [less ▲]

Detailed reference viewed: 22 (5 ULg)
Full Text
Peer Reviewed
See detailEnumeration and decidable properties of automatic sequences
Charlier, Emilie ULg; Rampersad, Narad; Shallit, Jeffrey

in International Journal of Foundations of Computer Science (2012), 23(5), 1035-1066

We show that various aspects of k-automatic sequences — such as having an unbordered factor of length n — are both decidable and effectively enumerable. As a consequence it follows that many related ... [more ▼]

We show that various aspects of k-automatic sequences — such as having an unbordered factor of length n — are both decidable and effectively enumerable. As a consequence it follows that many related sequences are either k-automatic or k-regular. These include many sequences previously studied in the literature, such as the recurrence function, the appearance function, and the repetitivity index. We also give some new characterizations of the class of k-regular sequences. Many results extend to other sequences defined in terms of Pisot numeration systems. [less ▲]

Detailed reference viewed: 13 (7 ULg)
Full Text
Peer Reviewed
See detailEnumeration and decidable properties of automatic sequences
Charlier, Emilie ULg; Rampersad, Narad; Shallit, Jeffrey

in Actes de Numération 2011 (2011, June)

We show that various aspects of k-automatic sequences such as having an unbordered factor of length n are both decidable and e ectively enumerable. As a consequence it follows that many related sequences ... [more ▼]

We show that various aspects of k-automatic sequences such as having an unbordered factor of length n are both decidable and e ectively enumerable. As a consequence it follows that many related sequences are either k-automatic or k-regular. These include many sequences previously studied in the literature, such as the recurrence function, the appearance function, and the repetitivity index. We also give a new characterization of the class of k-regular sequences. Many results extend to other sequences de ned in terms of Pisot numeration systems. [less ▲]

Detailed reference viewed: 20 (3 ULg)
Full Text
Peer Reviewed
See detailEnumeration and decidable properties of automatic sequences
Charlier, Emilie ULg; Rampersad, Narad; Shallit, Jeffrey

in Lecture Notes in Computer Science (2011), 6795

We show that various aspects of k-automatic sequences — such as having an unbordered factor of length n — are both decidable and effectively enumerable. As a consequence it follows that many related ... [more ▼]

We show that various aspects of k-automatic sequences — such as having an unbordered factor of length n — are both decidable and effectively enumerable. As a consequence it follows that many related sequences are either k-automatic or k-regular. These include many sequences previously studied in the literature, such as the recurrence function, the appearance function, and the repetitivity index. We also give a new characterization of the class of k-regular sequences. Many results extend to other sequences defined in terms of Pisot numeration systems. [less ▲]

Detailed reference viewed: 14 (4 ULg)
Full Text
Peer Reviewed
See detailFinite orbits of language operations
Charlier, Emilie ULg; Domaratzski, Michael; Harju, Tero et al

in Lecture Notes in Computer Science (2011), 6638

We consider a set of natural operations on languages, and prove that the orbit of any language L under the monoid generated by this set is finite and bounded, independently of L. This generalizes previous ... [more ▼]

We consider a set of natural operations on languages, and prove that the orbit of any language L under the monoid generated by this set is finite and bounded, independently of L. This generalizes previous results about complement, Kleene closure, and positive closure. [less ▲]

Detailed reference viewed: 22 (3 ULg)
Full Text
Peer Reviewed
See detailInverse star, borders, and palstars
Rampersad, Narad ULg; Shallit, Jeffrey; Wang, Ming-wei

in Information Processing Letters (2011), 111

A language L is closed if L = L*. We consider an operation on closed languages, L-*, that is an inverse to Kleene closure. It is known that if L is closed and regular, then L-* is also regular. We show ... [more ▼]

A language L is closed if L = L*. We consider an operation on closed languages, L-*, that is an inverse to Kleene closure. It is known that if L is closed and regular, then L-* is also regular. We show that the analogous result fails to hold for the context-free languages. Along the way we find a new relationship between the unbordered words and the prime palstars of Knuth, Morris, and Pratt. We use this relationship to enumerate the prime palstars, and we prove that neither the language of all unbordered words nor the language of all prime palstars is context-free. [less ▲]

Detailed reference viewed: 9 (0 ULg)