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...
Autor principal: | |
---|---|
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 |