Automatic sequences of rank two

DOI10.1051/ITA/2022006MaRDI QIDQ5044415zbMATH OpenOpenAlexFDO

Authors Jason P. Bell, Jeffrey Shallit

Publication date 31 October 2022

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

automatic sequencecombinatorics on wordsprimitive wordrank two

Mathematics Subject Classification ID

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

Recommendations

• Deciding whether a finite set of words has rank at most two
• Enumeration and decidable properties of automatic sequences
• Periodicity, repetitions, and orbits of an automatic sequence
• Enumeration and decidable properties of automatic sequences
• Words of minimum rank in deterministic finite automata

Cites work

• A decision method for the recognizability of sets defined by number systems
• A DECISION PROBLEM FOR ULTIMATELY PERIODIC SETS IN NONSTANDARD NUMERATION SYSTEMS
• A small aperiodic set of Wang tiles
• A variant of a recursively unsolvable problem
• An algorithm for enumerating all infinite repetitions in a D0L-system
• An aperiodic set of 13 Wang tiles
• Automatic Sequences
• Characterization of circular D0L-systems
• Decidability of periodicity for infinite words
• Decidability of the HD0L ultimate periodicity problem
• Decision problems for semi-Thue systems with a few rules
• Enumeration and decidable properties of automatic sequences
• scientific article; zbMATH DE number 3872709 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• If a DOL language is k-power free then it is circular
• Logic and p-recognizable sets of integers
• On the periodicity of morphisms on free monoids
• Periodicity and ultimate periodicity of D0L systems
• Repetition of subwords in DOL languages
• Repetitiveness of languages generated by morphisms
• Subword complexity and k-synchronization
• The (generalized) Post correspondence problem with lists consisting of two words is decidable
• The equation \(a_ M=b^ Nc^ P\) in a free group
• Ultimate periodicity of b-recognisable sets: a quasilinear procedure
• Uniform tag sequences

Cited in

(2)

• The distribution of elements in automatic double sequences
• The number of primitive words of unbounded exponent in the language of an HD0L-system is finite

This page was built for publication: Automatic sequences of rank two

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