Construction of Contextual Grammars

• Autorzy: Novotny M.
• Języki publikacji: EN

Abstrakty

EN

The concept of a contextual grammar is slightly generalized here; the generalized grammars called contextual hypergrammars admit to introduce the so called reducing operators. Using some results concerning these operators a construction is described assigning a contextual grammar Gn(V,L) to any language (V,L) and to any nonnegative integer n. This construction has the following property: The language (V,L) is generated by a contextual grammar if and only if there exists a nonnegative integer n0 such that Gn(V,L) = Gn0(V,L) for any > n0.

Słowa kluczowe

EN

contextual hypergrammar; contextual grammars; reducing operator

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

Twórcy

autor

Novotny M.

• Faculty of Informatics, Masaryk University, Botanicka 68a, 60200 Brno, Czech Republic,

Bibliografia

• [1] Fu, K.S., Taylor, L.B.: Grammatical inference: Introduction and survey, IEEE Transactions on Systems, Man and Cybernetics, Vol. SMC-5, No. 1 (1975), 95–111.
• [2] Gold, E.M.: Language identification in the limit, Information and Control, 10 (1967), 447–474.
• [3] Marcus, S.: Contextual grammars, Rev. Roum. Math. Pures et Appl., 14, 10 (1969), 1525–1534.
• [4] Marcus, S.: Algebraic Linguistics; Analytical Models, Academic Press, New York and London, 1967.
• [5] Marcus, S.: Contextual grammars, learning processes and the Kolmogorov-Chaitin metaphor, MFCS’98 Workshop ‘Mathematical Linguistics’ Proceedings (Ed. M. Kudlek), Universit¨at Hamburg, Fachbereich Informatik, Bericht 213, 1–12.
• [6] Martinek, P.: On a Construction of Context-free Grammars, Fundamenta Informaticae 44 (2000), 245–264.
• [7] Novotn´y, M.: On some operators reducing generalized grammars, Information and Control 26 (1974), 225–235.
• [8] Novotny, M.: Construction of Pure Grammars, Fundamenta Informaticae 52 (2002), 345–360.
• [9] Păun, G.: Gramatici Contextuale (Contextual grammars), Editura Academiei Republicii Socialiste Romania, Bucharest, 1982.
• [10] Păun, G.: Marcus Contextual Grammars, Kluwer, Boston–Dordrecht, 1997