On Pell, Narayana and Padovan Languages and Their Generalizations

Abstract

In this article, we study several languages associated with classical integer sequences such as the Pell, Narayana, and Padovan sequences, as well as various generalizations. Some of these languages arise naturally in the context of graph theory. We show that a subset of these languages is isomorphic to languages generated by natural word morphisms associated with the corresponding sequences, while others are not isomorphic to any language generated by such morphisms.