We consider first an operation with strings and languages suggested by superposed windows on the computer screen (as well as by cryptographic systems of Richelieu type): we assume that the strings contain usual symbols as well as a transparent symbol. Superposing two strings (justified to left), we produce a new string consisting of the symbols visible from above. This operation is investigated as an abstract operation on strings, then it is used in building a variant of grammar systems with the component grammars working on the layers of an array of strings. Each grammar can rewrite only symbols in its layers which are visible from above. The language generated in this way consists of strings of the visible symbols, produced at the end of a derivation. The power of several variants of these generative mechanisms is investigated for the case of two layered strings. When a matrix-like control on the work of the component grammars is considered, then a characterization of recursively enumerable languages is obtained.
Recommendations
Prefix and Suffix Reversals on Strings
SPIRE 2015: Proceedings of the 22nd International Symposium on String Processing and Information Retrieval - Volume 9309The Sorting by Prefix Reversals problem consists in sorting the elements of a given permutation $$\pi $$ with a minimum number of prefix reversals, i.e. reversals that always imply the leftmost element of $$\pi $$. A natural extension of this problem is ...
Fast Learning from Strings of 2-Letter Rigid Grammars
ICGI '02: Proceedings of the 6th International Colloquium on Grammatical Inference: Algorithms and ApplicationsIt is well-known that certain classes of classical categorial grammars are learnable, within Gold's paradigm of identification in the limit, from positive examples. In the search for classes which can be learned efficiently from strings, we study the ...