Operational State Complexity of Block Languages

In this paper we consider block languages, namely sets of words having the same length, and study the deterministic and nondeterministic state complexity of several operations on these languages. Being a subclass of finite languages, the upper bounds of operational state complexity known for finite languages apply for block languages as well. However, in several cases, smaller values were found. Block languages can be represented as bitmaps, which are a good tool to study their minimal finite...

Boolean Products of Languages

Partial Derivative Automaton for Regular Expressions with Shuffle

We generalize the partial derivative automaton to regular expressions with shuffle and study its size in the worst and in the average case. The number of states of the partial derivative automata is in the worst case at most 2^m, where m is the number of letters in the expression, while asymptotically and on average it is no more than (4\3)^m.

On the Complexity of Multi-entry DFAs

Multi-entry finite automata (MDFAs) are a generalization of DFAs that allow for an arbitrary number of initial states. This paper extends existing research on MDFAs by studying their operational state complexity and the computational complexity of their associated decision problems. In particular, we analyze the cost on the number of states of the standard language-theoretic operations when performed on MDFAs and compare these results with the well known complexities for DFAs and NFAs. Additi...