Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 20 of 74 for “"Models of Computation"”.
-
Automata and game theoretic models of computation
In this thesis we investigate two finite state models of computation: automata and games on graphs. First we investigate the state complexity of finite word and tree automata from two directions. One direction is to study the interplay between non-deterministic automata (NFA) and deterministic …
-
Explicit pseudorandom distributions for restricted models of computation
Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2025-02-04 without embargo terms
-
Turing Machines and Automatic Functions as Models of Computation
… input and output have to start at the left end of the tape. It is also shown that the same equivalence holds when non-deterministic one-tape Turing machines are considered. This result is extended to the study of the complexity class AF[log n] which is roughly the class of functions which can be …
-
A Computational Paradigm on Network-Based Models of Computation
The maturation of computer science has strengthened the need to consolidate isolated algorithms and techniques into general computational paradigms. The main goal of this dissertation is to provide a unifying framework which captures the essence of a number of problems in seemingly unrelated …
-
Adapting non-numeric, parallel algorithms for diverse models of computation
<p>The simplicity of the PRAM model avoids communication latency, memory lim-itations and other difficult issues. Efforts have been made to develop more real-istic models, especially with respect to communication, yet the restriction of finite memory space on computer architectures remains …
-
Optimal Graph Streaming Algorithms and Further Advances in Modern Models of Computation
The rise of large-scale datasets across domains such as social networks, biological systems, and the web has made it increasingly important to understand how core graph problems can be solved under tight resource constraints. As these datasets grow, traditional algorithms that assume random access …
-
Categorical models of computation: Partially traced categories and presheaf models of quantum computation
… relating to Haghverdi and Scott's notion of partially traced categories. The main result is a representation theorem for such categories: we prove that every partially traced category can be faithfully embedded in a totally traced category. Also conversely, every monoidal subcategory of a …
-
WhileCC-approximability and Acceptability of Elementary Functions
In this thesis, we study models of computation for partial functions on the reals. Existing work [Fu and Zucker, 2014, Tucker and Zucker, 1999, 2004] studies classes of computable partial functions on R, namely • GL-computability, • tracking computability, • multipolynomial approximability, and • …
-
Computational models relating properties of visual neurons to natural stimulus statistics
The topic of this thesis is mathematical modeling of computations taking place in the visual system, the largest sensory system in the primate brain. While a great deal is known about how certain visual neurons respond to stimuli, a very profound question is why they respond as they do. Here this …
-
Comparing and Evaluating Models of Tile-Assembly Using Intrinsic Simulation
Tile-assembly studies abstract models of computation inspired by advancements in the emerging field of DNA-nanotechnology, where synthetic strands of DNA are used as building blocks for microscopic structures. These DNA strands can be made to combine into structural units with selectively sticky …
-
A Kleene Theorem and Decision Problems for Probability and Angelic Nondeterminism
… to reason about the capabilities and limitations of a specific com-puting model or programming language, a formal system that can model the behavior of a computational device is required. Once such a correspondence is established, we have access to tools to reason about the performed computation …
-
Designing GALS software systems using libraries and run-time OS support
With the increasing use of multicore and distributed computing platforms, software systems are becoming more and more complex and as such require tremendous design effort. They are also very difficult to debug and guarantee for correct functionality. In the case of embedded systems, ideally, …
-
K-PERIODIC SCHEDULING FOR THROUGHPUT-BUFFERING TRADE-OFF EXPLORATION OF CSDF
The design of time-critical embedded systems often requires static models of computation such as Cyclo-Static Dataflow. These models enable performance guarantees, execution correctness, and optimized memory usage. Nonetheless, determining optimal buffer sizing of dataflow applications remains …
-
Asynchronous algorithms for shared memory machines
In an effort to develop more realistic models of computation, we introduce several asynchronous shared memory machines and design asynchronous algorithms for those machines. We first model asynchronous protocols for communication across unreliable channels using finite-state machines communicating …
-
Techniques for analyzing the computational power of constant-depth circuits and space-bounded computation
The subject of computational complexity theory is to analyze the difficulty of solving computational problems within different models of computation. Proving lower bounds is easier in less powerful models and proving upper bounds is easier in the more powerful models. This dissertation studies …
-
Derandomizing space-bounded computation via pseudorandom generators and their generalizations
… extent is randomness necessary for efficient computation? We study the problem of deterministically simulating randomized algorithms with low space overhead. The traditional approach to this problem is to try to design sufficiently powerful pseudorandom generators (PRGs). PRG constructions …
-
Promised streaming algorithms and finding pseudo-repetitions
As the size of data available for processing increases, new models of computation are needed. This motivates the study of data streams, which are sequences of information for which each element can be read only after the previous one. In this work we study two particular types of streaming …
-
The design and implementation of a language environment for evaluating the programming task
… the requirement, design, and implementation of a software package that can be used to perform quantitative studies on certain aspects of a programming task. Of specific interest are experiments with the level of interactiveness of the human-computer interface relating to program construction …
-
The semantics and transformation of imperative programs using horn clauses
The feasibility of using Horn clauses as a means of describing and transforming imperative pro-grams is explored. A logical semantics is derived for a typical imperative language. The style of this semantics permits direct translations between the source language and semantical representations. …
-
System Synthesis from a Monadic Functional Language
Embedded systems typically combine a mixture of heterogeneous components, some that are software executing on general purpose CPUs, some that are off-the-shelf hardware components, and some that are application specific circuitry. A major challenge when designing and implementing such systems is …
Page 1 of 4