The non-trivial extension of Fibonacci words to Fibonacci arrays was proposed by Apostolico and Brimkov in order to study repetitions in arrays. In this paper we investigate several combinatorial as well as formal language theoretic properties of Fibonacci arrays. In particular, we show that the set of all Fibonacci arrays is a 2D primitive language (under certain conditions), count the number of borders in Fibonacci arrays, and show that the set of all Fibonacci arrays is a non-recognizable language. We also show that the set of all square Fibonacci arrays is a two dimensional code. © Springer Nature Switzerland AG 2019.

Kalpana Mahalingam

Department of Mathematics

Manasi S. Kulkarni

M. Sivasankar

Formal languages

FIBONACCI ARRAYS

FIBONACCI WORD

PICTURE LANGUAGES

PRIMITIVITY

TWO DIMENSIONAL CODES

Binary sequences

IIT Madras is a public technical and research university located in Chennai, Tamil Nadu. Founded in 1959, it is recognised as an Institute of National Importance.

IIT Madras has been ranked as the top engineering institute in India for four years in a row by the National Institutional Ranking Framework of the MHRD

It currently offers undergraduate, postgraduate and research degrees across 16 disciplines in Engineering, Sciences, Humanities and Management. About 596 faculty belonging to science and engineering departments and centres of the Institute are engaged in teaching, research and industrial consultancy.

IIT Madras

Combinatorial Properties of Fibonacci Arrays.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

A two-dimensional word (2D) is a rectangular finite array of letters from the alphabet Σ. A 2D word is said to be a 2D palindrome if it is equal to its reverse image. In this paper, we study some combinatorial properties of 2D palindromes. In particular, we provide a sufficient condition under which a 2D word is said to be a 2D palindrome, discuss the necessary and sufficient condition under which a 2D word can be decomposed into 2D palindromes, and find the relation between the set of all 2D palindromes and the set of all 2D primitive words. We also show that the set of all 2D palindromes is not a recognizable language, and study a special class of 2D palindromes, namely 2D palindrome square words. © Springer International Publishing AG 2017.

Journal	Data powered by TypesetLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Publisher	Data powered by TypesetSpringer Verlag
ISSN	03029743
Open Access	No