Browsing Waterloo Research by Subject "quotient complexity"
Now showing items 16 of 6

Complexity Of Atoms Of Regular Languages
(World Scientific Publishing, 20131101)The quotient complexity of a regular language L, which is the same as its state complexity the number of left quotients of L. An atom of a nonempty regular language L with n quotients is a nonempty intersection of the n ... 
Complexity of proper prefixconvex regular languages
(Elsevier, 20191001)A language L over an alphabet Σ is prefixconvex if, for any words x,y,z ∈ Σ*, whenever x and xyz are in L, then so is xy. Prefixconvex languages include rightideal, prefixclosed, and prefixfree languages, which were ... 
Complexity of RightIdeal, PrefixClosed, and PrefixFree Regular Languages
(Institute of Informatics: University of Szeged, 2017)A language L over an alphabet E is prefixconvex if, for any words x, y, z is an element of Sigma*, whenever x and xyz are in L, then so is xy. Prefixconvex languages include rightideal, prefixclosed, and prefixfree ... 
In Search Of Most Complex Regular Languages
(World Scientific Publishing, 20130901)Sequences (Ln vertical bar n >= k), called streams, of regular languages Ln are considered, where k is some small positive integer, n is the state complexity of Ln, and the languages in a stream differ only in the ... 
Quotient Complexities of Atoms in Regular Ideal Languages
(Institute of Informatics: University of Szeged, 2015)A (left) quotient of a language L by a word w is the language w(1) L = {x vertical bar wx is an element of L}. The quotient complexity of a regular language L is the number of quotients of L; it is equal to the state ... 
Quotient Complexity of Bifix, Factor, and SubwordFree Regular Language
(Institute of Informatics: University of Szeged, 2014)A language $L$ is prefixfree if whenever words $u$ and $v$ are in $L$ and $u$ is a prefix of $v$, then $u=v$. Suffix, factor, and subwordfree languages are defined similarly, where by ``subword" we mean ``subsequence", ...