Planar digraphs for automatic complexity

DOI10.1007/978-3-030-14812-6_5MaRDI QIDQ6313491arXivFDO

Authors Achilles A. Beros, Bjørn Kjos-Hanssen, Daylan Kaui Yogi

Publication date 2 February 2019

Published in arXiv

Full work available at URL https://doi.org/10.1007/978-3-030-14812-6_5

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10)

arXiv classification

cs.FL math.CO math.LO

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.

This page was built for publication: Planar digraphs for automatic complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6313491)