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 41 for “"tree automata"”.
-
State Complexity of Tree Automata
Modern applications of XML use automata operating on unranked trees. A common definition of tree automata operating 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 …
-
Kleene-Type Results for Weighted Tree-Automata
… generalization of the Kleene-theorem to formal tree-series over commutative semirings (the Kleene theorem states the coincidence between rational and recognizable formal languages). To this end weighted tree-languages are introduced and the Kleene-theorem is proved for them. The desired result …
-
Using Tree Automata to Investigate Intuitionistic Propositional Logic
… of intuitionistic propositional formulas as tree automata. This representation permits a number of consequences, including a characterization theorem for free Heyting algebras, which are the intutionistic analogue of free Boolean algebras, and a new algorithm for solving equations over …
-
Weighted Unranked Tree Automata over Tree Valuation Monoids
… of resources, can be modeled by weighted automata. The usual approach is to weight transitions with elements of a semiring and to define the behavior of the weighted automaton by mul- tiplying the transition weights along a run. In this thesis, we define and investigate a new class of …
-
U-tree automata : machines that can classify patterns
Thesis (Ph. D.)--Michigan State University. Department of Computer Science, 1973
-
A Formal View on Training of Weighted Tree Automata by Likelihood-Driven State Splitting and Merging
… the structure of sentences by making use of trees. We use weighted tree automata (wta) in order to deal with such tree structures. Those devices assign weights to trees in order to, for example, distinguish between good and bad structures. The well-known expectation-maximization algorithm can …
-
Characterisation Theorems for Weighted Tree Automaton Models
… theoretical questions concerning weighted automata models over tree-like input structures. First, we study exact and approximated determinisation and then, we turn to Kleene-like and Büchi-like characterisations. We consider multiple weighted automata models, including weighted tree …
-
Application of three languages to pattern recognition
… is to develop new techniques in the theory of tree languages for applications in syntactic pattern recognition. The resulting procedures are presented as algorithms which are easy to implement in the form of computer programs.</p><p>The main areas covered are grammatical inference, minimization …
-
Decision Procedures for Equationally Based Reasoning
… been used in external projects including our tree automata library's integration into the ACTAS protocol verification tool [126], and the order-sorted unification procedures use in the Maude-NRL protocol analyzer [49].
-
Weighted Automata with Storage
In this thesis, we investigate weighted tree automata with storage theoretically. This model generalises finite state automata in three dimensions: (i) from words to trees, (ii) by using an arbitrary storage type in addition to a finite-state control, and (iii) by considering languages in a …
-
Expressiveness and Decidability of Weighted Automata and Weighted Logics
Automata theory, one of the main branches of theoretical computer science, established its roots in the middle of the 20th century. One of its most fundamental concepts is that of a finite automaton, a basic yet powerful model of computation. In essence, finite automata provide a method to finitely …
-
Weighing in on the HOM-Problem
… is inconceivable without the concept of finite automata. These devices and their upgraded versions, weighted automata, are widely used to implement (quantitative) evaluations of inputs in image compression, probabilistic systems or natural language processing. In particular, the handling of …
-
Learning via automaton minimization and matrix factorization
… studies minimization and learning of weighted automata with weights in a field, focusing on tree automata as representations of distributions over trees. We give a minimization algorithm that runs in polynomial time assuming unit-cost arithmetic, and show that a polynomial bound in the Turing …
-
Algebraic decoder specification: coupling formal-language theory and statistical machine translation
… stimulation between the theory of weighted tree automata and the application.
-
Multioperator Weighted Monadic Datalog
… datalog (mwmd), a formal model for specifying tree series, tree transformations, and tree languages. This model combines aspects of multioperator weighted tree automata (wmta), weighted monadic datalog (wmd), and monadic datalog tree transducers (mdtt). In order to develop a rich theory we will …
-
Finitely Constrained Groups
… of finitely constrained groups of p-adic tree automorphisms. The set of possible values of Hausdorff dimension for such a group is known, and we are able to show that every value in this set actually occurs. The second topic, related to the first, is topological finite generation of …
-
Verification of sequential and concurrent libraries
… data values of nodes in linked lists, binary trees, and directed acyclic graphs; methods to reverse linked lists; and methods to rotate balanced trees. Well-written methods are accompanied by documentation that specifies the observational behavior of these methods in terms of …
-
Automata and game theoretic models of computation
… 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 automata (DFA) state …
-
Probabilistic Logic, Probabilistic Regular Expressions, and Constraint Temporal Logic
… state the expressive equivalence of finite automata to monadic second order logic and regular expressions, respectively. These fundamental results enjoy applications in nearly every field of theoretical computer science. Around the same time as Büchi and Kleene, Rabin investigated …
Page 1 of 3