Marcus contextual grammars
type: Item
instance of: scholarly article
title: Marcus contextual grammars
zbMATH Open document ID: 0965.68037
author: Gheorghe Păun
published in: Studies in Linguistics and Philosophy
publication date: 2001-01-16T00:00:00Z
review text: 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 gener…
reviewed by: Neculai Curteanu
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 03B65
Mathematics Subject Classification ID: 68T50
Mathematics Subject Classification ID: 68-02
Mathematics Subject Classification ID: 68Q42
zbMATH DE Number: 1552758
zbMATH Keywords: contextual grammars
zbMATH Keywords: Marcus contextual grammars
zbMATH Keywords: formal language
zbMATH Keywords: semilinearity
zbMATH Keywords: ambiguity
zbMATH Keywords: automata recognition
zbMATH Keywords: insertion grammars
MaRDI profile type: Publication
Recommended article: Q4289280
Recommended article: Q4681306
Recommended article: Q4681309
Recommended article: Q4236233
Recommended article: Some periodicity of words and Marcus contextual grammars
Recommended article: Some results on contextual grammars∗
Recommended article: On some open problems about marcus contextual languages
Recommended article: Q4905124
Recommended article: Bracketed contextual grammars
Recommended article: Q3691075
description: scientific article; zbMATH DE number 1552758