Non-deterministic width of regular languages: the unary case

The (deterministic/non-deterministic) width of a regular language ℒ is the minimum number of chains necessary to decompose a partial order of the states of an automaton (deterministic/non-deterministic) accepting ℒ. We begin the study of the non-deterministic width of a regular language, with a special focus on unary languages. We review preliminary results and introduce two possible definitions of co-lexicographic (co-lex) order on non-deterministic finite automata (NFAs)-namely, a global and a local order-along with their corresponding widths. We illustrate that, in general, these two widths do not coincide on NFAs. We then analyze the unary case, proving that the two language-level widths-defined as the minimum width among equivalent NFAs-do coincide. We establish this by showing that the minimum width is realised by automata in Chrobak normal form. Finally, we provide an operational definition for the non-deterministic width of a unary language and we analyze its computational complexity, showing that the problem of computing it is in NP. We further ask if the width of a language is a good indicator for its degree of non-determinism and show that, for unary languages, a constant degree of non-determinism is always achievable, regardless of the width.