15 citations · 86 across the 34 of their papers we have counts for
5 papers · 1 filter
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…
On NFAs Where All States are Final, Initial, or Both
Jui-Yi Kao, Narad Rampersad, Jeffrey Shallit
We examine questions involving nondeterministic finite automata where all states are final, initial, or both initial and final. First, we prove hardness results for the nonuniversa…
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…
Detecting palindromes, patterns, and borders in regular languages
Terry Anderson, John Loftus, Narad Rampersad +2
Given a language L and a nondeterministic finite automaton M, we consider whether we can determine efficiently (in the size of M) if M accepts at least one word in L, or infinitely…