caa a22 4500 445869658 CHVBK 20180317145507.0 cr unu---uuuuu 170323e20110501xx s 000 0 eng 10.1007/s00236-011-0134-y doi (NATIONALLICENCE)springer-10.1007/s00236-011-0134-y One-sided random context grammars [Elektronische Daten] [Alexander Meduna, Petr Zemek] The notion of a one-sided random context grammar is defined as a context-free-based regulated grammar, in which a set of permitting symbols and a set of forbidding symbols are attached to every rule, and its set of rules is divided into the set of left random context rules and the set of right random context rules. A left random context rule can rewrite a nonterminal if each of its permitting symbols occurs to the left of the rewritten symbol in the current sentential form while each of its forbidding symbols does not occur there. A right random context rule is applied analogically except that the symbols are examined to the right of the rewritten symbol. The paper demonstrates that without erasing rules, one-sided random context grammars characterize the family of context-sensitive languages, and with erasing rules, these grammars characterize the family of recursively enumerable languages. In fact, these characterization results hold even if the set of left random context rules coincides with the set of right random context rules. Several special cases of these grammars are considered, and their generative power is established. In its conclusion, some important open problems are suggested to study in the future. Springer-Verlag, 2011 Meduna Alexander Department of Information Systems, Faculty of Information Technology, Brno University of Technology, Božetěchova 2, 61266, Brno, Czech Republic aut Zemek Petr Department of Information Systems, Faculty of Information Technology, Brno University of Technology, Božetěchova 2, 61266, Brno, Czech Republic aut Acta Informatica Springer-Verlag 48/3(2011-05-01), 149-163 0001-5903 48:3<149 2011 48 236 https://doi.org/10.1007/s00236-011-0134-y text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00236-011-0134-y text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Meduna Alexander Department of Information Systems, Faculty of Information Technology, Brno University of Technology, Božetěchova 2, 61266, Brno, Czech Republic aut NATIONALLICENCE 700 1- Zemek Petr Department of Information Systems, Faculty of Information Technology, Brno University of Technology, Božetěchova 2, 61266, Brno, Czech Republic aut NATIONALLICENCE 773 0- Acta Informatica Springer-Verlag 48/3(2011-05-01), 149-163 0001-5903 48:3<149 2011 48 236 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer