Search

In epistemic logic, dynamic operators describe the evolution of the knowledge of participating agents through communication, one of the most basic forms of communication being public announcement. Semantically, dynamic operators correspond to transformations of the underlying model. While metatheoretic results on dynamic epistemic logic so far are largely limited to the setting of Kripke models, there is evident interest in extending its scope to non-relational modalities capturing, e.g., uncertainty or collaboration. We develop a generic framework for non-relational dynamic logic by adding dynamic operators to coalgebraic logic. We discuss a range of examples and establish basic results including bisimulation invariance, complexity, and a small model property.

We study the problem of answering a union of Boolean conjunctive queries q against a database Δ, and a logical theory φ which falls in the guarded fragment with transitive guards (GF + TG). We trace the frontier between decidability and undecidability of the problem under consideration. Surprisingly, we show that query answering under GF2 + TG, i.e., the two-variable fragment of GF + TG, is already undecidable (even without equality), whereas its monadic fragment is decidable; in fact, it is 2exptime-complete in combined complexity and coNP-complete in data complexity. We also show that for a restricted class of queries, query answering under GF+TG is decidable. © 2013 Springer-Verlag.

It is well known that many local graph problems, like Vertex Cover and Dominating Set, can be solved in 2O(tw)nO(1) time for graphs with a given tree decomposition of width tw. However, for nonlocal problems, like the fundamental class of connectivity problems, for a long time it was unknown how to do this faster than twO(tw)nO(1) until recently, when Cygan et al. (FOCS 2011) introduced the Cut&Count technique that gives randomized algorithms for a wide range of connectivity problems running in time ctwnO(1) for a small constant c. In this paper, we show that we can improve upon the Cut&Count technique in multiple ways, with two new techniques. The first technique (rank-based approach) gives deterministic algorithms with O(c tw n) running time for connectivity problems (like Hamiltonian Cycle and Stei-ner Tree) and for weighted variants of these; the second technique (determinant approach) gives deterministic algorithms running in time ctwnO(1) for counting versions, e.g., counting the number of Hamiltonian cycles for graphs of treewidth tw. The rank-based approach introduces a new technique to speed up dynamic programming algorithms which is likely to have more applications. The determinant-based approach uses the Matrix Tree Theorem for deriving closed formulas for counting versions of connectivity problems; we show how to evaluate those formulas via dynamic programming.

The highway pricing problem asks for prices to be determined for segments of a single highway such as to maximize the revenue obtainable from a given set of customers with known valuations. The problem is NP-hard and a recent quasi-PTAS suggests that a PTAS might be in reach. Yet, so far it has resisted any attempt for constant-factor approximation algorithms. We relate the tractability of the problem to structural properties of customers' valuations. We show that the problem becomes NP-hard as soon as the average valuations of customers are not; homogeneous, even under further restrictions such as monotonicity. Moreover, we derive an efficient; approximation algorithm, parameterized along the inhomogeneity of customers' valuations. Finally, we discuss extensions of our results that go beyond the highway pricing problem.

In this paper we investigate the synchronization of multithreaded call graphs with reentrance similar to call graphs in Java programs. We model the individual threads as Visibly Pushdown Automata (VPA) and analyse the reachability of a state in the product automaton by means of a Context Free Language (CFL) which captures the synchronized interleaving of threads. We apply this CFL-reachability analysis to detect deadlock.

Vertex ranking has many practical applications, ranging from VLSI layout and sparse matrix factorization to parallel query processing and assembly of modular products. Much research has been done on vertex ranking and related problems, polynomial time algorithms are known for a wide variety of graph classes as well as NP-hardness has been shown for other graph classes. In this paper we propose an extension to vertex ranking. Vertex ranking has many applications in computing a parallel schedule, but there is the assumption that the amount of parallel capacity is unbounded. Many applications do have restricted capacity, such as the number of processors or machines. Therefore we introduce vertex ranking with capacity. In this paper we show that vertex ranking and vertex ranking with capacity do not have a polynomial sized kernel, unless all coNP-complete problems have distillation algorithms. Having to deal with the NP- hardness of both problems, we give, to our knowledge, the first O *(2 n ) time exact algorithm for vertex ranking and use this for devising an O *(2.5875 n ) time algorithm for vertex ranking with capacity. We also show that we can transform vertex rankings to vertex rankings with capacity, and use this for a polynomial time algorithm that transforms an f(n)-approximate vertex ranking to a vertex ranking with capacity of at most f(n) + 1 times the optimum size. Lastly, give an log(c) additive approximation for vertex ranking with capacity when restricted to trees and extend this to graphs of bounded treewidth.

We present a new (1+e)-spanner for sets of n points in Rd. Our spanner has size O(n/ed-1) and maximum degree O(logd n). The main advantage of our spanner is that it can be maintained efficiently as the points move: Assuming the trajectories of the points can be described by bounded-degree polynomials, the number of topological changes to the spanner is O(n2/ed-1), and using a supporting data structure of size O(n logdn) we can handle events in time O(logd+1n). Moreover, the spanner can be updated in time O(log n) if the flight plan of a point changes. This is the first kinetic spanner for points in Rd whose performance does not depend on the spread of the point set.

We examined the use of a new scoring system for the meconium-stained infant, which was designed to help the neonatologist decide on the appropriate therapeutic approach in the delivery room. Eighty meconium-stained infants were scored for: presence of fetal distress; meconium quality; performance of nasopharyngeal suctioning before the first breath and clinical condition in the first minute of life. Management consisted of gentle oropharyngeal suctioning or intubation and tracheal suctioning. Clinical outcome was compared with that of 100 meconium-stained infants born a year earlier. All babies in the control group underwent laryngoscopy and 30% were subsequently intubated. Universal laryngoscopy was not performed in the study group, and only 22.5% of these infants were intubated. The clinical outcome of the studied babies was identical to that of the newborns treated by the standard procedure. The use of the meconium intubation score eliminated the need for universal delivery room laryngoscopy for meconium-stained infants and significantly reduced the number of intubations performed.