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"”.

  1. 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 …

    queens Repository record for State Complexity of Tree Automata (opens in a new tab)

  2. 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 …

    queens Repository record for Nondeterministic State Complexity of Site-Directed Operations (opens in a new tab)

  3. 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. …

    waterloo Repository record for Algebraic Approaches to State Complexity of Regular Operations (opens in a new tab)

  4. 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 …

    queens Repository record for State Complexity of Nondeterministic Finite Automata with Limited Nondeterminism (opens in a new tab)

  5. 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 …

    ubc Repository record for The effects of white noise on state complexity and evaluative importance (opens in a new tab) Download PDF for The effects of white noise on state complexity and evaluative importance (opens in a new tab)

  6. 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 …

    waterloo Repository record for State Complexity of Linear Relations and Linear Subsequences of Automatic Sequences (opens in a new tab)

  7. 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 …

    waterloo Repository record for Monoids and the State Complexity of the Operation root(<i>L</i>) (opens in a new tab)

  8. 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 …

    queens Repository record for Distances Between Languages: Algorithms and Descriptional Complexity (opens in a new tab)

  9. 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 …

    auckland-ms Repository record for Automata and game theoretic models of computation (opens in a new tab)

  10. 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 …

    waterloo Repository record for Syntactic Complexities of Nine Subclasses of Regular Languages (opens in a new tab)

  11. 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. …

    queens Repository record for Closure, Decidability, and Complexity Results for Restricted Variants of Two-Dimensional Automata (opens in a new tab)

  12. 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 …

    milano Repository record for DESCRIPTIONAL COMPLEXITY AND PARIKH EQUIVALENCE (opens in a new tab)

  13. 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 …

    waterloo Repository record for Problems Related to Shortest Strings in Formal Languages (opens in a new tab)

  14. 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 …

    waterloo Repository record for Circuit Complexity of Mixed States (opens in a new tab)

  15. 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 …

    liege Repository record for Positional Numeration Systems: Ultimate Periodicity, Complexity and Automatic Sequences (opens in a new tab) Download PDF for Positional Numeration Systems: Ultimate Periodicity, Complexity and Automatic Sequences (opens in a new tab)

  16. 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 …

    queens Repository record for Limited Existential and Universal Width Alternating Finite Automata (opens in a new tab)

  17. 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 …

    cape-town Repository record for K-complexity and the Jordan-Wigner transformation (opens in a new tab)

  18. 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 …

    tamu Repository record for Fatigue Resistance of Asphalt Mixtures Affected by Water Vapor Movement (opens in a new tab)

  19. 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 …

    wm-mary Repository record for Neurometric Profiling of Autism Spectrum Disorder using The Brief Neurometric Battery: A Novel Eeg Based Task (opens in a new tab)

Page 1 of 2