19 citations · 55 across the 13 of their papers we have counts for
Showing 2009Show all
3 papers · 1 filter
cs.FL2009★ 13 cited
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…
cs.FL2009
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…
cs.FL2009★ 2 cited
Nondeterministic State Complexity of Positional Addition
Galina Jirásková, Alexander Okhotin
Consider nondeterministic finite automata recognizing base-k positional notation of numbers. Assume that numbers are read starting from their least significant digits. It is proved…