Characterizations of regular and context-free matrices
Authors:
- 1 January 1974
- journal article
- research article
- Published by Taylor & Francis in International Journal of Computer Mathematics
- Vol. 4 (1-4) , 229-245
Abstract
The u-v theorem for context-free languages is extended to prove an intercalation theorem for the family of context-free matrix languages. A row-wise iteration factor theorem is proved for the families of regular and context-free matrix languages. Characterizations of regular and context-free matrix languages are given in terms of vertical regular sequences and simple operations on vertical regular sequences. Closure of regular and context-free matrix languages under array nondeterministic finite state transducer mappings is established and an image theorem proved. This is used to give another characterization of regular matrix languages. Further it is shown that the family of regular matrix languages is a principal abstract family of matrices (AFM). The effect of string control and array control on these families are examined.Keywords
This publication has 8 references indexed in Scilit:
- Parallel context-free languagesInformation and Control, 1974
- Picture languages with array rewriting rulesInformation and Control, 1973
- Absolutely parallel grammars and two-way finite-state transducersJournal of Computer and System Sciences, 1972
- One-Pass Complexity of Digital Picture PropertiesJournal of the ACM, 1972
- A characterization of context-free languagesJournal of Computer and System Sciences, 1971
- Simple matrix languagesInformation and Control, 1970
- Chains of full AFL'sTheory of Computing Systems, 1970
- On equal matrix languagesInformation and Control, 1969