Concerning bounded-right-context grammars
| Autor: | Thomas G. Szymanski |
|---|---|
| Rok vydání: | 1976 |
| Předmět: |
Discrete mathematics
General Computer Science Degree (graph theory) Grammar media_common.quotation_subject Context (language use) Theoretical Computer Science Combinatorics Nondeterministic algorithm Rule-based machine translation If and only if Bounded function Computer Science(all) media_common Mathematics |
| Zdroj: | Theoretical Computer Science. 3:273-282 |
| ISSN: | 0304-3975 |
| DOI: | 10.1016/0304-3975(76)90046-3 |
| Popis: | Consider the problem of testing whether a context-free grammar is an (m, n)-BRC grammar. Let ‖G‖ denote the size of the grammar G. It is first shown that G is (m, n)-BRC if and only if G is (m0, n)-BRC where m0=4·‖G‖2·(n + 1)2. Deterministic and nondeterministic algorithms are then presented for testing whether an arbitrary grammar has the (m, n)-BRC property for fixed values of m and n. The running times of both algorithms are low degree polynomials which are independent of m. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|