The Narayana Morphism and Related Words

2025/03/02 by Shallit, Jeffrey · 3 citations
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #Number Theory (math.NT)

paper · doi:10.48550/arxiv.2503.01026

Abstract

The Narayana morphism ν maps 0 → 01, 1 → 2, 2 → 0 and has a fixed point n = n₀ n₁ n₂ ⋯ = \tt 0120010120120⋯. In this paper we study the properties of this word and related words using automata theory.

Cited by

• Variants of Wythoff game with terminal positions or blocking maneuvers
• On two conjectures of Shallit about Thue-Morse-like sequences
• Deconstructing Subset Construction -- Reducing While Determinizing

Related

• A new generalization of the Narayana numbers inspired by linear operators on associative d-ary algebras
• Narayana's cows numbers which are concatenations of three repdigits in base ρ
• A Note on Generalized Narayana Numbers
• Kreweras's Narayana number identity has a simple Dyck path interpretation
• Members of Narayana's cow sequence that are concatenations of two repdigits