Growing context-sensitive grammar

Last updated

In formal language theory, a growing context-sensitive grammar is a context-sensitive grammar in which the productions increase the length of the sentences being generated. [1] [2] These grammars are thus noncontracting and context-sensitive. A growing context-sensitive language is a context-sensitive language generated by these grammars.

A context-sensitive grammar (CSG) is a formal grammar in which the left-hand sides and right-hand sides of any production rules may be surrounded by a context of terminal and nonterminal symbols. Context-sensitive grammars are more general than context-free grammars, in the sense that there are languages that can be described by CSG but not by context-free grammars. Context-sensitive grammars are less general than unrestricted grammars. Thus, CSG are positioned between context-free and unrestricted grammars in the Chomsky hierarchy.

In formal language theory, a grammar is noncontracting if all of its production rules are of the form α → β where α and β are strings of nonterminal and terminal symbols, and the length of α is less than or equal to that of β, |α| ≤ |β|, that is β is not shorter than α. A grammar is essentially noncontracting if there may be one exception, namely, a rule S → ε where S is the start symbol and ε the empty string, and furthermore, S never occurs in the right-hand side of any rule.

In formal language theory, a context-sensitive language is a language that can be defined by a context-sensitive grammar. Context-sensitive is one of the four types of grammars in the Chomsky hierarchy.

Contents

In these grammars the "start symbol" S does not appear on the right hand side of any production rule and the length of the right hand side of each production exceeds the length of the left side, unless the left side is S. [1]

These grammars were introduced by Dahlhaus and Warmuth. [3] They were later shown to be equivalent to the acyclic context-sensitive grammars. [3] Membership in any growing context-sensitive language is polynomial time computable; [4] [5] however, the uniform problem of deciding whether a given string belongs to the language generated by a given growing [6] or acyclic [7] context-sensitive grammar is NP-complete.

See also

Related Research Articles

In computer science, an ambiguous grammar is a context-free grammar for which there exists a string that can have more than one leftmost derivation or parse tree, while an unambiguous grammar is a context-free grammar for which every valid string has a unique leftmost derivation or parse tree. Many languages admit both ambiguous and unambiguous grammars, while some languages admit only ambiguous grammars. Any non-empty language admits an ambiguous grammar by taking an unambiguous grammar and introducing a duplicate rule or synonym. A language that only admits ambiguous grammars is called an inherently ambiguous language, and there are inherently ambiguous context-free languages. Deterministic context-free grammars are always unambiguous, and are an important subclass of unambiguous grammars; there are non-deterministic unambiguous grammars, however.

In computational complexity theory, P, also known as PTIME or DTIME(nO ), is a fundamental complexity class. It contains all decision problems that can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.

In computational complexity theory, the complexity class PH is the union of all complexity classes in the polynomial hierarchy:

In formal language theory, a grammar is in Kuroda normal form if all production rules are of the form:

In the mathematical discipline of graph theory, a feedback vertex set of a graph is a set of vertices whose removal leaves a graph without cycles. In other words, each feedback vertex set contains at least one vertex of any cycle in the graph. The feedback vertex set problem is an NP-complete problem in computational complexity theory. It was among the first problems shown to be NP-complete. It has wide applications in operating systems, database systems, and VLSI chip design.

In computer science, a termination analysis is program analysis which attempts to determine whether the evaluation of a given program will definitely terminate. Because the halting problem is undecidable, termination analysis cannot be total. The aim is to find the answer "program does terminate" whenever this is possible. Without success the algorithm working on the termination analysis may answer with "maybe" or continue working infinitely long.

In formal language theory, deterministic context-free languages (DCFL) are a proper subset of context-free languages. They are the context-free languages that can be accepted by a deterministic pushdown automaton. DCFLs are always unambiguous, meaning that they admit an unambiguous grammar. There are non-deterministic unambiguous CFLs, so DCFLs form a proper subset of unambiguous CFLs.

A straight-line grammar is a formal grammar that generates exactly one string. Consequently, it does not branch nor loop.

In structural complexity theory, the Berman–Hartmanis conjecture is an unsolved conjecture named after Leonard C. Berman and Juris Hartmanis that states that all NP-complete languages look alike, in the sense that they can be related to each other by polynomial time isomorphisms.

Dis-unification, in computer science and logic, is an algorithmic process of solving inequations between symbolic expressions.

In computational learning theory, induction of regular languages refers to the task of learning a formal description of a regular language from a given set of example strings. Although Mark E. Gold has shown that not every regular language can be learned this way, approaches have been investigated for a variety of subclasses. They are sketched in this article. For learning of more general grammars, see Grammar induction.

Set constraint

In mathematics and theoretical computer science, a set constraint is an equation or an inequation between sets of terms. Similar to systems of (in)equations between numbers, methods are studied for solving systems of set constraints. Different approaches admit different operators on sets and different (in)equation relations between set expressions.

In computational linguistics, the term mildly context-sensitive grammar formalisms refers to several grammar formalisms that have been developed with the ambition to provide adequate descriptions of the syntactic structure of natural language.

Jean-Pierre Jouannaud French computer scientist

Jean-Pierre Jouannaud is a French computer scientist, known for his work in the area of term rewriting.

Nachum Dershowitz is an Israeli computer scientist, known e.g. for the Dershowitz–Manna ordering used to prove termination of term rewrite systems.

Wayne Snyder is an associate professor at Boston University known for his work in E-unification theory.

Tobias Nipkow is a German computer scientist. He received his Diplom (MSc) in computer science from the Technische Hochschule Darmstadt in 1982, and his Ph.D. from the University of Manchester in 1987. He worked at MIT from 1987, changed to Cambridge University in 1989, and to Technical University Munich in 1992, where he was appointed professor for programming theory. He is chair of the Logic and Verification group since 2011.

References

  1. 1 2 G. Buntrock and F. Otto (1995). "Growing Context-Sensitive Languages and Church-Rosser Languages". In Ernst W. Mayr and Claude Puech (ed.). Proc. 12th STACS. LNCS. 900. Springer. pp. 313–324. ISBN   978-3540590422. Here: p.316-317
  2. ↑ Gerhard Buntrock and Friedrich Otto (1998). "Growing Context-Sensitive Languages and Church-Rosser Languages". Information and Computation. 141: 1–36. doi:10.1006/inco.1997.2681.
  3. 1 2 Gundula Niemann and Jens R. Woinowski (2002). "The Growing Context-Sensitive Languages Are the Acyclic Context-Sensitive Languages". In Werner Kuich and Grzegorz Rozenberg and Arto Salomaa (ed.). Proc. 5th Int. Conf on Developments in Language Theory (DLT). Lecture Notes in Computer Science. 2295. Springer. pp. 197–205. ISBN   978-3540434535.. Here: p.197-198
  4. ↑ E. Dahlhaus und M.K. Warmuth (1986). "Membership for growing context-sensitive grammars is polynomial". In Paul Franchi-Zannettacci (ed.). Proc. 11th Colloquium on Trees in Algebra and Programming (CAAP) (PDF). LNCS. 214. Springer. pp. 85–99. Here: p.85-86
  5. ↑ E. Dahlhaus und M.K. Warmuth (1986). "Membership for growing context-sensitive grammars is polynomial". Journal of Computer and System Sciences. 33 (3): 456–472. doi:10.1016/0022-0000(86)90062-0.
  6. ↑ G. Buntrock and K. Lorys. On growing context-sensitive languages. In Proc. 19th ICALP, Lecture Notes in Computer Science (W. Kuich,ed, pages 77–88. Springer-Verlag, 1992.
  7. ↑ Erik Aarts (1992). "Uniform recognition for context-sensitive grammars is NP-complete" (PDF). Proc. 14th Int. Conf. on Computational Linguistics (COLING, Nantes, Aug. 23-28). pp. 1157–1161.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.