|
|
Scalable link-time optimization
Láska, Ladislav ; Hubička, Jan (advisor) ; Mareš, Martin (referee)
Both major open-source compilers, GCC and LLVM, have a mature link-time optimization framework usable on most current programs. They are however not free from many performance issues, which prevent them to perform certain analyses and optimizations. We analyze bottlenecks and identify multiple places for improvement, focusing on improving interprocedural points-to analysis. For this purpose, we design a new data structure derived from Bloom filters and use it to significantly improve performance and memory consumption of link-time optimization. Powered by TCPDF (www.tcpdf.org)
|
|
| |
|
|
Combinatorial Properties of Finite Models
Hubička, Jan ; Nešetřil, Jaroslav (advisor) ; Pultr, Aleš (referee) ; Cameron, P. (referee)
We study countable embedding-universal and homomorphism-universal structures and unify results related to both of these notions. We show that many universal and ultrahomogeneous structures allow a concise description (called here a finite presentation). Extending classical work of Rado (for the random graph), we find a finite presentation for each of the following classes: homogeneous undirected graphs, homogeneous tournaments and homogeneous partially ordered sets. We also give a finite presentation of the rational Urysohn metric space and some homogeneous directed graphs. We survey well known structures that are finitely presented. We focus on structures endowed with natural partial orders and prove their universality. These partial orders include partial orders on sets of words, partial orders formed by geometric objects, grammars, polynomials and homomorphism orders for various combinatorial objects. We give a new combinatorial proof of the existence of embedding-universal objects for homomorphism-defined classes of structures. This relates countable embedding-universal structures to homomorphism dualities (finite homomorphism-universal structures) and Urysohn metric spaces. Our explicit construction also allows us to show several properties of these structures.
|
|
|
Modular tool for parametric analysis of dynamical systems using complex networks
Hons, Tomáš ; Hartman, David (advisor) ; Hubička, Jan (referee)
Modelling of dynamical systems with complex internal structure is a complicated task which has more and more frequently been solved using complex networks capturing the structure of interactions among individual elements of the system. An important task of this process is the selection of suitable methods and their parameters by which we create the network and subsequently examine it. However, there is no tool that could automat- ically configure various parametrized analytical pipelines, enable executing all potential runs and compare their results. Such a tool would consequently allow selection of meth- ods and parameters most suitable for the system explored. This work presents the Neads library which is able to execute parametric analyses of general dynamical systems using complex networks, intermediate results being stored and available for subsequent calcula- tions as well as potential pipelines extensions. The tool has the potential to significantly accelerate scientific work in this area. 1
|
|
|
Semigroup-valued metric spaces
Konečný, Matěj ; Hubička, Jan (advisor)
The structural Ramsey theory is a field on the boundary of combinatorics and model theory with deep connections to topological dynamics. Most of the known Ramsey classes in finite binary symmetric relational language can be shown to be Ramsey by utilizing a variant of the shortest path completion (e.g. Sauer's S-metric spaces, Conant's generalised metric spaces, Braunfeld's Λ-ultrametric spaces or Cherlin's metrically homogeneous graphs). In this thesis we explore the limits of the shortest path completion. We offer a unifying framework - semigroup-valued metric spaces - for all the aforementioned Ramsey classes and study their Ramsey expansions and EPPA (the extension property for partial automorphisms). Our results can be seen as evidence for the importance of studying the completion problem for amalgamation classes and have some further applications (such as the stationary independence relation). As a corollary of our general theorems, we reprove results of Hubička and Nešetřil on Sauer's S-metric spaces, results of Hubička, Nešetřil and the author on Conant's generalised metric spaces, Braunfeld's results on Λ-ultrametric spaces and the results of Aranda et al. on Cherlin's primitive 3-constrained metrically homogeneous graphs. We also solve several open problems such as EPPA for Λ-ultrametric...
|
|
|
Semigroup-valued metric spaces
Konečný, Matěj ; Hubička, Jan (advisor)
The structural Ramsey theory is a field on the boundary of combinatorics and model theory with deep connections to topological dynamics. Most of the known Ramsey classes in finite binary symmetric relational language can be shown to be Ramsey by utilizing a variant of the shortest path completion (e.g. Sauer's S-metric spaces, Conant's generalised metric spaces, Braunfeld's Λ-ultrametric spaces or Cherlin's metrically homogeneous graphs). In this thesis we explore the limits of the shortest path completion. We offer a unifying framework - semigroup-valued metric spaces - for all the aforementioned Ramsey classes and study their Ramsey expansions and EPPA (the extension property for partial automorphisms). Our results can be seen as evidence for the importance of studying the completion problem for amalgamation classes and have some further applications (such as the stationary independence relation). As a corollary of our general theorems, we reprove results of Hubička and Nešetřil on Sauer's S-metric spaces, results of Hubička, Nešetřil and the author on Conant's generalised metric spaces, Braunfeld's results on Λ-ultrametric spaces and the results of Aranda et al. on Cherlin's primitive 3-constrained metrically homogeneous graphs. We also solve several open problems such as EPPA for Λ-ultrametric...
|
|
|
API for C# code generation
Lukeš, Stanislav ; Hubička, Jan (advisor) ; Kliber, Filip (referee)
This work presents a library for implementing robust generators of C# code. Exist- ing code generators often generate invalid code for some inputs. Issues such as name collisions reduce the reliability of code generation. Programmers are then forced to han- dle these cases manually, which breaks build pipelines and lowers productivity. Our library solves these issues. It automatically avoids name collisions, and keeps the gener- ated code clean and human-readable. We compare our approach to other solutions such as reflection-based metaprogramming, macros, intermediate language rewriting and F# Type Providers. 1
|
|
|
Computing and estimating ordered Ramsey numbers
Poljak, Marian ; Balko, Martin (advisor) ; Hubička, Jan (referee)
We study ordered Ramsey numbers, which are an analogue of the classical Ramsey numbers for ordered graphs. We improve some already obtained results for a special class of ordered matchings and disprove a conjecture of Rohatgi. We expand the classical notion of Ramsey goodness to the ordered case and we attempt to characterize all Ram- sey good connected ordered graphs. We outline how Ramsey numbers can be obtained computationally and describe our SAT solver based utility developed to achieve this goal, which might be of use to other researchers studying this topic. 1
|
|
|
Semigroup-valued metric spaces
Konečný, Matěj ; Hubička, Jan (advisor) ; Pultr, Aleš (referee)
The structural Ramsey theory is a field on the boundary of combinatorics and model theory with deep connections to topological dynamics. Most of the known Ramsey classes in finite binary symmetric relational language can be shown to be Ramsey by utilizing a variant of the shortest path completion (e.g. Sauer's S-metric spaces, Conant's generalised metric spaces, Braunfeld's Λ-ultrametric spaces or Cherlin's metrically homogeneous graphs). In this thesis we explore the limits of the shortest path completion. We offer a unifying framework - semigroup-valued metric spaces - for all the aforementioned Ramsey classes and study their Ramsey expansions and EPPA (the extension property for partial automorphisms). Our results can be seen as evidence for the importance of studying the completion problem for amalgamation classes and have some further applications (such as the stationary independence relation). As a corollary of our general theorems, we reprove results of Hubička and Nešetřil on Sauer's S-metric spaces, results of Hubička, Nešetřil and the author on Conant's generalised metric spaces, Braunfeld's results on Λ-ultrametric spaces and the results of Aranda et al. on Cherlin's primitive 3-constrained metrically homogeneous graphs. We also solve several open problems such as EPPA for Λ-ultrametric...
|
|
|
Combinatorial Properties of Metrically Homogeneous Graphs
Konečný, Matěj ; Hubička, Jan (advisor) ; Nešetřil, Jaroslav (referee)
Ramsey theory looks for regularities in large objects. Model theory studies algebraic structures as models of theories. The structural Ramsey theory com- bines these two fields and is concerned with Ramsey-type questions about certain model-theoretic structures. In 2005, Nešetřil initiated a systematic study of the so-called Ramsey classes of finite structures. This thesis is a contribution to the programme; we find Ramsey expansions of the primitive 3-constrained classes from Cherlin's catalogue of metrically homogeneous graphs. A key ingredient is an explicit combinatorial algorithm to fill-in the missing distances in edge-labelled graphs to obtain structures from Cherlin's classes. This algorithm also implies the extension property for partial automorphisms (EPPA), another combinatorial property of classes of finite structures. 1
|
guest ::
