Title: Two-dimensional double jumping finite automata

Authors: S. James Immanuel; D. Gnanaraj Thomas

Addresses: Department of Mathematics, Madras Christian College, Tambaram, Chennai, India ' Department of Mathematics, Madras Christian College, Tambaram, Chennai, India

Abstract: In this paper, we extend the concept of double jumping automata for string languages recently introduced in the literature to two-dimensional languages, also called as picture languages. The paper is a modification and study of jumping finite automata for two-dimensional languages already introduced in the literature, where they always perform two simultaneous row-jumps over a row of an input array according to the same rule which is defined. The direction of either of the two simultaneous row-jumps is: 1) left; 2) right or 3) in either direction. Based on the directions of the two simultaneous jumps, we give the classification of the jumping finite automata for two-dimensional languages. The mutual relationship between the families of languages accepted by the two-dimensional jumping finite automata performing the jumps in the ways as mentioned above are investigated. We also give the comparison of these families with that of local and recognisable families of languages and families of Siromoney matrix languages.

Keywords: jumping automata; two-dimensional arrays; picture languages; double jumping.

DOI: 10.1504/IJAISC.2017.10009796

International Journal of Artificial Intelligence and Soft Computing, 2017 Vol.6 No.3, pp.250 - 264

Received: 07 Mar 2017
Accepted: 31 Aug 2017
Published online: 22 Dec 2017 *

Full-text access for editors Access for subscribers Purchase this article Comment on this article