Most of these proofs require only little effort, as it is possible to use existing results on three different models from formal language theory and combinatorics on words: Pattern languages, word equations, and regular expressions with back references. This also illustrates how these models can be used as a general toolkit for query languages with string equality operators. Authors: Martin Schuster Abstract: Context-free games are two-player rewriting games that are played on nested strings representing XML documents with embedded function symbols.

These games were introduced to model rewriting processes for intensional documents in the Active XML framework, where input documents are to be rewritten into a given target schema by calls to external services. This talk is based on a paper which studies the setting where dependencies between inputs and outputs of service calls are modelled by transducers.

The paper defines transducer models operating on nested words and studies their properties, as well as the computational complexity of the winning problem for transducer-based context-free games in several scenarios. While the complexity of this problem is quite high in most settings ranging from NP-complete to undecidable , some tractable restrictions are also identified. The paper corresponding to this talk has been accepted for MFCS Authors: Abstract: We investigate minimization of tree pattern queries that use the child relation, descendant relation, node labels, and wildcards. We prove that minimization for such tree patterns is complete for the second level of the polynomial hierarchy and thus solve a problem first attacked by Flesca, Furfaro, and Masciari in We first provide an example that shows that tree patterns cannot be minimized by deleting nodes.

This example shows that the M-NR conjecture, which states that minimality of tree patterns is equivalent to their nonredundancy, is false. We then show how the example can be turned into a gadget that allows us to prove hardness. The paper will be presented at PODS There are some significant differences between SPARQL and the relational algebra for the classical relational data model. First, queries do not access relations directly but rather perform pattern matching on RDF triples.

Patterns may match only partially, so that the result of a query is a heterogeneous relation; different tuples in the result may be defined on different sets of variables. The only feature that comes close to negation are negated bound constraints: the ability to express the condition that a certain variable from the pattern is not matched.

We are intrigued by this language as a new, heterogeneous variant of the classical relational algebra that gives equal weight to outer join and natural join. Indeed, while there already existed studies focusing on outer join in the relational setting [GLR97], the expressive power of outer join in interplay with other query operators has only become a research topic thanks to the new SPARQL context. We want to understand what happens when the use of constraints in patterns is restricted. We distinguish six kinds of constraints: equalities, constant-equalities, bound constraints, and their respective negations.

Our main result is that as soon as inconsistent constraints can be formulated, satisfiability becomes undecidable. So, not only negated bound constraints, but also conjunctions of equalities and inequalities, or just constant equalities by themselves, already cause undecidability. Indeed, we show that MINUS can also be expressed using these constraints instead of negated bound constraints. Conversely, when inconsistent constraints cannot be formulated, satisfiability is shown to be decidable, and a finite model property is observed. A full article on this research has recently been accepted pending minor revisions in the Journal of Artificial Intelligence Research.

Ahmetaj, W. Fischl, M. Pichler, M. Gyssens and G. Arenas and J. ACM, Galindo-Legaria and A. Outerjoin simplification and reordering for query optimization. Kaminski and E. Arenas, and C.

### Bibliographic Information

Our upper bound result shows that this task can be efficiently performed in data complexity, i. Our lower bound shows that, on graphs, there is a first-order query which is always intractable to evaluate on database families of unbounded treewidth under a constructibility assumption , no matter which other restrictions we impose on the databases. This amounts to solving a Gale-Stewart game where a play is a sequence of natural numbers chosen in alternation by two players Input and Output rather than a sequence of bits; so a play is an element of the Baire space rather than of the Cantor space.

First, from a descriptive set theoretical point of view, Matthew de Brecht showed in [dB13] that it is a counterpart of the Baire space in a generalization of descriptive set theory to the more general class of second countable complete quasi-metrizable spaces. As it is a domain, it is also strongly connected to both logic and computer science see the introduction of the recent book of Jean Goubault-Larrecq [GL13].

We propose a game characterization of the notion of continuous reductions in the Scott domain. It allows us to investigate the topological complexity of the subsets of the Scott domain. In particular, the game characterization provides arbitrarily large finite antichains with respect to the quasi-order induced by continuous reducibility.

Semantically, this means that if we are provided a circuit for a language L in V, then putting the function at the input level results in a language that is still in V. This notion has been used with different values of V to characterize the transductions computable in classes of low complexity. Here, we report on problems focusing only on this notion over transductions; we provide decidability properties and characterize continuity through some natural algebraic properties.

Unpublished joint work with Olivier Carton and Charles Paperman. Authors: Abstract: The continuous evolution of a wide variety of systems, including continuous-time Markov chains and linear hybrid automata, can be described in terms of linear differential equations. In this presentation we focus on the decision problem of whether the solution of a system of linear differential equations reaches a target halfspace infinitely often. This recurrent reachability problem can equivalently be formulated as the following Infinite Zeros Problem: does a real-valued function satisfying a given linear differential equation have infinitely many zeros on the non-negative reals?

On the other hand, in the same paper we show that a decision procedure for the Infinite Zeros Problem at order 9 and above would entail a major breakthrough in Diophantine Approximation, specifically an algorithm for computing the Lagrange constants of arbitrary real algebraic numbers to arbitrary precision. In this presentation, we will offer a high-level overview of the problem, followed by an outline of the techniques from model theory and transcendental number theory which proved most useful in establishing our results.

The concept of primitive sets of matrices comes up in a number of problems within control theory, non-homogeneous Markov chains etc. In my talk I will speak about the recently discovered connections between synchronizing automata and primitive sets of matrices. On one hand, the properties of synchronizing automata are relatively well studied due to their applications to industrial automation, coding theory, group theory, etc. On the other hand, there is still a persisting interest of the research community to the topic due to one of the most famous open problems in automata theory.

In my talk I will explain how the aforementioned connections lead to a relatively large number of results about primitive sets of matrices. In my talk the set of matrices with no zero rows and columns, denoted by NZ, will receive a special attention due to its intriguing connections to the Cerny conjecture and the recent generalization of Perron-Frobenius theory for this class. I will characterize the computational complexity of different problems related to the exponent of NZ matrix sets, and present a quadratic bound on the exponents of sets belonging to a special subclass.

These results are not published. For reactive systems, this often requires assumptions about the behaviour of the environment. It is difficult for the designer to identify the assumptions that ensures the existence of a correct controller, and doing so manually can lead to assumptions that are stronger than necessary. As a consequence the generated controllers are sub-optimal in terms of generality and robustness.

In this work, given a specification, we identify the weakest assumptions that ensures the existence of a controller. We also consider two important classes of assumptions: the ones that can be ensured by the environment and assumptions that speaks only about inputs of the systems. We show that optimal assumptions correspond to strongly winning strategies, admissible strategies and remorse-free strategies respectively.

Based on this correspondence, we propose an algorithm for computing optimal assumptions that can be ensured by the environment.

### References

Ramanujam Abstract: Coordination problems at the crux of distributed systems are highly sensitive to the information that agents have about the game and the actual play. There is abundant literature on the challenge of imperfect information, that is, the situation when agents are not perfectly informed about the play history — in the setting, however, that the structure of the game is common knowledge among them.

In this talk, we discuss the situation where players are uncertain about the structure of the game that is being played: the actual winning condition and the choices available to the players are drawn by Nature from a finite set of alternatives. In classical game theory, this is called incomplete information — in contrast to imperfect information; in the computing literature, the terms have been thoroughly confused.

Of course, the combination of incomplete with imperfect information in games of infinite duration leaves little hope for computational tractability in general. We show that it is decidable whether the players have a joint strategy to recover the incomplete information about the game structure, for a significant particular case where each player is perfectly informed about the global state, but not about the actions of the other players.

As a prominent application, we prove that it is decidable whether the grand coalition has a joint strategy that allows to detect unilateral deviations in the setting of infinite games with private monitoring of moves. This is joint work with R. Ramanujam IMSc Chennai. During this talk, we precise the decidability border of MITL synthesis. We show RS is undecidable on finite words too, and present a landscape of restrictions both on the logic and on the possible controllers that are still undecidable. On the positive side, we revisit BResRS and introduce an efficient on-the-fly algorithm to solve it.

Priced timed games are two-player zero-sum games played on priced timed automata whose locations and transitions are labeled by weights modeling the costs of spending time in a state and executing an action, respectively.

## Logic For Concurrency And Synchronisation (Trends In Logic) Free

The goals of the players are to minimise and maximise the cost to reach a target location, respectively. We consider priced timed games with one clock and arbitrary positive and negative weights and show that, for an important subclass of theirs the so-called simple priced timed games , one can compute, in exponential time, the optimal values that the players can achieve, with their associated optimal strategies. As side results, we also show that one-clock priced timed games are determined and that we can use our result on simple priced timed games to solve the more general class of so-called reset-acyclic priced timed games with arbitrary weights and one-clock.

Authors: Abstract: We consider distributed timed systems that implement leader election protocols which are at the heart of clock synchronization proto- cols. We develop abstraction techniques for parameterized model check- ing of such protocols under arbitrary network topologies, where nodes have independently evolving clocks. We apply our technique for model checking the root election part of the flooding time synchronisation pro- tocol FTSP , and obtain improved results compared to previous work. We model check the protocol for all topologies in which the distance to the node to be elected leader is bounded by a given parameter.

Hyperproperties, like observational determinism or symmetry, cannot be expressed as properties of individual computation traces, because they describe a relation between multiple computation traces. HyperLTL is a temporal logic that captures such relations through trace variables, which are introduced through existential and universal trace quantifiers and can be used to refer to multiple computations at the same time. We study the satisfiability problem of HyperLTL. Many practical hyperproperties can be expressed as alternation-free formulas. Our results show that both satisfiability and implication are decidable for such properties.

Authors: Abstract: We described a new approach to deciding satisfiability of quantified bit-vector formulas using binary decision diagrams and approximations. The approach is motivated by the observation that the binary decision diagram for a quantified formula is typically significantly smaller than the diagram for the subformula within the quantifier scope.

The approach relies on the combination of syntactic formula simplifications, tailored initial ordering of BDD variables, and using underapproximations and overapproximations, all of which help to reduce the size of the BDDs during the computation of the BDD corresponding to the input formula.

- Description of the RECRE project!
- Real-Resumes for Financial Jobs.
- Perspectives on the Performance of French Piano Music?
- Logic for Concurrency and Synchronisation (Trends in Logic) - PDF Free Download.
- Pay the Devil.
- Brussels – Highlights of Logic, Games and Automata!
- The Art of Losing: Why the Proteas Choke at the Cricket World Cup.

The experimental results show that it decides more benchmarks from the SMT-LIB repository than state-of-the-art SMT solvers for this theory, namely Z3 and CVC4, which solve quantified bit-vector formulas using the quantifier instantiation. Furthermore, we compared the implemented solver with the mentioned state-of-the art solvers on the quantified formulas produced by the symbolic model checker SymDIVINE. Underapproximations used in the approach are performed by reducing the bit-width of all existentially quantified variables.

Similarly, overapproximations are performed by reducing the bit-width of all existentially quantified variables. We describe several ways of reducing bit-width of a variable and we evaluate the effect of each of these on the performance of the solver. The publication with the detailed description of the approach, experimental results, and the evaluation of all three components used in the approach was accepted to SAT We investigate the complexity of grammar-based compression, i. It is shown that the shortest-grammar problem remains NP-complete if the alphabet is fixed and has a size of at least 24 which settles an open question.

On the other hand, this problem can be solved in polynomial-time, if the number of nonterminals is bounded, which is shown by encoding the problem as a problem on graphs with interval structure. Similar results are also given for 1-level grammars, i. We show that separability problem of reachability sets of Vector Addition Systems by both modular and unary sets is decidable.

We study the concept of synchronizing data words in RAs: Does there exist a data word that sends all states of the RA to a single state? We study the existence of Hanf normal forms for extensions FO Qs of first-order logic by sets Qs of unary counting quantifiers, i. We show that a formula from FO Qs can be transformed into a formula in Hanf normal form that is equivalent on all structures of degree at most d if, and only if, all counting quantifiers occurring in the formula are ultimately periodic.

This transformation can be carried out in worst-case optimal 3-fold exponential time. As an immediate consequence, we obtain that on finite structures of degree at most d, model checking of first-order logic with modulo-counting quantifiers is fixed-parameter tractable. Order invariance is frequently used for logic-based approaches in computer science. Order-invariant formulas capture unordered problems of complexity classes and they model the independence of the answer to a database query from low-level aspects of databases.

We study the expressive power of order-invariant monadic second-order MSO and first-order FO logic on restricted classes of structures that admit certain forms of tree decompositions not necessarily of bounded width. This extends an earlier result for trees due to Courcelle. Moreover, we show that all properties definable in order-invariant FO are also definable in MSO on these classes. This is joint work with Michael Elberfeld and Martin Grohe. It was accepted to LICS Authors: Thomas Schwentick, Nils Vortmeier and Thomas Zeume Abstract: A dynamic program, as introduced by Dong, Su and Topor and Patnaik and Immerman, maintains the result of a fixed query for an input database which is subject to modifications.

It can use an auxiliary database whose relations are updated via first-order formulas upon modifications of the input database. In the original setting, only insertions and deletions of single tuples are considered. In this talk, which is based on joint work with Thomas Schwentick and Thomas Zeume, we will allow modifications defined by restricted first-order formulas and review which queries can still be maintained. This talk is based on so far unpublished work.

The unbounding quantifier is used to say that a property of finite sets holds for sets of arbitrarily large size. We prove that the logic is undecidable on infinite words, i. This settles an open problem about the logic, and improves a previous undecidability result, which used infinite trees and additional axioms from set theory.

More precisely, consider the following notions: D a class of graphs is called MSO definable if it can be defined in monadic second-order logic with counting quantifiers. R a class of graphs is called recognisable if for each k there is a tree automaton which recognises width k tree decompositions of graphs satisfying the property. Many natural graph classes are easily seen to satisfy D , e.

In the talk, I will discuss a proof of this conjecture. A property is synchronized in a system if it holds in all paths of a certain length. The new logic is obtained by using the same path quantifiers and temporal operators as in CTL, but allowing a different order of the quantifiers. This small syntactic variation induces a logic that can express non-regular properties for which known extensions of MSO with equality of path length are undecidable.

Authors: joint work with Anca Muscholl and Igor Walukiewicz Abstract: We consider here parametrized asynchronous shared-memory pushdown systems, as introduced by Hague. The past decade has witnessed the evolution of workflow specification frameworks from the traditional process-centric approach towards data-awareness. Process-centric formalisms focus on control flow while under-specifying the underlying data and its manipulations by the process tasks, often abstracting them away completely.

In contrast, data-aware formalisms treat data as first-class citizens. In a nutshell, artifacts consist of data that is updated by a set of services that implement business process tasks, specified declaratively by pre-and-post conditions. The artifact approach has spawned a rich body of research in academia, focused primarily on verification. The present work represents a significant advance on the artifact verification problem on several fronts. In particular, the model features task hierarchy, concurrency, and richer artifact data including updatable artifact relations.

The results require qualitatively new techniques, because the reduction to finite-state model checking used in previous work is no longer possible. The arithmetic constraints are handled using quantifier elimination techniques, adapted to our setting. The talk will present some of the mathematical intuition behind the results, focusing on two of my favorite aspects: i the use of Vector Addition Systems to handle unbounded evolving data, and ii the new hierarchical variant of LTL-FO.

We answer positively the main question left open by their work, namely establish that reachability witnesses of pseudo-polynomial length always exist. Hence, when the input vectors are given in unary, the improved guess-and-verify algorithm requires only logarithmic space. When performing a branching step, the counter values are distributed non-deterministically between two successor processes. A run of a BVASS consequently becomes a tree, and reachability is to decide whether a given configuration is the root of a reachability tree. Our recent result is that the reachability, coverability and boundedness problems are polynomial-time complete for BVASS in dimension one.

Regarding the reachability problem, this is the first decidability result in a subclass of BVASS known so far. Authors: joint with Igor Potapov Liverpool and Julien Reichert Abstract: Robot game is a two-player vector addition game played on the integer lattice. Both players have sets of vectors and in each turn the vector chosen by a player is added to the current configuration vector of the game. One of the players, called Eve, tries to play the game from the initial configuration to the origin while the other player, Adam, tries to avoid the origin.

The problem is to decide whether or not Eve has a winning strategy. In this talk we prove undecidability of the robot game in dimension two answering the question formulated by Doyen and Rabinovich in and closing the gap between undecidable and decidable cases. The coverability problem captures the verification of safety properties in this nominal extension of Petri nets with name management and fresh name creation.

Joint work with R. Authors: Abstract: In Petri nets with data, every token carries a data value, and executability of a transition is conditioned by a relation between data values involved. Decidability status of various decision problems for Petri nets with data may depend on the structure of data domain. For instance, if data values are only tested for equality, decidability status of the reachability problem is unknown but decidability is conjectured. On the other hand, the reachability problem is undecidable if data values are additionally equipped with a total ordering.

We investigate the frontiers of decidability for Petri nets with various data, and formulate the WQO Dichotomy Conjecture: under a mild assumption, either a data domain exhibits a well quasi-order in which case one can apply the general setting of well-structured transition systems to solve problems like coverability or boundedness , or essentially all the decision problems are undecidable for Petri nets over that data domain. However, modal operates on arbitrary labelled transition systems while automata are usually defined only on infinite trees with one successor per label.

This seemingly harmless difference has suprising consequences. Non-deterministic automata for example can be generalised to arbitrary labelling systems and used to define the non-deterministic fragment of modal. I argue that this fragment is less powerful than disjunctive modal mu, the fragment of modal mu originally conceived in order to mimic non-determinism in automata. It also has unique properties which suggest that this might be a rare example of a non-trivial fragment of modal for which deciding the alternation hierarchy might be within reach.

In any case, its index-problem is distinct from the index-problem for non-deterministic automata. The take-away of this talk is that the relationship between automata theory and the modal mu calculus has its pitfalls and we have to take adequate care when moving between the two theories.

Authors: joint with Aniello Murano, Giuseppe Perelli and Moshe Vardi Abstract: Parity games are abstract infinite-round games that take an important role in formal verification. In the basic setting, these games are two-player, turn-based, and played under perfect information on directed graphs, whose nodes are labeled with priorities. International Symposium on Functional and Logic Programming. Conference paper First Online: 21 February This is a preview of subscription content, log in to check access.

Armstrong, J. Benton, N. In: Magnusson, B. ECOOP LNCS, vol. Chandy, K. Charles, P. ACM Google Scholar. Foster, I. Gupta, V. In: Antsaklis, P. HS As it is a domain, it is also strongly connected to both logic and computer science see the introduction of the recent book of Jean Goubault-Larrecq [GL13]. We propose a game characterization of the notion of continuous reductions in the Scott domain. It allows us to investigate the topological complexity of the subsets of the Scott domain. In particular, the game characterization provides arbitrarily large finite antichains with respect to the quasi-order induced by continuous reducibility.

Semantically, this means that if we are provided a circuit for a language L in V, then putting the function at the input level results in a language that is still in V. This notion has been used with different values of V to characterize the transductions computable in classes of low complexity. Here, we report on problems focusing only on this notion over transductions; we provide decidability properties and characterize continuity through some natural algebraic properties. Unpublished joint work with Olivier Carton and Charles Paperman. Authors: Abstract: The continuous evolution of a wide variety of systems, including continuous-time Markov chains and linear hybrid automata, can be described in terms of linear differential equations.

In this presentation we focus on the decision problem of whether the solution of a system of linear differential equations reaches a target halfspace infinitely often. This recurrent reachability problem can equivalently be formulated as the following Infinite Zeros Problem: does a real-valued function satisfying a given linear differential equation have infinitely many zeros on the non-negative reals? On the other hand, in the same paper we show that a decision procedure for the Infinite Zeros Problem at order 9 and above would entail a major breakthrough in Diophantine Approximation, specifically an algorithm for computing the Lagrange constants of arbitrary real algebraic numbers to arbitrary precision.

In this presentation, we will offer a high-level overview of the problem, followed by an outline of the techniques from model theory and transcendental number theory which proved most useful in establishing our results. The concept of primitive sets of matrices comes up in a number of problems within control theory, non-homogeneous Markov chains etc. In my talk I will speak about the recently discovered connections between synchronizing automata and primitive sets of matrices.

On one hand, the properties of synchronizing automata are relatively well studied due to their applications to industrial automation, coding theory, group theory, etc. On the other hand, there is still a persisting interest of the research community to the topic due to one of the most famous open problems in automata theory.

In my talk I will explain how the aforementioned connections lead to a relatively large number of results about primitive sets of matrices. In my talk the set of matrices with no zero rows and columns, denoted by NZ, will receive a special attention due to its intriguing connections to the Cerny conjecture and the recent generalization of Perron-Frobenius theory for this class.

I will characterize the computational complexity of different problems related to the exponent of NZ matrix sets, and present a quadratic bound on the exponents of sets belonging to a special subclass. These results are not published. For reactive systems, this often requires assumptions about the behaviour of the environment.

It is difficult for the designer to identify the assumptions that ensures the existence of a correct controller, and doing so manually can lead to assumptions that are stronger than necessary. As a consequence the generated controllers are sub-optimal in terms of generality and robustness. In this work, given a specification, we identify the weakest assumptions that ensures the existence of a controller. We also consider two important classes of assumptions: the ones that can be ensured by the environment and assumptions that speaks only about inputs of the systems.

We show that optimal assumptions correspond to strongly winning strategies, admissible strategies and remorse-free strategies respectively. Based on this correspondence, we propose an algorithm for computing optimal assumptions that can be ensured by the environment. Ramanujam Abstract: Coordination problems at the crux of distributed systems are highly sensitive to the information that agents have about the game and the actual play.

There is abundant literature on the challenge of imperfect information, that is, the situation when agents are not perfectly informed about the play history — in the setting, however, that the structure of the game is common knowledge among them. In this talk, we discuss the situation where players are uncertain about the structure of the game that is being played: the actual winning condition and the choices available to the players are drawn by Nature from a finite set of alternatives.

In classical game theory, this is called incomplete information — in contrast to imperfect information; in the computing literature, the terms have been thoroughly confused. Of course, the combination of incomplete with imperfect information in games of infinite duration leaves little hope for computational tractability in general.

- Schloss Dagstuhl : Seminar Homepage.
- Coach Us Essential Coaching Tools: Your Complete Practice Resource.
- List of Publications of Catuscia Palamidessi;
- List of Publications of Catuscia Palamidessi.
- Inhibition of Tumor Induction and Development!
- Mrs. Perkinss Electric Quilt: And Other Intriguing Stories of Mathematical Physics.
- HTML5 and CSS3 All-in-One For Dummies (3rd Edition).

We show that it is decidable whether the players have a joint strategy to recover the incomplete information about the game structure, for a significant particular case where each player is perfectly informed about the global state, but not about the actions of the other players. As a prominent application, we prove that it is decidable whether the grand coalition has a joint strategy that allows to detect unilateral deviations in the setting of infinite games with private monitoring of moves. This is joint work with R. Ramanujam IMSc Chennai. During this talk, we precise the decidability border of MITL synthesis.

We show RS is undecidable on finite words too, and present a landscape of restrictions both on the logic and on the possible controllers that are still undecidable. On the positive side, we revisit BResRS and introduce an efficient on-the-fly algorithm to solve it. Priced timed games are two-player zero-sum games played on priced timed automata whose locations and transitions are labeled by weights modeling the costs of spending time in a state and executing an action, respectively.

The goals of the players are to minimise and maximise the cost to reach a target location, respectively. We consider priced timed games with one clock and arbitrary positive and negative weights and show that, for an important subclass of theirs the so-called simple priced timed games , one can compute, in exponential time, the optimal values that the players can achieve, with their associated optimal strategies. As side results, we also show that one-clock priced timed games are determined and that we can use our result on simple priced timed games to solve the more general class of so-called reset-acyclic priced timed games with arbitrary weights and one-clock.

Authors: Abstract: We consider distributed timed systems that implement leader election protocols which are at the heart of clock synchronization proto- cols. We develop abstraction techniques for parameterized model check- ing of such protocols under arbitrary network topologies, where nodes have independently evolving clocks. We apply our technique for model checking the root election part of the flooding time synchronisation pro- tocol FTSP , and obtain improved results compared to previous work.

We model check the protocol for all topologies in which the distance to the node to be elected leader is bounded by a given parameter. Hyperproperties, like observational determinism or symmetry, cannot be expressed as properties of individual computation traces, because they describe a relation between multiple computation traces.

HyperLTL is a temporal logic that captures such relations through trace variables, which are introduced through existential and universal trace quantifiers and can be used to refer to multiple computations at the same time. We study the satisfiability problem of HyperLTL. Many practical hyperproperties can be expressed as alternation-free formulas. Our results show that both satisfiability and implication are decidable for such properties.

Authors: Abstract: We described a new approach to deciding satisfiability of quantified bit-vector formulas using binary decision diagrams and approximations. The approach is motivated by the observation that the binary decision diagram for a quantified formula is typically significantly smaller than the diagram for the subformula within the quantifier scope. The approach relies on the combination of syntactic formula simplifications, tailored initial ordering of BDD variables, and using underapproximations and overapproximations, all of which help to reduce the size of the BDDs during the computation of the BDD corresponding to the input formula.

The experimental results show that it decides more benchmarks from the SMT-LIB repository than state-of-the-art SMT solvers for this theory, namely Z3 and CVC4, which solve quantified bit-vector formulas using the quantifier instantiation. Furthermore, we compared the implemented solver with the mentioned state-of-the art solvers on the quantified formulas produced by the symbolic model checker SymDIVINE. Underapproximations used in the approach are performed by reducing the bit-width of all existentially quantified variables.

Similarly, overapproximations are performed by reducing the bit-width of all existentially quantified variables. We describe several ways of reducing bit-width of a variable and we evaluate the effect of each of these on the performance of the solver. The publication with the detailed description of the approach, experimental results, and the evaluation of all three components used in the approach was accepted to SAT We investigate the complexity of grammar-based compression, i. It is shown that the shortest-grammar problem remains NP-complete if the alphabet is fixed and has a size of at least 24 which settles an open question.

On the other hand, this problem can be solved in polynomial-time, if the number of nonterminals is bounded, which is shown by encoding the problem as a problem on graphs with interval structure. Similar results are also given for 1-level grammars, i. We show that separability problem of reachability sets of Vector Addition Systems by both modular and unary sets is decidable.

We study the concept of synchronizing data words in RAs: Does there exist a data word that sends all states of the RA to a single state? We study the existence of Hanf normal forms for extensions FO Qs of first-order logic by sets Qs of unary counting quantifiers, i. We show that a formula from FO Qs can be transformed into a formula in Hanf normal form that is equivalent on all structures of degree at most d if, and only if, all counting quantifiers occurring in the formula are ultimately periodic. This transformation can be carried out in worst-case optimal 3-fold exponential time.

As an immediate consequence, we obtain that on finite structures of degree at most d, model checking of first-order logic with modulo-counting quantifiers is fixed-parameter tractable. Order invariance is frequently used for logic-based approaches in computer science. Order-invariant formulas capture unordered problems of complexity classes and they model the independence of the answer to a database query from low-level aspects of databases. We study the expressive power of order-invariant monadic second-order MSO and first-order FO logic on restricted classes of structures that admit certain forms of tree decompositions not necessarily of bounded width.

This extends an earlier result for trees due to Courcelle. Moreover, we show that all properties definable in order-invariant FO are also definable in MSO on these classes. This is joint work with Michael Elberfeld and Martin Grohe. It was accepted to LICS Authors: Thomas Schwentick, Nils Vortmeier and Thomas Zeume Abstract: A dynamic program, as introduced by Dong, Su and Topor and Patnaik and Immerman, maintains the result of a fixed query for an input database which is subject to modifications. It can use an auxiliary database whose relations are updated via first-order formulas upon modifications of the input database.

In the original setting, only insertions and deletions of single tuples are considered. In this talk, which is based on joint work with Thomas Schwentick and Thomas Zeume, we will allow modifications defined by restricted first-order formulas and review which queries can still be maintained. This talk is based on so far unpublished work. The unbounding quantifier is used to say that a property of finite sets holds for sets of arbitrarily large size.

We prove that the logic is undecidable on infinite words, i. This settles an open problem about the logic, and improves a previous undecidability result, which used infinite trees and additional axioms from set theory. More precisely, consider the following notions: D a class of graphs is called MSO definable if it can be defined in monadic second-order logic with counting quantifiers.

R a class of graphs is called recognisable if for each k there is a tree automaton which recognises width k tree decompositions of graphs satisfying the property. Many natural graph classes are easily seen to satisfy D , e. In the talk, I will discuss a proof of this conjecture. A property is synchronized in a system if it holds in all paths of a certain length. The new logic is obtained by using the same path quantifiers and temporal operators as in CTL, but allowing a different order of the quantifiers.

This small syntactic variation induces a logic that can express non-regular properties for which known extensions of MSO with equality of path length are undecidable. Authors: joint work with Anca Muscholl and Igor Walukiewicz Abstract: We consider here parametrized asynchronous shared-memory pushdown systems, as introduced by Hague. The past decade has witnessed the evolution of workflow specification frameworks from the traditional process-centric approach towards data-awareness.

Process-centric formalisms focus on control flow while under-specifying the underlying data and its manipulations by the process tasks, often abstracting them away completely. In contrast, data-aware formalisms treat data as first-class citizens. In a nutshell, artifacts consist of data that is updated by a set of services that implement business process tasks, specified declaratively by pre-and-post conditions.

The artifact approach has spawned a rich body of research in academia, focused primarily on verification. The present work represents a significant advance on the artifact verification problem on several fronts. In particular, the model features task hierarchy, concurrency, and richer artifact data including updatable artifact relations.

The results require qualitatively new techniques, because the reduction to finite-state model checking used in previous work is no longer possible. The arithmetic constraints are handled using quantifier elimination techniques, adapted to our setting.

The talk will present some of the mathematical intuition behind the results, focusing on two of my favorite aspects: i the use of Vector Addition Systems to handle unbounded evolving data, and ii the new hierarchical variant of LTL-FO. We answer positively the main question left open by their work, namely establish that reachability witnesses of pseudo-polynomial length always exist. Hence, when the input vectors are given in unary, the improved guess-and-verify algorithm requires only logarithmic space.

When performing a branching step, the counter values are distributed non-deterministically between two successor processes. A run of a BVASS consequently becomes a tree, and reachability is to decide whether a given configuration is the root of a reachability tree. Our recent result is that the reachability, coverability and boundedness problems are polynomial-time complete for BVASS in dimension one. Regarding the reachability problem, this is the first decidability result in a subclass of BVASS known so far. Authors: joint with Igor Potapov Liverpool and Julien Reichert Abstract: Robot game is a two-player vector addition game played on the integer lattice.

Both players have sets of vectors and in each turn the vector chosen by a player is added to the current configuration vector of the game. One of the players, called Eve, tries to play the game from the initial configuration to the origin while the other player, Adam, tries to avoid the origin. The problem is to decide whether or not Eve has a winning strategy. In this talk we prove undecidability of the robot game in dimension two answering the question formulated by Doyen and Rabinovich in and closing the gap between undecidable and decidable cases.

## Structured programming

The coverability problem captures the verification of safety properties in this nominal extension of Petri nets with name management and fresh name creation. Joint work with R. Authors: Abstract: In Petri nets with data, every token carries a data value, and executability of a transition is conditioned by a relation between data values involved. Decidability status of various decision problems for Petri nets with data may depend on the structure of data domain.

For instance, if data values are only tested for equality, decidability status of the reachability problem is unknown but decidability is conjectured. On the other hand, the reachability problem is undecidable if data values are additionally equipped with a total ordering. We investigate the frontiers of decidability for Petri nets with various data, and formulate the WQO Dichotomy Conjecture: under a mild assumption, either a data domain exhibits a well quasi-order in which case one can apply the general setting of well-structured transition systems to solve problems like coverability or boundedness , or essentially all the decision problems are undecidable for Petri nets over that data domain.

However, modal operates on arbitrary labelled transition systems while automata are usually defined only on infinite trees with one successor per label. This seemingly harmless difference has suprising consequences. Non-deterministic automata for example can be generalised to arbitrary labelling systems and used to define the non-deterministic fragment of modal.

I argue that this fragment is less powerful than disjunctive modal mu, the fragment of modal mu originally conceived in order to mimic non-determinism in automata. It also has unique properties which suggest that this might be a rare example of a non-trivial fragment of modal for which deciding the alternation hierarchy might be within reach. In any case, its index-problem is distinct from the index-problem for non-deterministic automata. The take-away of this talk is that the relationship between automata theory and the modal mu calculus has its pitfalls and we have to take adequate care when moving between the two theories.

Authors: joint with Aniello Murano, Giuseppe Perelli and Moshe Vardi Abstract: Parity games are abstract infinite-round games that take an important role in formal verification. In the basic setting, these games are two-player, turn-based, and played under perfect information on directed graphs, whose nodes are labeled with priorities. The winner of a play is determined according to the parities even or odd of the minimal priority occurring infinitely often in that play.

In the last two decades, a variety of algorithms have been proposed. Many of them have been also implemented in a platform named PGSolver. This has enabled an empirical evaluation of these algorithms and a better understanding of their relative merits. In this paper, we further contribute to this subject by implementing, for the first time, an algorithm based on alternating automata. More precisely, we consider an algorithm introduced by Kupferman and Vardi that solves a parity game by solving the emptiness problem of a corresponding alternating parity automaton.

Our empirical evaluation demonstrates that this algorithm outperforms other algorithms when the game has a a small number of priorities relative to the size of the game. In many concrete applications, we do indeed end up with parity games where the number of priorities is relatively small. This makes the new algorithm quite useful in practice. In the literature, who wins a play is defined via winning conditions such as Muller, energy, reachability, mean-payoff, etc. The usual winning conditions guarantee the existence of winning strategies that are simple enough to be implemented via finite automata.

This guarantee is called finite-memory determinacy. Advanced modeling may involve combinations of the usual winning conditions mentioned above. Finite-memory determinacy may or may not be preserved by such combinations. I will describe a criterion for boolean combinations of winning conditions to preserve this determinacy. The criterion is general enough to imply finite-memory determinacy of energy Muller games, multi-dimensional bounded energy games, etc.

Alternatively, they can be seen as a model of concurrency with synchronized choice as communication primitive. Well-designed negotiations must be sound, meaning that, whatever its current state, the negotiation can still be completed. They have also provided an algorithm for an intermediate class of acyclic, non-deterministic negotiations, but left the complexity of the soundness problem open. In the first part of this paper we study two further analysis problems for sound acyclic deterministic negotiations, called the race and the omission problem, and give polynomial algorithms.

We use these results to provide the first polynomial algorithm for some analysis problems of workflow nets with data previously studied by Trcka, van der Aalst, and Sidorova. We show that soundness of acyclic, weakly non-deterministic negotiations is in PTIME, and that checking soundness is already NP-complete for slightly more general classes. Those objectives offer powerful abstraction mechanisms and often yield nice properties such as memoryless determinacy. However, their very nature provides no guarantee on time bounds within which something good can be witnessed. In this work, we consider two approaches toward inclusion of time bounds in parity games.

The first one, parity-response games, is based on the notion of finitary parity games and parity games with costs. The second one, window parity games, is inspired by window mean-payoff games. We compare the two approaches and show that while they prove to be equivalent in some contexts, window parity games offer a more tractable alternative when the time bound is given as a parameter P vs PSPACE. In particular, it provides a conservative approximation of parity games computable in polynomial time.

Furthermore, we extend both approaches to the multi-dimension setting. We give the full picture for both types of games with regard to complexity and memory bounds. I will focus on measures that depend only on the rules of the games, and not on how people actually play them. Finally, I will present numerical estimates of these measures for several well-known games and a sport. The reason for targeting average controllability, rather than minimum or maximum controllability, stems from the observation that the first may more accurately approximate the behavior of a population of players of various skill levels.

Authors: Abstract: We consider the fixed-delay synthesis problem for continuous-time Markov chains extended with fixed-delay transitions fdCTMC. The goal is to synthesize concrete values of the fixed-delays timeouts that minimize the expected total cost incurred before reaching a given set of target states.

The same problem has been considered and solved in previous works by computing an optimal policy in a certain discrete-time Markov decision process with a huge number of actions that correspond to suitably discretized values of the timeouts. In this paper, we design a symbolic fixed-delay synthesis algorithm which avoids the explicit construction of large action spaces.

The candidate actions are selected by minimizing a certain objective function by computing its symbolic derivative and extracting a univariate polynomial whose roots are precisely the points where the derivative takes zero value. Since roots of high degree univariate polynomials can be isolated very efficiently using modern mathematical software, we achieve not only drastic memory savings but also speedup by three orders of magnitude compared to the previous methods.

Intuitively, decisiveness allows one to lift the good properties of finite Markov chains to infinite Markov chains.