15 citations · 86 across the 34 of their papers we have counts for
7 papers · 1 filter
Automata and Reduced Words in the Free Group
Thomas Ang, Giovanni Pighizzini, Narad Rampersad +1
We consider some questions about formal languages that arise when inverses of letters, words and languages are defined. The reduced representation of a language over the free monoi…
Length of the Shortest Word in the Intersection of Regular Languages
Thomas Ang, Jeffrey Shallit
In this note, we give a construction that provides a tight lower bound of mn-1 for the length of the shortest word in the intersection of two regular languages with state complexit…
The computational complexity of universality problems for prefixes, suffixes, factors, and subwords of regular languages
N. Rampersad, J. Shallit, Z. Xu
In this paper we consider the computational complexity of the following problems: given a DFA or NFA representing a regular language L over a finite alphabet Sigma is the set of al…
Detecting patterns in finite regular and context-free languages
Narad Rampersad, Jeffrey Shallit
We consider variations on the following problem: given an NFA M and a pattern p, does there exist an x in L(M) such that p matches x? We consider the restricted problem where M onl…
Closures in Formal Languages: Concatenation, Separation, and Algorithms
J. Brzozowski, E. Grant, J. Shallit
We continue our study of open and closed languages. We investigate how the properties of being open and closed are preserved under concatenation. We investigate analogues, in forma…
Closures in Formal Languages and Kuratowski's Theorem
J. Brzozowski, E. Grant, J. Shallit
A famous theorem of Kuratowski states that in a topological space, at most 14 distinct sets can be produced by repeatedly applying the operations of closure and complement to a giv…