Machine characterization of eol-regular matrix systems

Abstract

In formal language theory, a traditional topic is to characterize classes of languages by machine models. Motivated by the idea of extending the machine characterization of L systems to two dimensions and at the same time to generate interesting picture classes we propose in this paper a new model called EOL-Regular Matrix Systems (EOL-RMS). EOL-RM languages are obtained by substituting regular sets vertically into EOL languages. First a horizontal line of intermediates is generated by an EOL system. Then regular sets are substituted vertically for each intermediate eel! resulting in a rectangular array. We propose in this paper Restricted Pushdown Array of Counters-Finite Matrix Automaton (RPAC-FMA) and show that a lanauge is RPAC-FM Language if and only if it is a EOL-RM Language.

Keywords:

• EOL-Regular Matrix Systems
• EOL-RML
• Pushdown Array of Counters-Finite Matrix Automaton (PAC-FMA)
• Restricted Pushdown Array of Counters-Finite Matrix Automaton (RPAC-FMA)

C.R. Categories:

• 5.23