Word Matrix Rewriting Systems

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 a₁, . . . , a_k). 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., {aⁿbⁿcⁿ | 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.