Date of Award

1-1-2017

Language

English

Document Type

Dissertation

Degree Name

Doctor of Philosophy (PhD)

College/School/Department

Department of Computer Science

Content Description

1 online resource (ix, 103 pages) : illustrations

Dissertation/Thesis Chair

Harry B Hunt, III

Committee Members

Harry B Hunt, III, Richard E Stearns, Paliath Narendran

Keywords

Cellular Automata, Computational Complexity Theory, Lindenmayer Systems, Pattern Matching, Theory of Computation, Theory of functions of real variables, Computational complexity, Formal languages, Cellular automata, L systems, Complexity (Linguistics)

Subject Categories

Computer Sciences | Mathematics

Abstract

In this dissertation, we emphasize productiveness not just undecidability since pro- ductiveness implies constructive incompleteness. Analogues of Rice’s Theorem for different classes of languages are investigated, refined and generalized. In particular, several sufficient but general conditions are presented for predicates to be as hard as some widely discussed predicates such as “= ∅” and “= {0,1}∗”. These conditions provide several general methods for proving complexity/productiveness results and apply to a large number of simple and natural predicates. As the first step in apply- ing these general methods, we investigate the complexity/productiveness of the pred- icates “= ∅”, “= {0,1}∗” and other predicates that can be useful sources of many- one reductions for different classes of languages. Then we use very efficient many- one reductions of these basic source predicates to prove many new non-polynomial complexity lower bounds and productiveness results. Moreover, we study the com- plexity/productiveness of predicates for easily recognizable subsets of instances with important semantic properties. Because of the efficiency of our reductions, intuitively these reductions can preserve many levels of complexity.

Download

Share

COinS