Contextual Grammars with Subregular Choice

• Autorzy: Dassow J.
• Języki publikacji: EN

Abstrakty

EN

We discuss external contextual grammars with choice where the choice language belongs to a family of subregular languages. We determine the hierarchy of language families of contextual languages which is obtained by the use of nilpotent, combinational, definite, regular suffix closed, and regular commutative languages as choice languages.

Słowa kluczowe

EN

contextual grammars; controlled derivations; subregular languages

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2005
• Tom: Vol. 64, nr 1-4
• Strony: 109--118
• Opis fizyczny: Bibliogr. 15 poz.

Twórcy

autor

Dassow J.

• Otto-von Guericke Universität Magdeburg, Fakultät für Informatik, PSF 4120, D-39016 Magdeburg , Germany,

Bibliografia

• [1] J. Dassow and H. Hornig, Conditional grammars with subregular conditions. In: Proc. Internat. Conf. Words, Languages and Combinatorics II (Eds.: M. Ito and H. J¨urgensen),World Scientific, Singapore, 1994, 71–86.
• [2] A. Ehrenfeucht, Gh. P˘aun, and G. Rozenberg, Contextual grammars and formal languages. In [13], 237–293.
• [3] F. Gecseg and I. Peak, Algebraic Theory of Automata. Academiai Kiado, Budapest, 1972.
• [4] A. Gill and L.T. Kou, Multiple-entry finite automata. J. Comp. Syst. Sci. 9 (1974) 1–19.
• [5] I.M. Havel, The theory of regular events II. Kybernetika 6 (1969) 520–544.
• [6] S. Istrail, Gramatici contextuale cu select¸ie regulat˘a. Stud. Cerc. Mat. 30 (1978) 287–294.
• [7] S. Marcus, Contextual grammars. Revue Roum. Math. Pures Appl. 14 (1969) 1525–1534.
• [8] S. Marcus, Contextual grammars and natural languages. In [13], 215–235.
• [9] Gh. Păun, On some classes of contextual grammars. Bull. Math. de la Soc. de Sci. Math. de R.S.R. 22 (1978) 183–189.
• [10] Gh. Păun, Grammatici Contextuale. Editura Acad. Rep. Soc. Romania, Bucharest, 1982.
• [11] Gh. Păun, Marcus Contextual Grammars. Kluwer Publ. House, Dordrecht, 1998.
• [12] M. Perles, M.O. Rabin, and E. Shamir, The theory of definite automata. IEEE Trans. Electronic Computers 12 (1963) 233–243.
• [13] G. Rozenberg and A. Salomaa (Eds.), Handbook of Formal Languages, Vol. I–III. Springer-Verlag, 1997.
• [14] G. Thierrin, Some properties of the languages accepted by multiple-entry finite automata. Manuscript, Department of Mathematics, The University of Western Ontario.
• [15] B. Wiedemann, Vergleich der Leistungsf¨ahigkeit endlicher determinierter Automaten. Diplomarbeit, Universität Rostock, 1978.