automata without initial state

[strejcek]

The format states that it is not necessary to specify any initial state. Do we want to support automata without any initial state? Or do we plan to add some rule like "if no initial state is specified, than 0 is initial?" Or is it there just for the case of empty automaton without any state ate all?

[adl]

I'd rather not specify something like a "default" initial state.

An empty automaton cannot have an initial state, so the initial state had to be optional. A non-deterministic automaton can have multiple initial states, so if you consider the initial states as a set, it just sounds natural that when no initial state is specified, that set of initial states is considered empty.

Of course any automaton without initial state has an empty language, so can be reduced to the empty automaton, but I see no reason to impose this optimization in the format.

Note that initial states is also discussed for alternation support in #2. There the initial state can be positive Boolean formula, and a missing initial state would be equivalent to false.

[strejcek]

I don't know any formal definition admitting automata without any initial state. I understand that you want to have an empty automaton that has no state and thus also no initial one (I'm fully ok with this), but I do not see any benefits of non-empty automata without initial state.

Regarding nondeterministic automata: I think that it is natural to require a nonempty set of initial states.

Regarding alternating automata (#2): I expect that initial states will be given by a nonempty positive boolean formula over states. And false is not such a formula.

[adl]

I can point to definitions of a Automata admitting no initial states. For instance Elements of Automata Theory defines the set of initial states I as a subset of the set of states Q (Def. 1.1), and later (Def. 1.13) defines a deterministic automaton has having at most one initial state (in addition to the usual constraints on the outgoing transitions of each state). A Google search for "at most one initial state" returns several papers by other authors using similar definitions.

Any way the point is that as long we have a set of initial states, and that all definitions work with empty sets as well, a restriction to a non-empty set feels artificial (i.e. non-natural) to me. For instance I do not understand how you can accept an empty automaton with no initial state (this is therefore a deterministic automaton) and reject non-deterministic automata with no initial states: the set of DFA is supposed to be included in the set of NFA, and I would expect the same for omega automata.

I agree with you that I wouldn't use an empty set of initial states with a non-empty automaton, but I see no reason to add this as a constraint. To me such a restriction would be similar to saying "you are not allowed to use false in a conjunction, because it's better to write false by itself".

A similar constraint, which I'm against, would be to constrain the listed states to be reachable (from some initial state). Maybe you remember one paper we might have discussed in Rome last year? They define a kind of unambiguous Büchi automata (but not what we call unambiguous) where the non-reachable components are very important: indeed you can complement these unambiguous automata by just complementing the set of initial states.

Come to think of it, the last paper I mentioned should probably convince you more than any other argument, since it shows one case where restricting the set of initial states to be non-empty would not be an option (the complementation would be a pain to define otherwise).

[strejcek]

I'm convinced. Well done.