Dichotomization, reachability, and the forbidden subgraph problem(Extended Abstract)
| Autor: | H. B. Hunt, T. G. Szymanski |
|---|---|
| Rok vydání: | 1976 |
| Předmět: |
Discrete mathematics
Post correspondence problem TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES Membership problem Rule-based machine translation Reachability Simple (abstract algebra) Reachability problem Formal language Computer Science::Formal Languages and Automata Theory Mathematics Automaton |
| Zdroj: | STOC |
| DOI: | 10.1145/800113.803640 |
| Popis: | We present several techniques for proving lower bounds that can be applied to problems about grammars, formal languages, program schemes, simple programming languages, and automata. These techniques include dichotomization, extensions of dichotomization to certain classes of relational problems, recursive analogues of the Post Correspondence Problem, and the reachability problem. These techniques provide many new lower bounds and provide a unified framework for viewing much of the work on the complexity of problems about grammars, languages, schemes, and automata. We show how to prove the undecidability of a problem by efficiently reducing the membership problem for Tms that always halt to it. We also introduce the forbidden subgraph problem. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|