Marcus contextual grammars (Q1592313)

Contextual grammars have been introduced by Solomon Marcus in the late sixties and they currently represent a well-developed branch within the field of formal language theory. Professor Marcus explained the circumstances and motivation of introducing contextual grammars as follows: ``Contextual grammars are one component in the efforts to bridge two important complementary strategies in the study of natural language: the generative approach to syntactic structures and the analytical mathematical models of languages''. Since Natural Languages (NLs) are known to be non-context-free, the class of the so-called mildly context-sensitive generative formalisms have been designed in order: to contain the context-free languages; to cover the specific non-context-free constructions in NLs; to be suitably parsable (in polynomial time); to have the bounded growth property etc. Marcus Contextual Grammars (MCGs) are intended to be such a mildly context-sensitive formalism, introducing an intrinsic generative mechanism, without using auxiliary symbols, based not on rewriting but on the fundamental linguistic operation of adjoining strings/contexts according to a selection procedure. The association of certain strings with certain contexts (pairs of strings), with respect to the idea of (string) well-formedness within a given language, represents a basic idea in descriptive linguistics. MCGs are just trying to capture this strings-contexts interaction, under the form of a generative device. Several variants of MCGs provide a special relevance for the study of NLs. Among them have to be mentioned the so-called internal contextual grammars with maximal use of selectors. The present monograph covers all major developments on MCGs, and substantially extends and updates the author's first monograph on MCGs, written in Romanian (1982). There are included important (new) topics about semilinearity, ambiguity, automata recognition and characterization, complexity structure of strings generated (parsed) by MCGs, the dual model of insertion grammars (where strings are inserted into a given context), marked-derivation and pattern-based MCGs, two-level MCGs, etc. In a separate chapter, G. Păun, whose major contribution to the development of MCG formalism is incontestably acknowledged, collects a set of problems of special interest for further investigation, mainly oriented to the study of NLs on the basis of MCGs. The book addresses a large category of readers: computer scientists, (computational) linguists, mathematicians, logicians, language philosophers, programmers looking for improved theoretical models, from students to researchers. The contents of this outstanding monograph points out at least two facts: it represents a fundamental contribution to modeling the (linguistic) generative processes, and shows the vigorous and distinct voice of the Romanian schools of mathematics and informatics within the international market of scientific research.