![Loading...](https://link.springer.com/static/c4a417b97a76cc2980e3c25e2271af3129e08bbe/images/pdf-preview/spacer.gif)
-
Chapter and Conference Paper
Sequent Calculi for Normal Update Logics
Normal update logic is the temporalization of normal conditional logic. Sequent calculi for the least normal update logic $$\mathbf {U...
-
Article
Cyclotomic construction of strong external difference families in finite fields
Strong external difference families (SEDFs) and their generalizations GSEDFs and BGSEDFs in a finite abelian group G are combinatorial designs introduced by Paterson and Stinson (Discret Math 339: 2891–2906, 2016
-
Chapter and Conference Paper
Labelled Sequent Calculus for Inquisitive Logic
A contraction-free and cut-free labelled sequent calculus \(\mathsf {GInqL}\) ...
-
Chapter and Conference Paper
Tableaux for Non-normal Public Announcement Logic
This paper presents a tableau calculus for two semantic interpretations of public announcements over monotone neighbourhood models: the intersection and the subset semantics, developed by Ma and Sano. We show ...
-
Chapter and Conference Paper
Algebraic Semantics for Dynamic Dynamic Logic
Dynamic dynamic logic (DDL) is a generalisation of propositional dynamic logic PDL and dynamic epistemic logic. In this paper, we develop algebraic semantics for DDL without the constant program. We introduce ind...
-
Chapter and Conference Paper
Edge-Disjoint Packing of Stars and Cycles
We study the parameterized complexity of two graph packing problems, Edge-Disjoint \(k\) ...
-
Chapter and Conference Paper
Trees, Paths, Stars, Caterpillars and Spiders
For any \(k \ge 2\) k ≥ ...
-
Chapter and Conference Paper
Quell
We study the computational complexity of the puzzle Quell. The goal is to collect pearls by sliding a droplet of water over them in a grid map. The map contains obstacles. In each move, the droplet slides in o...
-
Chapter and Conference Paper
Shortest Color-Spanning Intervals
Given a set of n points on a line, where each point has one of k colors, and given an integer s i ≥ 1 for each color i, 1 ≤ i ≤ k, the problem Shortest Color-Sp...
-
Chapter and Conference Paper
Competitive Algorithms for Unbounded One-Way Trading
In the one-way trading problem, a seller has some product to be sold to a sequence σ of buyers u 1, u 2, …, u σ arriving online ...
-
Chapter and Conference Paper
How to Update Neighborhood Models
This paper studies two ways of updating neighborhood models: update by taking the intersection of the neighborhoods with the announced proposition, and update by selecting all the neighborhoods that can entail...
-
Chapter and Conference Paper
On Covering Points with Minimum Turns
We point out mistakes in several previous FPT algorithms for k -Link Covering Tour and its variants in ℝ2, and show that the previous NP-hardness proofs for Minimum-Link Rectilinear Covering Tour an...
-
Chapter and Conference Paper
Hardness of Longest Common Subsequence for Sequences with Bounded Run-Lengths
The longest common subsequence (LCS) problem is a classic and well-studied problem in computer science with extensive applications in diverse areas ranging from spelling error corrections to molecular biology....
-
Chapter and Conference Paper
Maximal Empty Boxes Amidst Random Points
We show that the expected number of maximal empty axis-parallel boxes amidst n random points in the unit hypercube [0,1] d in ℝ d is ...
-
Chapter and Conference Paper
Parameterized Complexity in Multiple-Interval Graphs: Domination
We show that several variants of the problem k -Dominating Set, including k -Connected Dominating Set, k -Independent Dominating Set, k -Dominating Clique,
-
Chapter and Conference Paper
H ∞ Synchronization Control in Nonlinear Time-Delay Complex Dynamical Network
On the basis of Lyapunov stability theory and LMI technique, this paper investigates H ∞ synchronization control of time-varying synchronization state in general complex networks with time-delay...
-
Chapter and Conference Paper
Mathematics of Public Announcements
We study some mathematical aspects of public announcement logic (PAL) and its several variants. By a model-theoretic approach, we explore van Benthem’s result that uses recursion axioms to characterize the sub...
-
Chapter and Conference Paper
Flip** Triangles and Rectangles
We study the chromatic number of the flip graph of triangles determined by n points in convex position in the plane, and present new or improved bounds on several related parameters for this graph. We also find t...
-
Chapter and Conference Paper
Algebraic Semantics and Model Completeness for Intuitionistic Public Announcement Logic
In this paper, we start studying epistemic updates using the standard toolkit of duality theory. We focus on public announcements. We give the dual characterization of the corresponding submodel-injection map,...
-
Chapter and Conference Paper
Parameterized Complexity in Multiple-Interval Graphs: Partition, Separation, Irredundancy
We present new results on the parameterized complexities of k - Vertex Clique Partition and k -Separating Vertices in multiple-interval graphs and their complements, and present a very...