Planar digraphs for automatic complexity

DOI10.1007/978-3-030-14812-6_5MaRDI QIDQ2327457zbMATH OpenOpenAlexFDO

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

Publication date 15 October 2019

Full work available at URL https://arxiv.org/abs/1902.00812

zbMATH Keywords

automatic complexityMöbius functionnondeterministic finite automataplanar graph

Mathematics Subject Classification ID

Recommendations

• Inherently nonplanar automata
• An incompressibility theorem for automatic complexity
• Automaticity. I: Properties of a measure of descriptional complexity
• On the complexity of automatic complexity
• Automaticity. II: Descriptional complexity in the unary case

Cited in

(1)

• Planar digraphs for automatic complexity

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 Q2327457)