19 citations · 121 across the 33 of their papers we have counts for
5 papers · 1 filter
Quotient Complexity of Closed Languages
J. Brzozowski, G. Jirásková, C. Zou
A language L is prefix-closed if, whenever a word w is in L, then every prefix of w is also in L. We define suffix-, factor-, and subword-closed languages in the same way, where by…
Quotient complexity of ideal languages
J. Brzozowski, G. Jirásková, B. Li
We study the state complexity of regular operations in the class of ideal languages. A language L over an alphabet Sigma is a right (left) ideal if it satisfies L = L Sigma* (L = S…
Quotient Complexity of Regular Languages
Janusz Brzozowski
The past research on the state complexity of operations on regular languages is examined, and a new approach based on an old method (derivatives of regular expressions) is presente…
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…