Papers by Jan Hubicka

This page lists all papers and related texts I've worked on so far. I did work on two main areas For the compiler papers I include the HTML version produced by latex2html. These versions should be used for orientation only as they contain some inexact translations of the original LaTeX document.

Graph homomorpshims and homogeneous structures

Finite Paths are Universal (With Jaroslav Nesetril), 2003
We prove that any countable (finite or infinite) partially ordered set may be represented by finite oriented paths ordered by the existence of homomorphism between them. This (what we believe a surprising result) solves several open problems. Such path-representations were previously known only for finite and infinite posets of dimension 2. Path-representation implies the universality of other classes of graphs (such as connected cubic planar graphs). It also implies that finite partially ordered sets are on-line representable by paths and their homomorphisms. This leads to a new on-line dimensions.

Compressed PostScript, PDF

Universal Partial Order Represented by Means of Trees and Other Simple Graphs (With Jaroslav Nesetril), 2003
We present several simple representations of universal partially ordered sets and use them for the proof of universality of the class of oriented trees ordered by the graph homomorphisms. This (what we believe surprising result) solves several open problems. It implies for example universality of cubic planar graphs. This is in sharp contrast with representing even groups (and monoids) by automorphisms (and endomorphims) of a bounded degree and planar graph. Thus universal partial orders (thin categories) are representable by much simpler structures than categories in general.

Compressed PostScript, PDF

On Homogeneous Graphs and Posets (With Jaroslav Nesetril), 2003
We present a class Pu of simple finite structures which induce the countable homogeneous universal poset. We also define the notion of a finitely presented countable structure and conjecture that every generic structure for a finitely axiomatizable class of structures is finitely presented. This is verified for undirected graphs, tournaments and posets. The structure Pu extends Conway's surreal numbers and their linear ordering to posets.

Compressed PostScript, PDF

Ramsey Properties of Universal Sets (diploma thesis in Czech language), 2002
In this thesis we describe correspondence between the Ramsey properties and the subjects of universality and homogenity of the relational structures. Later we show description of new homogene and universal partially ordered set and its relation to Conway's surreal numbers. We use this structure for description of universal oriented acyclic graph and for new proof of universality of multicuts. We show new structure, truncated vectors TV, as dual structure to multicuts. We found this structure as useful step to close problem of universality of the class of oriented paths ordered by graph homomorphisms. We show this new proof and use it to prove universality of class of undirected planar graphs of limited degree ordered by homomorphisms.

Keywords: Graphs, homomorphisms, universality, homogenity, extension properties

Compressed PostScript, PDF

Compilers

Porting GCC to the AMD64 architecture, 2003
In this paper we describe our experience from porting GCC to the x86-64 architecture and the AMD Opteron processor. Our target was a high quality port producing fast code. We discuss decisions taken while designing the Application Binary Interface (ABI) and effect of various code optimizations we implemented. We also present several open issues we would like to solve in the future.

Compressed PostScript, PDF (with hyperlinks and times), PDF, HTML, PDF presentation slides

UNIX System V Application Binary Interface; AMD64 Architecture Processor Supplement(co-edited by Andreas Jaeger and Mark Mitchell), draft
Specify function call conventions, stack unwinding, code models, linking and more

PDF, HTML (version 0.90, possibly out of date)

Infrastructure for Profiled Driven Optimizations in GCC(With Zdenek Dvorak, Pavel Nejedly and Josef Zlomek), 2002
Documentation for the school project held on Charles University under lead of David Bednarek.

Compressed PostScript, PDF, HTML, PDF of presentation slides (in Czech)