Morphisms on infinite alphabets, countable states automata and regular sequences

DOI10.1016/J.CHAOS.2017.04.018MaRDI QIDQ1674337zbMATH OpenOpenAlexFDO

Authors Jiemeng Zhang, Jin Chen, Ying-Jun Guo, Zhixiong Wen

Publication date 2 November 2017

Published in Chaos, Solitons and Fractals (Search for Journal in Brave)

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

zbMATH Keywords

automatic sequenceregular sequencemorphismlinear recurrencecountable states automaton

Mathematics Subject Classification ID

Combinatorics on words (68R15) Recurrences (11B37) Automata sequences (11B85)

Abstract: In this paper, we prove that a class of regular sequences can be viewed as projections of fixed points of uniform morphisms on a countable alphabet, and also can be generated by countable states automata. Moreover, we prove that the regularity of some regular sequences is invariant under some codings.

Recommendations

• Automaton transformations and monadic theories of infinite sequences
• scientific article; zbMATH DE number 3983141
• Infinity problems and countability problems for -automata
• Automata over infinite alphabets
• scientific article; zbMATH DE number 1522569
• Automata over infinite sequences of reals
• P Finite Automata and Regular Languages over Countably Infinite Alphabets
• Automata and Logics for Words and Trees over an Infinite Alphabet
• scientific article; zbMATH DE number 1834677

Cites work

• scientific article; zbMATH DE number 5707089 (Why is no real title available?)
• scientific article; zbMATH DE number 4071020 (Why is no real title available?)
• scientific article; zbMATH DE number 1973372 (Why is no real title available?)
• scientific article; zbMATH DE number 1548996 (Why is no real title available?)
• scientific article; zbMATH DE number 2087217 (Why is no real title available?)
• Analytic functions over \(\mathbb Z_p\) and \(p\)-regular sequences
• Arithmetics properties of substitutions and infinite automata
• Automatic Sequences
• Avoiding squares and overlaps over the natural numbers
• Drunken man infinite words complexity
• Enumeration and decidable properties of automatic sequences
• Finite automata in number theory
• Non-Regularity of ⌊α + log k n⌋
• On complexity functions of infinite words associated with generalized Dyck languages
• On some questions regarding \(k\)-regular and \(k\)-context-free sequences
• On the complexity of infinite words generated by countable \(q\)-automata
• On the regular sum-free sets
• Properties and limits of recognition of sets of integers by countable automata
• Substitution dynamical systems on infinite alphabets
• Substitutions in dynamics, arithmetics and combinatorics
• Suites algébriques, automates et substitutions
• The minimal growth of a \(k\)-regular sequence
• The ring of \(k\)-regular sequences
• The ring of \(k\)-regular sequences. II.
• Uniform tag sequences

Cited in

(3)

• On a possible classification of real-time constructed sequences
• Regular Mappings of Sequence Spaces over Finite Fields
• Some properties of the Fibonacci sequence on an infinite alphabet

This page was built for publication: Morphisms on infinite alphabets, countable states automata and regular sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1674337)