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 15 of 15 for “"Infinite Graphs"”.
-
Infinite graphs generated by tree rewriting
Finite graphs and algorithms on finite graphs are an important tool for the verification of finite-state systems. To transfer the methods for finite systems, at least partially, to infinite systems a theory of infinite graphs with finite representations is needed. In this thesis the class of the …
-
Decision problems over infinite graphs : higher order pushdown systems and synchronized products
The extension of formal verification methods to infinite models requires classes of graphs which are finitely representable and for which the model checking problem is decidable. We consider three approaches to define classes of finitely representable graphs: internal representations as …
-
Games on pushdown graphs and extensions
… the winner and a winning strategy. For finite graphs these problems have been solved for a long time, although some complexity questions remain open. We consider several classes of infinite graphs, from transition graphs of pushdown automata up to graphs of the Caucal hierarchy, and we …
-
On stochastic completeness of weighted graphs
… time behavior of continuous time random walks on infinite graphs. The following three related problems are considered. 1. Stochastic completeness of the random walk. We characterize the stochastic completeness of the random walk in terms of function-theoretic and geometric properties of the …
-
Provably Asymptotically Near-Optimal Motion Planning with Sparse Data Structures
… near-optimal solutions produce sparser graphs by notincluding all edges. The idea stems from graph spanner algorithms,which produce sparse subgraphs that guarantee near-optimal paths.Existing asymptotically optimal and near-optimal planners, however,include all sampled configurations as …
-
Unavoidable minors in graphs and matroids
… this result to 3- and internally 4-connected graphs identifying all unavoidable series minors of these classes. Loosely speaking, a series minor allows for arbitrary edge deletions but only allows edges to be contracted when they meet a degree-2 vertex. Dually, a parallel minor allows for any …
-
Characterizations and Probabilistic Representations of Effective Resistance Metrics
… studies effective resistances of finite and infinite weighted graphs. Classical results state that it is a metric on the set of vertices of the graph and that it can be expressed completely in terms of the graph’s random walk. The first goal of this thesis is to provide a concise and …
-
Width functions for hypertree decompositions
… directly for structures, or at least for hypergraphs. This was done by Gottlob, Leone and Scarcello, who defined hypertree-width of hypergraphs. <br> <br>Tree-width is defined in terms of the cardinalities of the pieces of tree-decompositions. Hypertree-width can be understood as a variant of …
-
Studies in Statistical Mechanics and Supersymmetric Lattice Models
… two distinct but related models on regular tree graphs: the vertex-reinforced jump process (VRJP), a random walk that prefers to jump to previously visited sites, and the $\mathbb{H}^{2|2}$-model, a lattice spin system whose spins take values in a supersymmetric extension of the hyperbolic plane. …
-
Reachability over word rewriting systems
… been investigated as a mechanism to represent infinite graphs by a finite formalism. This thesis has its main focus in the latter domain. In the first part of the thesis, we investigate mixed prefix/suffix rewriting (MPSR) systems, which combine prefix and suffix rewriting in a nondeterministic …
-
Group-invariant random processes
… point process on Rd and examine what types of graphs can be defined on the points of the process in such a way that the point process and the graph have an equivariant distribution. We show that 1-ended trees and Zn can be achieved for invariant point processes in Rd that satisfy some …
-
Perpetual exploration of relational information and enhanced star glyphs for multi-source data visualization
… visualization to the display of directed graphs and to the display of multivariate data for analysis. Two novel applications will be presented that are both advancements in the field of information visualization. The first application applies to the visualization and navigation of large or …
-
Properties of p-modulus on radially symmetric infinite trees
… have meaningful and interesting extensions to infinite graphs. For example, certain effective resistance calculations on infinite trees are known to be related to the transience or recurrence of random walks on these trees. The goal of this dissertation is to extend the theory of p-modulus to …
-
Poset saturation and other combinatorial results
… we say that a factorisation x = u1u2 · · · of an infinite word x is ‘super-monochromatic’ if each word uk1 uk2 · · · ukn, where k1 < · · · < kn, is the same colour. We show that a word x is eventually periodic if and only if for every finite colouring of X∗ there is a suffix of x having a …
-
Grafos periódicos: Una familia de grafos infinitos que admiten una algorítmica constructiva
… en M. Bauderon, “On System of Equations Defining Infinite Graphs”. C.N.R.S. prc. Mathematiques et Informatique); en teoría de probabilidades; los Diagramas de Cayley son ejemplos de grafos infinitos contenidos en esta familia, etc. Los algoritmos básicos que se emplean en la resolución de multitud …