We gratefully acknowledge support from
the Simons Foundation and member institutions.
Full-text links:

Download:

Current browse context:

cs.FL

Change to browse by:

References & Citations

DBLP - CS Bibliography

Bookmark

(what is this?)
CiteULike logo BibSonomy logo Mendeley logo del.icio.us logo Digg logo Reddit logo

Computer Science > Formal Languages and Automata Theory

Title: Opacity complexity of automatic sequences. The general case

Abstract: In this work we introduce a new notion called opacity complexity to measure the complexity of automatic sequences. We study basic properties of this notion, and exhibit an algorithm to compute it. As applications, we compute the opacity complexity of some well-known automatic sequences, including in particular constant sequences, purely periodic sequences, the Thue-Morse sequence, the period-doubling sequence, the Golay-Shapiro(-Rudin) sequence, the paperfolding sequence, the Baum-Sweet sequence, the Tower of Hanoi sequence, and so on.
Subjects: Formal Languages and Automata Theory (cs.FL); Combinatorics (math.CO); Number Theory (math.NT)
MSC classes: 94A17, 68Q45, 11B85
Cite as: arXiv:2404.13601 [cs.FL]
  (or arXiv:2404.13601v1 [cs.FL] for this version)

Submission history

From: Jean-Paul Allouche [view email]
[v1] Sun, 21 Apr 2024 10:03:24 GMT (14kb)

Link back to: arXiv, form interface, contact.