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"”.
-
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, …
-
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 …
-
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 …
-
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 …
-
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, …
-
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.
-
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 …
-
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 …
-
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 …
-
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 …
-
Assessing Core Stable Coalitions Based On Social Network Structures
… as a regular expression which can be read by a finite automaton.
-
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 …
-
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 …
-
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 …
-
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 …
-
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}.
-
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 …
-
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. …
-
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 …
Page 1 of 4