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 14 of 14 for “"Regular Languages"”.
-
Tolerant Testing of Regular Languages in Sublinear Time
… is to test whether a binary input word 𝑤 is in regular language 𝐿. Such testers distinguish the case that 𝑤 is in 𝐿 from the case where 𝑤 is 𝜖-far from 𝐿 (𝜖-far means that at least 𝜖 fraction of the bits in 𝑤 must be modified to change 𝑤 into a word in 𝐿. Otherwise, 𝑤 is 𝜖-close). When it is …
-
Foundations of Regular Languages for Processing RDF and XML
Die vorliegende Arbeit befasst sich mit der Komplexität und Optimierung von Problemen, die bei der Verwendung von regulären Sprachen für die web-basierte Datenverarbeitung entstehen. Die betrachteten Problemstellungen sind insbesondere durch Anwendungen motiviert die eines der folgenden zwei …
-
Predicate Classes, Promise Classes, and the Acceptance Power of Regular Languages
Die Dissertation untersucht eine uniforme Methode, Komplexitaetsklassen zu definieren.
-
The Forbidden Pattern Approach to Concatenation Hierarchies
… the computability of the dot-depth of star-free regular languages. Here one has to determine for a given star-free regular language the minimal number of alternations between concatenation on one hand, and intersection, union, complement on the other hand. This question was first raised in 1971 …
-
Expressiveness and Decidability of Weighted Automata and Weighted Logics
… of strings is also called a language, and the languages which can be described by finite automata are known as regular languages. Owing to their versatility, regular languages have received a great deal of attention over the years. Other formalisms were shown to be expressively equivalent to …
-
On the power of nondeterminism in small two-way finite automata
… can recognize B, for B a particular sequence of regular languages that is among the hardest of those recognizable by polynomial-size sequences of 1NFAs. We prove that the most natural single-pass 2DFA algorithm for deciding B fails, "single-pass" meaning that the automaton is bound to terminate …
-
Human and artificial intelligence acquisition of quantifiers
… place strong constraints on possible languages to identify an unknown language in a certain given class of languages. The experiment presented in this paper measures the cognitive ability of humans to acquire quantifiers, both conservative and non-conservative, through a series of …
-
The transformational implementation of JSD process specifications via finite automata representation
… Jackson structure diagrams are equivalent to regular expressions and can be thought of as specifying corresponding finite automata. The thesis discusses the automatic transformation of structure diagrams into finite automata using an algorithm adapted from compiler theory, and then extends the …
-
COMPOSITIONAL GENERALIZATION IN INSTRUCTION FOLLOWING TASKS
… complexity: semantic parsing in synthetic languages, natural language instruction following in blocks world and vision-and-language navigation in complex indoor environments. We demonstrate empirically that existing systems for these tasks, while performant on the standard iid test set …
-
Forbidden-Patterns and Word Extensions for Concatenation Hierarchies
Starfree regular languages can be build up from alphabet letters by using only Boolean operations and concatenation. The complexity of these languages can be measured with the so-called dot-depth. This measure leads to concatenation hierarchies like the dot-depth hierarchy (DDH) and the closely …
-
Development of a Supervisory Control System as a Transition Technology Towards Autonomous Reactor Plant Operations
… set of mathematical proofs within the scope of regular languages. Furthermore, a DES can be directly linked to reactor plant systems and operational procedures within a hierarchical architecture by using a graded functionalization approach analogous to that of complex dynamic systems, such as …
-
Reconstructing Signaling Pathways Using Regular-Language Constrained Paths
… The key idea underlying RegLinker is the use of regular-language constraints to control the number of non-pathway edges present in the computed paths. We systematically evaluate RegLinker and alternative approaches against a comprehensive set of 15 signaling pathways and demonstrate that …
-
QUANTUM AND TRANSLUCENT PARADIGMS IN AUTOMATA THEORY: A STUDY ON COMPUTATIONAL CAPABILITIES
… recognition. Frameworks for recognising unary languages by Latvian QFAs (LQFAs) and QFAs with Control Language (QFCs) are developed. Moreover, decidability questions related to periodicity in measure-once QFAs, measure-many QFAs, LQFAs, and QFCs are analyzed. For DPDAwtl’s - which extend …
-
Substructurality and residuation in logic and algebra
… like for example Dedekind-McNeil completions, regular completions, complete ideal completions, . . . Very often it happens that for a certain algebra in a variety of residuated lattices, those completions exists but do not belong to the same variety. That is, varieties are not closed, in …