Planar digraphs for automatic complexity

2019/02/02 by Beros, Achilles A., Kjos-Hanssen, Bjørn, Yogi, Daylan Kaui · 1 citation
#Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #Logic (math.LO)

paper · doi:10.48550/arxiv.1902.00812

Abstract

We show that the digraph of a nondeterministic finite automaton witnessing the automatic complexity of a word can always be taken to be planar. In the case of total transition functions studied by Shallit and Wang, planarity can fail. Let s_q(n) be the number of binary words x of length n having nondeterministic automatic complexity A_N(x)=q. We show that s_q is eventually constant for each q and that the eventual constant value of s_q is computable.

Cited by

• Languages of Words of Low Automatic Complexity Are Hard to Compute

Related

• Languages of Words of Low Automatic Complexity Are Hard to Compute
• Arithmetical subword complexity of automatic sequences
• Maximal automatic complexity and context-free languages
• Lengths of Words Accepted by Nondeterministic Finite Automata
• Planar Graphs: Logical Complexity and Parallel Isomorphism Tests