Source author record

Antonin Kucera

Antonin Kucera appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Computer Science and Game Theory Logic in Computer Science Artificial Intelligence Formal Languages and Automata Theory

Catalog footprint

What is connected

4works

4topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2015arXiv

Long-Run Average Behaviour of Probabilistic Vector Addition Systems

We study the pattern frequency vector for runs in probabilistic Vector Addition Systems with States (pVASS). Intuitively, each configuration of a given pVASS is assigned one of finitely many patterns, and every run can thus be seen as an infinite sequence of these patterns. The pattern frequency vector assigns to each run the limit of pattern frequencies computed for longer and longer prefixes of the run. If the limit does not exist, then the vector is undefined. We show that for one-counter pVASS, the pattern frequency vector is defined and takes only finitely many values for almost all runs. Further, these values and their associated probabilities can be approximated up to an arbitrarily small relative error in polynomial time. For stable two-counter pVASS, we show the same result, but we do not provide any upper complexity bound. As a byproduct of our study, we discover counterexamples falsifying some classical results about stochastic Petri nets published in the~80s.

preprint2015arXiv

Strategy Synthesis for General Deductive Games Based on SAT Solving

We propose a general framework for modelling and solving deductive games, where one player selects a secret code and the other player strives to discover this code using a minimal number of allowed experiments that reveal some partial information about the code. The framework is implemented in a software tool Cobra, and its functionality is demonstrated by producing new results about existing deductive games.

preprint2012arXiv

Runtime Analysis of Probabilistic Programs with Unbounded Recursion

We study termination time and recurrence time in programs with unbounded recursion, which are either randomized or operate on some statistically quantified inputs. As the underlying formal model for such programs we use probabilistic pushdown automata (pPDA) which are equivalent to probabilistic recursive state machines. We obtain tail bounds for the distribution of termination time for pPDA. We also study the recurrence time for probabilistic recursive programs that are not supposed to terminate (such as system daemons, network servers, etc.). Typically, such programs react to certain requests generated by their environment, and hence operate in finite request-service cycles. We obtain bounds for the frequency of long request-service cycles.

preprint2010arXiv

Reachability Games on Extended Vector Addition Systems with States

We consider two-player turn-based games with zero-reachability and zero-safety objectives generated by extended vector addition systems with states. Although the problem of deciding the winner in such games is undecidable in general, we identify several decidable and even tractable subcases of this problem obtained by restricting the number of counters and/or the sets of target configurations.