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 63 for “"finite automaton"”.

  1. New metrics for finite automaton complexity and subregular language hierarchies

    The degree of ambiguity of nondeterministic finite automata (NFA) has been studied significantly since at least the 1980s. Roughly speaking, the degree of ambiguity counts the number of accepting computations of an NFA. To get a more comprehensive understanding of the branching complexity of NFAs, …

    queens Repository record for New metrics for finite automaton complexity and subregular language hierarchies (opens in a new tab)

  2. Groups generated by bounded automata and their schreier graphs

    … introduce the notion of a post-critical set of a finite automaton and prove that the limit space of a contracting self-similar group generated by a finite automaton is post-critically finite (finitely-ramified) if and only if the automaton is bounded. We show that the Schreier graphs on levels of …

    tamu Repository record for Groups generated by bounded automata and their schreier graphs (opens in a new tab)

  3. Finite-state quantum computational complexity

    The automatic complexity of finite words was introduced by Shallit and Wang (2001) as a computable and visual analogue to Kolmogorov complexity. It measures the complexity of a word $x$ as the minimum number of states of a finite automaton that uniquely accepts $x$. Here, an automaton $M$ uniquely …

    hawaii Repository record for Finite-state quantum computational complexity (opens in a new tab)

  4. Presburger Arithmetic: From Automata to Formulas

    … including formulas, generators, and finiteautomata, the latter being the focus of this thesis. Finite-automata representations of Presburger sets work by encoding numbers as words and sets by automata-defined languages. With this representation, set operations are easily computableas …

    liege Repository record for Presburger Arithmetic: From Automata to Formulas (opens in a new tab) Download PDF for Presburger Arithmetic: From Automata to Formulas (opens in a new tab)

  5. Representing processes as Update Automata and Transducers

    In 2007 Nerode introduced the notion of an update automaton and update transducer to model the evolution of interactions of arbitrary functions on arbitrary domains governed by a finite automaton. We show the scope of this methodology by modeling a variety of processes, including database networks, …

    cornell Repository record for Representing processes as Update Automata and Transducers (opens in a new tab)

  6. Conformance Testing and Error Explanation for Software Models

    … of determining the smallest deterministic finite automaton that is consistent with a given sample of positively and negatively labeled inputs. We also prove that error explanation based on the second heuristic is tractable for several models that capture program behavior.

    uiuc Repository record for Conformance Testing and Error Explanation for Software Models (opens in a new tab)

  7. Finite Automata Algorithms in Map-Reduce

    … intersection of several large nondeterministic finite automata (NFA's) as well as minimization of a large deterministic finite automaton (DFA) in map-reduce are studied. We have derived a lower bound on replication rate for computing NFA intersections and provided three concrete algorithms for …

    concordia Download PDF for Finite Automata Algorithms in Map-Reduce (opens in a new tab)

  8. Implementing supervisory control maps with PLC

    … transforms a supervisor represented by a finite automaton to a Ladder Logic Diagram (LLD). To demonstrate the correctness of our proposed approach and discuss the issues that may arise in modeling and development of DES supervisors, we design supervisors for a boiler control system using …

    concordia Download PDF for Implementing supervisory control maps with PLC (opens in a new tab)

  9. Finite Automata Models: Algorithm, Application, and Semigroup Study

    A finite automaton consists of states and state transitions labeled by letters of a finite alphabet. Every letter describes a transformation of the automaton's state space, generating a corresponding transformation semigroup. A stochastic version of automata has a probability distribution over the …

    waterloo Repository record for Finite Automata Models: Algorithm, Application, and Semigroup Study (opens in a new tab)

  10. High performance stride-based network payload inspection

    … set is usually organized as a Deterministic Finite Automata (DFA). The processing time of DFA is proportional to the length of the input string, but the memory cost of a DFA is quite large. Meanwhile, the link bandwidth and the traffic of the Internet are rapidly increasing, the size of the …

    dcu Download PDF for High performance stride-based network payload inspection (opens in a new tab)

  11. Assessing Core Stable Coalitions Based On Social Network Structures

    … as a regular expression which can be read by a finite automaton.

    auckland-tech Repository record for Assessing Core Stable Coalitions Based On Social Network Structures (opens in a new tab)

  12. eMicro: Real-Time Multi-Hop Access Control for Microservices with eBPF

    … policies encoded as efficient deterministic finite automaton (DFA), supporting constant-time lookups and compact label propagation; (3) eBPF-based in-kernel request tracing for transparent, low-overhead enforcement without code changes. Evaluations on DeathStarBench and production cloud …

    vt Repository record for eMicro: Real-Time Multi-Hop Access Control for Microservices with eBPF (opens in a new tab)

  13. Automata-Theoretic Models for Computational Complementarity

    … point of view, a new type of questions about finite automata, questions motivated by looking at automata as toy models of physical particles. Working along the line of research initiated by Moore, two computational complementarity principles are studied, (for finite-deterministic, complete or …

    auckland-ms Repository record for Automata-Theoretic Models for Computational Complementarity (opens in a new tab)

  14. On the Finite Axiomatizability of Equational Theories of Automatic Algebras

    … that hold in an algebra is axiomatizable by a finite set of equations, for which we call the algebra finitely based. If not, we can further ask if the algebra satisfies a stronger condition we call inherently nonfinitely based. For instance all finite groups and rings were shown in 1964 and …

    south-carolina Repository record for On the Finite Axiomatizability of Equational Theories of Automatic Algebras (opens in a new tab)

  15. Verification and Enforcement of State-Based Notions of Opacity in Discrete Event Systems

    … that are modeled as (possibly non-deterministic) finite automata with partial observation on their transitions. Assuming that the intruder observes system activity through some projection map and has complete knowledge of the system model, we define three notions of opacity with respect to a set …

    uiuc Repository record for Verification and Enforcement of State-Based Notions of Opacity in Discrete Event Systems (opens in a new tab)

  16. Problems Related to Shortest Strings in Formal Languages

    … squarefree string accepted by a deterministic finite automaton, and finding an efficient way to check if a finite set of finite words generates the free monoid. Some of the results in this thesis have appeared in work that the author has participated in \cite{AngPigRamSha,AngShallit}.

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

  17. Nondeterministic State Complexity of Site-Directed Operations

    … and deletion. Constructing a nondeterministic finite automaton (NFA) for the operation provides an upper bound for the state complexity of the operation. Our construction improves the earlier upper bound in the literature. Existing literature did not give lower bounds for the nondeterministic …

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

  18. Recognizable Languages Defined by Two-dimensional Shift Spaces

    … as varied examples. We next define a new type of finite automaton and with it, a tool for recognizing two-dimensional "strings" of data. It is then shown that these automata correctly represent the sofic shift spaces that result from the application of block maps to shifts of finite type. …

    usf Repository record for Recognizable Languages Defined by Two-dimensional Shift Spaces (opens in a new tab)

  19. Forbidden-Patterns and Word Extensions for Concatenation Hierarchies

    … these levels in terms of patterns in finite automata (subgraphs in the transition graph) that are not allowed. Therefore, such characterizations are called forbidden-pattern characterizations. The main results of the thesis are as follows: forbidden-pattern characterization for level …

    wurz-thes Repository record for Forbidden-Patterns and Word Extensions for Concatenation Hierarchies (opens in a new tab)

Page 1 of 4