<p>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. We apply our general methods to pattern languages [1] and multi-pattern lan- guages [2]. Interrelations between multi-pattern languages (or pattern languages) and standard classes of languages such as context-free languages and regular languages are studied. A way to study the descriptional complexity of standard language descriptors (for examples, context-free grammars and regular expressions) and multi-patterns is illustrated. We apply our general methods to several generalizations of regular ex- pressions. A productiveness result for the predicate ?= {0,1}?? is established for synchronized regular expressions [3]. Because of this, many new productiveness re- sults for synchronized regular expressions follow easily. We also apply our general methods to several classes of Lindenmayer systems [4] and of cellular automata [5]. A way of studying the complexity/productiveness of the 0Lness problem is developed and many new results follow from it. For real time one-way cellular automata, we observe that the predicates ?= ?? and ?= {0,1}?? are both productive. Because vi of this, many more general results are presented. For two-way cellular automata, we prove a strong meta-theorem and give a complete characterization for testing containment of any fixed two-way cellular automaton language. Finally, we generalize our methods and apply them to the theory of functions of real variables. In rings, the equivalence to identically 0 function problem which is an analogue of ?= ?? is studied. We show that the equivalence to identically 0 function problem for some classes of elementary functions is productive for different domains including open and closed bounded intervals of real numbers. Two initial results for real fields are also presented.

<p> The exponential nature of Moore's law has inadvertently created huge data storage complexes that are scattered around the world. Data elements are continuously being searched, processed, erased, combined and transferred to other storage units without much regard to power consumption. The need for faster searches and power efficient data processing is becoming a fundamental requirement. Quantum computing may offer an elegant solution to speed and power through the utilization of the natural laws of quantum mechanics. Therefore, minimal cost quantum circuit implementation methodologies are greatly desired. </p><p> This thesis explores the decomposition of group functions and the Walsh spectrum for implementing quantum canonical cascades with minimal cost. Three different methodologies, using group decomposition, are presented and generalized to take advantage of different quantum computing hardware, such as ion traps and quantum dots. Quantum square root of swap gates and fixed angle rotation gates comprise the first two methodologies. The third and final methodology provides further quantum cost reduction by more efficiently utilizing Hilbert spaces through variable angle rotation gates. The thesis then extends the methodology to realize a robust quantum circuit synthesis tool for single and multi-output quantum logic functions.</p>