How to prove that a sequence is not automatic

Allouche, J.-P.; Shallit, J. and Yassawi, R. (2022). How to prove that a sequence is not automatic. Expositiones Mathematicae, 40(1) pp. 1–22.

DOI: https://doi.org/10.1016/j.exmath.2021.08.001

Abstract

Automatic sequences have many properties that other sequences (in particular, non-uniformly morphic sequences) do not necessarily share. In this paper we survey a number of different methods that can be used to prove that a given sequence is not automatic. When the sequences take their values in a finite field F, this also permits proving that the associated formal power series are transcendental over F().

Viewing alternatives

Metrics

Item Actions

Export

You can export this page using these formats Digital Object Identifier - DOI

About

• Item ORO ID
• 78782
• Item Type
• Journal Item
• Project Funding Details

• Funded Project Name	Project ID	Funding Body
  Computing algebraic invariants for symbolic dynamical systems	EP/V007459/1.	EPSRC
  Not Set	2018-04118	NSERC

• Keywords
• automata sequences; morphic sequences; transcendental formal power series
• Academic Unit or School
• Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
  Faculty of Science, Technology, Engineering and Mathematics (STEM)
• Research Group
• Astrobiology
• Copyright Holders
• © 2021 Elsevier.
• Related URLs
• • https://arxiv.org/abs/2104.13072(Other)
• Depositing User
• Reem Yassawi