9 citations · 17 across the 5 of their papers we have counts for
5 papers
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…
Decision Problems For Convex Languages
Janusz Brzozowski, Jeffrey Shallit, Zhi Xu
In this paper we examine decision problems associated with various classes of convex languages, studied by Ang and Brzozowski (under the name "continuous languages"). We show that…