New measures of automatic complexity arising from quantum logic

The automatic complexity of finite words was introduced by
Shallit and Wang (2001). It measures the complexity of a word x as the
minimum number of states of a finite automaton that uniquely accepts
x. Here, an automaton M uniquely accepts a word x if x is the only
word of length |x| accepted by M. Via the digraph representation of
automata we can view the computation of this number of states as a
problem of extremal graph theory. A quantum version of automatic
complexity was first studied by Kjos-Hanssen (2017). In this talk, we
explore several new measures of automatic complexity motivated by the
geometric subspace structure of the automata and the associated
quantum logic. We consider some generalizations of quantum finite
automata with the application of an immortality constraint,
considering a family of automata without dead states.