Seminars

you must be logged-in to have full access to seminar attachments

Extensional acyclic digraphs and set graphs

Date: 
18 November, 2011 - 14:30 - 15:00
Location: 
Aula Multimediale
Description
Abstract: 

A digraph is called ‘extensional’ if its vertices have pairwise distinct out-neighborhoods. Extensional acyclic digraphs originate from set theory where they represent transitive closures of hereditarily finite sets.

We will present some results concerning the underlying graphs of extensional acyclic digraphs, which we call ‘set graphs’. Even though we argue that recognizing set graphs is NP-complete, we show that set graphs contain all connected claw-free graphs and all graphs with a Hamiltonian path. In the case of claw-free graphs, we provide a polynomial-time algorithm for finding an extensional acyclic orientation.

Extensional digraphs can also be characterized in terms of a slight variation of the notion of separating code for digraphs, which we call open-out-separating code. Concerning this, deciding if a digraph admits an open-out-separating code of given size is NP-complete.

This is joint work with Martin Milanic and Romeo Rizzi.

Annual Reports of the PhD Students

Date: 
5 October, 2011 - 10:00 - 12:00
Description
Abstract: 

First-year students will hold a 5-10 minute presentation about their research so far, schools and courses attended, as well as future educational plans. Second-year students will hold a 30-minute presentation (plus 5-10 minutes for questions) on their thesis proposal.

Date: 5th October 2011

Local Normal Forms for First-Order Logic with Applications to Games and Automata

Date: 
13 July, 2011 - 11:30 - 12:30
Location: 
Sala riunioni
Description
Abstract: 

Work of T. Schwentick and K. Barthelmann is presented.
Authors show that every first-order formula is logically equivalent to a normal form characterized by a subformula that is r-local around y, i. e. quantification is restricted to elements of the universe of distance at most r from y.
From this and related normal forms, variants of the Ehrenfeucht game for first-order and existential
monadic second-order logic are developed that restrict the possible strategies for the spoiler, one of the
two players. This makes proofs of the existence of a winning strategy for the duplicator, the other player,
easier and can thus simplify inexpressibility proofs.
As another application, automata models are defined that have, on arbitrary classes of relational structures, exactly the expressive power of first-order logic and existential monadic second-order logic, respectively.

Extensional acyclic orientations and set graphs

Date: 
17 June, 2011 - 12:30 - 12:50
Location: 
Aula Multimediale
Description
Abstract: 

A graph is said to be a `set graph' if it is the underlying graph of the transitive closure of a hereditarily finite set; equivalently, if it admits an acyclic orientation in which all out-neighborhoods of its vertices are distinct.

The study of set graphs was initiated only recently. Even though we argue that recognizing set graphs is NP-complete, we identify, on the one hand, several necessary conditions that every set graph must satisfy. On the other hand, we show that set graphs form a rich class of graphs containing all connected claw-free graphs and all graphs with a Hamiltonian path. In the case of claw-free graphs, we provide a polynomial-time algorithm for finding an extensional acyclic orientation. We also characterize the largest hereditary class in which being connected and claw-free is equivalent to being a set graph.

Syndicate content