Affiliations: [a] Department of Applied Sciences, Amrapali Institute of Technology and Sciences, Lamachaur, Haldwani, (Nainital) Uttarakhand 263139, India. bishtrk@gmail.com | [b] Department of Information Systems, Toyama Prefectural University, Imizu 939-0398, Japan. nishida@pu-toyama.ac.jp
Correspondence:
[*]
Address for correspondence: Department of Information Systems, Toyama Prefectural University, Imizu 939-0398, Japan.
Abstract: We introduce word matrices and word matrix rewriting systems. A word matrix over an alphabet ∑ of k letters is a k × n rectangular matrix with entries of nonnegative integers. A word matrix represents a set of words. The i-th row corresponds to the i-th letter in ∑ (thus the letters in ∑ are ordered as a1, . . . , ak). Each column vector represents a set of words which have the vector as the Parikh vector. The word matrix represents the concatenation of all sets represented by column vectors. A word matrix rewriting system consists of a set of rewriting rules which rewrite word matrices and an initial word matrix (the axiom). A word matrix rewriting system generates a set of word matrices by iterated applications of rules to the axiom and generates a language which is the union of all sets represented by the matrices. A word matrix rewriting system is a kind of (restricted) parallel rewriting system with scattered context dependency and hence can generate non-context-free languages, e.g., {anbncn | 1 ≤ n}. We define variants of word matrix rewriting systems and show an infinite hierarchy among them. Some language theoretical problems, including relations among Chomsky hierarchy, closure properties, and decision properties, are considered.
Keywords: restricted parallel rewriting, Parikh vector, regular languages, context-free languages
