From Context-Free Languages to Mildly Context-Sensitive Languages Complexity Views

Authors

  • Liliana Cojocaru „Petre Andrei” University of Iaşi, Romania Author

DOI:

https://doi.org/10.63331/upalaw/32/03

Keywords:

context-free languages, alternating Turing machines, Boolean matrix multiplication

Abstract

The class of context-free languages is the second class in the Chomsky hierarchy, and probably it is the most exciting one. It is easy to be parsed but not trivial, it is rich in algebraic and combinatorial properties, it stands at the basis of programming languages, and besides, it provides structural patterns for the so called mildly context-sensitive formalisms used in Natural Language Processing. Usually parsing algorithms for mildly context-sensitive grammars are generalized parsing algorithms for context-free grammars. In this paper we deal with the main parsing algorithms for context-free and mildly context-sensitive grammars, motivated by potential applications in Computational Complexity, Parsing Theory and DNA Computing. These algorithms are based on graphical, combinatorial, or algebraic approaches, on Boolean matrix multiplication techniques and on regular approximations for context-free and mildly context-sensitive languages.

Author Biography

  • Liliana Cojocaru, „Petre Andrei” University of Iaşi, Romania

    Lecturer Ph.D., „Petre Andrei” University of Iaşi & „Alexandru Ioan Cuza” University, Departament of Computer Science

Downloads

Published

2025-05-11

Issue

Vol. 32 (2024): Anuarul Universitatii "Petre Andrei" din Iasi - Fascicula: Drept, Stiinte Economice, Stiinte Politice

Section

Articles

License

Copyright (c) 2025 Anuarul Universitatii "Petre Andrei" din Iasi & POLIS BOOKS Puplishing House

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Authors who publish with this journal agree to the following terms:

  • Authors retain copyright and grant this journal right of first publication, with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work, with an acknowledgement of the work's authorship and initial publication in this journal.
  • Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g. post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
  • Authors are permitted and encouraged to post their work online (e.g. in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as an earlier and greater citation of published work (See The Effect of Open Access).