Evaluating Restricted First-Order Counting Properties on Nowhere Dense Classes and Beyond

It is known that first-order logic with some counting extensions canbe efficiently evaluated on graph classes with bounded expansion, wheredepth-$r$ minors have constant density. More precisely, the formulasare $\exists x_1. .. x_k \#y \phi(x_1, \ldots, x_k, y)>N$, where $\phi$ is an FO-formula. If $\phi$ is quantifier-free, we canextend this result to \emph{nowhere dense} graph classes with analmost linear FPT run time. Lifting thisresult further to slightly more general graph classes, namely almost nowheredense classes, where the size of depth-$r$ clique minors is subpolynomial, is impossible unless $\rm FPT=W[1]$. On the other hand, in almostnowhere dense classes we can approximate such counting formulas with asmall additive error. In particular, it follows that partial covering problems, such as partialdominating set, have fixed parameter algorithms on nowhere densegraph classes with almost linear running time. Contributed talk given by Daniel Mock Wednesday Wednesday 09h00 - 10h00, Keynote Speaker | HS 3 | chair: Christof Löding | Sven Schewe - Automata for Profit and Pleasure What could be greater fun than toying around with formal structures? One particularly beautiful structure to play with are automata over infinite words, and there is really no need to give any supporting argument for the _pleasure_ part in the title. But how about profit? When using ω-regular languages as target languages for practical applications like Markov chain model checking, MDP model checking and reinforcement learning, reactive synthesis, or as a target for an infinite word played out in a two player game, the classic approach has been to first produce a deterministic automaton D that recognises that language. This deterministic automaton is quite useful: we can essentially play on the syntactic product of the structure and use the acceptance mechanism it inherits from the automaton as target. This is beautiful and moves all the heavy lifting to the required automata transformations. But when we want even more profit in addition to the pleasure, the question arises whether deterministic automata are the best we can do. They are clearly good enough: determinism is as restrictive as it gets, and easily guarantees that one can just work on the product. But what we really want is the reverse: we want an automaton, so that we can work on the product, and determinism is just maximally restrictive, and therefore good enough for everything. At Highlights, all will know that we can lift quite a few restrictions and instead turn to the gains we can make when we focus on the real needs of being able to work on the product. For Markov chains, this could be unambiguous automata, for MDPs this could be good-for-MDP automata, and for synthesis and games, it could be good-for-games automata. We will shed a light to a few nooks and corners of the vast room available open questions and answers, with a bias MDPs analysis in general and reinforcement learning in particular. Coffee Break Wednesday 10h30 - 11h42, Contributed Talks Games 2 | HS 3 | chair: Benjamin Bisping Logic | HS 4 | chair: Marie Fortin Games 2 | HS 3 | chair: Benjamin Bisping Logic | HS 4 | chair: Marie Fortin

Authors

• Daniel Mock

Keywords

No keywords are indexed for this paper.