15 citations · 88 across the 37 of their papers we have counts for
4 papers · 2 filters
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…