New Measures of Automatic Complexity Arising from Quantum Logic

Abstract: 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. In keeping with the Hallowe'en spirit, We consider some generalizations of quantum finite automata with the application of an immortality constraint, considering a family of automata without dead states.

discrete mathematicsformal languages and automata theoryquantum computing and informationlogicquantum physics

Audience: researchers in the topic

Online logic seminar

Series comments: Description: Seminar on all areas of logic