A given automaton ${{\mathcal A}}$ [*accepts*]{} a word $w = a_1a_2\ldots a_{n}$ if and only if ${{\mathcal A}}$ is in a final state after having read all symbols from left to right, i.e. $$\delta(\ldots\delta(\delta(q_{\text{ini}},a_1),a_2),\ldots a_{n})\in F.$$ The language ${{\mathcal L}}({{\mathcal A}}) \subseteq \Sigma^*$ that is [*recognized*]{} by ${{\mathcal A}}$ is defined as the set of words that ${{\mathcal A}}$ accepts. For the automata constructed in this paper, we have $|F| = 1$ and $\delta$ being a total function that maps each pair of a state in $Q$ and a symbol in $\Sigma$ to a state in $Q$. For a detailed introduction to automata theory and languages, see the book by Hopcroft and Ullman [@hopcroft79].

A variant of the [Intermezzo]{} problem {#sec:intermezzo}
=======================================

In this section, we establish NP-completeness of a variant of the ordering problem [Intermezzo]{}. Let $A$ be a finite set, and let ${{\mathcal O}}$ be an ordering on the elements in $A$. For two elements $a$ and $b$ in $A$, we write $a<b$ precisely if $a$ precedes $b$ in ${{\mathcal O}}$. With this notation in hand, we now formally state [Intermezzo]{} which was shown to be NP-complete via reduction from [3-SAT]{} [@guttmann06 Lemma 1].

[Intermezzo]{}\
[**Instance.**]{} A finite 