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 27 for “"state complexity"”.
-
State Complexity of Tree Automata
… on unranked trees uses a set of vertical states that define the bottom-up computation, and the transitions on vertical states are determined by so called horizontal languages recognized by finite automata on strings. The bottom-up computation of an unranked tree automaton may be either …
-
Nondeterministic State Complexity of Site-Directed Operations
In this thesis, we consider the nondeterministic state complexity of PCR-inspired (polymerase chain reaction) operations. Site-directed operations are used to formally describe the behavior of certain DNA (deoxyribonucleic acid) editing methods which need to identify a subsequence in a host DNA …
-
Algebraic Approaches to State Complexity of Regular Operations
The state complexity of operations on regular languages is an active area of research in theoretical computer science. Through connections with algebra, particularly the theory of semigroups and monoids, many problems in this area can be simplified or completely reduced to combinatorial problems. …
-
State Complexity of Nondeterministic Finite Automata with Limited Nondeterminism
… a function of the tree width and the number of states of A. We introduce a lower bound technique for ftw-NFAs. We study the interrelationships between various measures of nondeterminism for finite automata. We define the trace measure which is a new approach of quantifying nondeterminism. The …
-
The effects of white noise on state complexity and evaluative importance
The effects of cortical arousal on state complexity and evaluative importance were examined. Arousal was manipulated using two levels of white noise. In Study 1, a three-dimensional social domain was created using behavioral descriptions of eight fictitious people. In Study 2, subjects memorized …
-
State Complexity of Linear Relations and Linear Subsequences of Automatic Sequences
In this thesis, we study the state complexity of specific formal languages; for example, we study the number of states required in the minimal automaton reading the representation of two integers $i, j$ in parallel and accepting them if and only $i+c = j$ for some constant integer $c \geq 1$. We …
-
Monoids and the State Complexity of the Operation root(<i>L</i>)
In this thesis, we cover the general topic of state complexity. In particular, we examine the bounds on the state complexity of some different representations of regular languages. As well, we consider the state complexity of the operation root(<i>L</i>). We give quick treatment of the …
-
Distances Between Languages: Algorithms and Descriptional Complexity
We consider the descriptional complexity of neighbourhoods of regular languages and the computational complexity of computing the distance between languages. Distance measures are defined on words to describe their similarity. These measures can be extended to languages, which are sets of words. We …
-
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 …
-
Syntactic Complexities of Nine Subclasses of Regular Languages
The syntactic complexity of a regular language is the cardinality of its syntactic semigroup. The syntactic complexity of a subclass of the class of regular languages is the maximal syntactic complexity of languages in that class, taken as a function of the state complexity n of these languages. We …
-
Closure, Decidability, and Complexity Results for Restricted Variants of Two-Dimensional Automata
… that can be answered by an algorithm), and complexity properties (computational resources needed to decide problems or recognize languages). We first consider decision problems for restricted variants of two-dimensional automata, establishing time complexity bounds on the emptiness problem. …
-
DESCRIPTIONAL COMPLEXITY AND PARIKH EQUIVALENCE
… languages and the study of their descriptional complexity. The descriptional complexity of a formal structure (e.g., grammar, model of automata, etc) is the number of symbols needed to write down its description. While this aspect is extensively treated in regular languages, as evidenced by …
-
Problems Related to Shortest Strings in Formal Languages
… a regular language provides a lower bound on the state complexity of the language. In Chapter 1, we introduce some relevant concepts and notation used in automata and language theory, and we show some basic results concerning the connection between the length of the shortest string and the …
-
Circuit Complexity of Mixed States
… increasing attention, is quantum circuit complexity. As a natural generalization for the complexity of pure states, we investigate the circuit complexity of mixed states in this thesis. First of all, we explore the so-called purification complexity which is defined as the lowest value of the …
-
Positional Numeration Systems: Ultimate Periodicity, Complexity and Automatic Sequences
… of three distinct parts, connected especially by complexity notion, factorial complexity as well as state complexity. We study positional numeration systems and recognizable sets through decision problems and automatic sequences. The first part is devoted to the following problem: given a …
-
Limited Existential and Universal Width Alternating Finite Automata
… alternation between existential and universal states, is fairly new in the literature. Drawing inspiration from limited NFAs, recent studies have introduced maximal and optimal existential and universal widths of AFAs, designed to quantify the amount of existential and universal power used by …
-
K-complexity and the Jordan-Wigner transformation
Krylov complexity is a measure of operator growth that demonstrates universal properties and bounds a large class of complexities. One such measure from this bounded class is operator size. The relationship between operator size and operator growth has been conjectured to be non-trivial due to the …
-
Fatigue Resistance of Asphalt Mixtures Affected by Water Vapor Movement
… growth. The RDT test greatly reduced the stress state complexity within the specimens by evenly distributing stress over the cross section area of the cylindrical specimen. Compared to the previous torsional test, the newly proposed test protocol was more efficient in characterizing the moisture …
-
Neurometric Profiling of Autism Spectrum Disorder using The Brief Neurometric Battery: A Novel Eeg Based Task
… such as event-related potentials (ERPs), resting state oscillatory activity (OA), and resting state complexity (multiscale entropy), are well-suited for the measurement of such biomarkers. Due to the complexity and heterogeneity of ASD symptoms, it is important that research aiming to use EEG to …
Page 1 of 2