Marcus Contextual Grammars

1. Front Matter

   Pages i-xiv

   PDF

2. Origin and Motivation

   • Gheorghe Păun

   Pages 1-6

3. Formal Language Theory Prerequisites

   • Gheorghe Păun

   Pages 7-23

4. Contexts (Adjoining) Everywhere

   • Gheorghe Păun

   Pages 25-32

5. Basic Classes of Contextual Grammars

   • Gheorghe Păun

   Pages 33-41

6. Generative Capacity

   • Gheorghe Păun

   Pages 43-55

7. Language Theoretic Properties

   • Gheorghe Păun

   Pages 57-69

8. Linguistically Relevant Properties

   • Gheorghe Păun

   Pages 71-127

9. Grammars with Restricted Selection

   • Gheorghe Păun

   Pages 129-163

10. Grammars with Minimal/Maximal Use of Selectors

    • Gheorghe Păun

    Pages 165-184

11. Variants of Contextual Grammars

    • Gheorghe Păun

    Pages 185-243

12. Two-Level Contextual Grammars

    • Gheorghe Păun

    Pages 245-256

13. Regulated Contextual Grammars

    • Gheorghe Păun

    Pages 257-265

14. A Generalization: n-Contextual Grammars

    • Gheorghe Păun

    Pages 267-278

15. A Dual Model: Insertion Grammars

    • Gheorghe Păun

    Pages 279-305

16. Further Topics

    • Gheorghe Păun

    Pages 307-347

17. Open Problems and Research Topics

    • Gheorghe Păun

    Pages 349-354

18. Back Matter

    Pages 355-378

    PDF

Marcus Contextual Grammars is the first monograph to present a class of grammars introduced about three decades ago, based on the fundamental linguistic phenomenon of strings-contexts interplay (selection). Most of the theoretical results obtained so far about the many variants of contextual grammars are presented with emphasis on classes of questions with relevance for applications in the study of natural language syntax: generative powers, descriptive and computational complexity, automata recognition, semilinearity, structure of the generated strings, ambiguity, regulated rewriting, etc. Constant comparison with families of languages in the Chomsky hierarchy is made. Connections with non-linguistic areas are established, such as molecular computing.
Audience: Researchers and students in theoretical computer science (formal language theory and automata theory), computational linguistics, mathematical methods in linguistics, and linguists interested in formal models of syntax.

• Syntax
• automata
• automata theory
• cognition
• complexity
• computational linguistics
• computer
• computer science
• formal language
• grammar
• linguistics
• natural language
• theoretical computer science

• Institute of Mathematics of the Romanian Academy, Bucharest, Romania

  Gheorghe Păun

Policies and ethics