$|{{\mathcal P}}|=1$, then ${{\mathcal P}}$ has a cherry-picking sequence. However, if $|{{\mathcal P}}|>1$, then ${{\mathcal P}}$ may or may not have a cherry-picking sequence.

We now formally state the decision problem that this paper is centered around.

[CPS-Existence]{}\
[**Instance.**]{} A collection ${{\mathcal P}}$ of rooted binary phylogenetic $X$-trees.\
[**Question.**]{} Does there exist a cherry-picking sequence for ${{\mathcal P}}$?

The significance of [CPS-Existence]{} is the problem’s equivalence to the question whether or not all trees in ${{\mathcal P}}$ can simultaneously be embedded into a rooted phylogenetic network that satisfies the three temporal constraints as alluded to in the introduction.

[**Automata and languages.**]{} Let $\Sigma$ be an alphabet. A [*language*]{} ${{\mathcal L}}$ is a subset of all possible strings (also called [*words*]{}) whose symbols are in $\Sigma$. More precisely, ${{\mathcal L}}$ is a subset of $\Sigma^*$, where the operator $*$ is the Kleene star. A [*deterministic finite automaton*]{} (or short [*automaton*]{}) is a tuple ${{\mathcal A}}= (Q, \Sigma, \delta, q_{\text{ini}}, F)$, where

(i) $Q$ is a finite set of states,

(ii) $\Sigma$ is a finite alphabet,

(iii) $\delta \colon Q \times \Sigma \rightarrow Q$ is a transition relation,

(iv) $q_{\text{ini}}$ is the initial state, and

(v) $F \subseteq Q$ are final states.

