Premium
THE COMPUTATIONAL COMPLEXITY OF THE UNIVERSAL RECOGNITION PROBLEM FOR PARALLEL MULTIPLE CONTEXT‐FREE GRAMMARS
Author(s) -
Kaji Yuichi,
Nakanishi Ryuichi,
Seki Hiroyuki,
Kasami Tadao
Publication year - 1994
Publication title -
computational intelligence
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.353
H-Index - 52
eISSN - 1467-8640
pISSN - 0824-7935
DOI - 10.1111/j.1467-8640.1994.tb00008.x
Subject(s) - context free grammar , computer science , rule based machine translation , computational complexity theory , stochastic context free grammar , context free language , embedded pushdown automaton , context (archaeology) , context sensitive grammar , artificial intelligence , speech recognition , l attributed grammar , algorithm , biology , paleontology
A number of grammatical formalisms have been proposed to describe the syntax of natural languages, and the universal recognition problems for some of those classes of grammars have been studied. A universal recognition problem for a class Q of grammars is the one to decide, taking a grammar G ∈ G and a string ui as an input, whether G can generate w or not. In this paper, the computational complexities of the universal recognition problems for parallel multiple context‐free grammars, multiple context‐free grammars, and their subclasses are discussed.