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 6 of 6 for “"nested words"”.
-
The (Nested) Word Problem: Formal Languages, Group Theory, and Languages of Nested Words
… results concerning applications of languages of nested words for studying the word problem.</p>
-
Weighted Automata and Logics on Hierarchical Structures and Graphs
… over graphs. In particular, we study infinite nested words, operator precedence languages, and finite and infinite graphs. We show Büchi-like results connecting weighted automata and weighted monadic second order (MSO) logic for the respective classes of weighted languages over these …
-
Expressiveness and Decidability of Weighted Automata and Weighted Logics
… to describe not only languages of strings, or words, but also of infinite words by Büchi and Muller, finite trees by Doner and Thatcher and Wright, infinite trees by Rabin, nested words by Alur and Madhusudan, and pictures by Blum and Hewitt, just to name a few examples. In a parallel line of …
-
On collapsible pushdown automata, their graphs and the power of links
… (HOPDA) are abstract machines equipped with a nested stacks of stacks... of stacks of stacks. Collapsible pushdown automata (CPDA) enhance these stacks with the addition of ‘links’ emanating from atomic elements to the higher-order stacks below. For trees CPDA are equi-expressive with recursion …
-
Weighted Logics and Weighted Simple Automata for Context-Free Languages of Infinite Words
… and finite automata for both finite and infinite words. This BET- Theorem has been extended by Lautemann, Schwentick and Thérien to context-free languages by introducing a monadic second-order logic with an additional existentially quantified second-order variable. This new variable models the …
-
Traces, interpolants, and automata : a new approach to automatic software verification
… a Floyd-Hoare automaton.<br>We use the theory of nested words to present a new kind of correctness proof for an interprocedural trace. We call such a proof a sequence of nested interpolants. The combination of nested word automata and nested interpolants allow us to apply our new software …