Cargando…

Complexity of Automatic Sequences

Automatic sequences can be defined by DFAs with output (DFAO) in two natural ways. We propose to consider the minimal size of a corresponding DFAO as the complexity measure of the automatic sequence, for both variants. This paper compares these complexity measures and investigates their properties l...

Descripción completa

Detalles Bibliográficos
Autor principal: Zantema, Hans
Formato: Online Artículo Texto
Lenguaje:English
Publicado: 2020
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7206635/
http://dx.doi.org/10.1007/978-3-030-40608-0_18
_version_ 1783530448068018176
author Zantema, Hans
author_facet Zantema, Hans
author_sort Zantema, Hans
collection PubMed
description Automatic sequences can be defined by DFAs with output (DFAO) in two natural ways. We propose to consider the minimal size of a corresponding DFAO as the complexity measure of the automatic sequence, for both variants. This paper compares these complexity measures and investigates their properties like the relationships with kernel and morphic sequences. There exist automatic sequences for which the one complexity is exponentially greater than the other one, in both directions. For both complexity measures we investigate the effect of taking basic operations on sequences like removing or adding an element in front, and observe that these operations may increase the complexity by at most a quadratic factor.
format Online
Article
Text
id pubmed-7206635
institution National Center for Biotechnology Information
language English
publishDate 2020
record_format MEDLINE/PubMed
spelling pubmed-72066352020-05-08 Complexity of Automatic Sequences Zantema, Hans Language and Automata Theory and Applications Article Automatic sequences can be defined by DFAs with output (DFAO) in two natural ways. We propose to consider the minimal size of a corresponding DFAO as the complexity measure of the automatic sequence, for both variants. This paper compares these complexity measures and investigates their properties like the relationships with kernel and morphic sequences. There exist automatic sequences for which the one complexity is exponentially greater than the other one, in both directions. For both complexity measures we investigate the effect of taking basic operations on sequences like removing or adding an element in front, and observe that these operations may increase the complexity by at most a quadratic factor. 2020-01-07 /pmc/articles/PMC7206635/ http://dx.doi.org/10.1007/978-3-030-40608-0_18 Text en © Springer Nature Switzerland AG 2020 This article is made available via the PMC Open Access Subset for unrestricted research re-use and secondary analysis in any form or by any means with acknowledgement of the original source. These permissions are granted for the duration of the World Health Organization (WHO) declaration of COVID-19 as a global pandemic.
spellingShingle Article
Zantema, Hans
Complexity of Automatic Sequences
title Complexity of Automatic Sequences
title_full Complexity of Automatic Sequences
title_fullStr Complexity of Automatic Sequences
title_full_unstemmed Complexity of Automatic Sequences
title_short Complexity of Automatic Sequences
title_sort complexity of automatic sequences
topic Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7206635/
http://dx.doi.org/10.1007/978-3-030-40608-0_18
work_keys_str_mv AT zantemahans complexityofautomaticsequences