On the complexity of grammar and related problems
| Autor: | H. B. Hunt, T. G. Szymanski |
|---|---|
| Rok vydání: | 1975 |
| Předmět: |
Discrete mathematics
Structural complexity theory Theoretical computer science Complete Formal language Theory of computation Complexity class Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) Descriptive complexity theory Decision problem Mathematics Quantum complexity theory |
| Zdroj: | STOC |
| DOI: | 10.1145/800116.803753 |
| Popis: | In [1] and [2] a complexity theory for formal languages and automata was developed. This theory implies most of the previously known results and yields many new results as well. Here we develop an analogous theory for several classes of more practically motivated problems. Two such classes, both closely related to formal language and automata theory, suggest themselves - grammar problems and program scheme problems. Here, our primary emphasis is on grammar problems of interest in parsing and compiling. Other problems considered include - (1) possible techniques for proving non-trivial lower complexity bounds for problems in P; (2) the relationship of the complexity of tree automaton equivalence, structural equivalence, and grammatical covering; and (3) the complexity of the equivalence problem for schemes. In each case we relate the computational complexity of a problem to its underlying combinatorial structure. The remainder of the paper is divided into four sections. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|