Mathematical Foundations of Computer Science 2014

Table of Contents - Volume I.-Invited contributions.- Partial-Observation Stochastic Reachability and Parity Games.- Every graph is easy or hard: dichotomy theorems for graph problems.- Computer Poker and Computational Game Theory.- Random Deterministic Automata.- Communication Complexity Theory: Thirty-Five Years of Set Disjointness.- What does the local structure of a planar graph tell us about its global structure?.- Logic, Semantics, Automata and Theory of Programming.- Choiceless Polynomial Time on structures with small Abelian colour Classes.- Sofic-Dyck shifts.- A Logical Characterization of Timed (non-)Regular Languages.- Asymptotic Monadic Second-Order Logic.- Towards Efficient Reasoning Under Guarded-based Disjunctive Existential Rules.- Alternating Parity Krivine Automata.- Advances in Parametric Real-Time Reasoning.- Universal Lyndon Words.- Subword complexity and decomposition of the set of factors.- Cyclic Complexity of Words.- Classifying Recognizable Infinitary Trace Languages Using Word Automata.- Bounded variable logic, parameterized logarithmic space, and Savitch’s Theorem.- An algebraic characterization of unary two-way transducers.- Size-Change Abstraction and Max-Plus Automata.- Alternating Vector Addition Systems with States.- Information Rate of Some Classes of Non-regular Languages: An Automata-theoretic Approach.- Relating Nominal and Higher-Order Rewriting.- Expressivity and Succinctness of Order-Invariant Logics on Depth-Bounded Structures.- Two Recursively Inseparable Problems for Probabilistic Automata.- Monadic Second-Order Logic with Arbitrary Monadic Predicates.- Transforming two-way alternating finite automata to one-way nondeterministic automata.- Measure Properties of Game Tree Languages.- On Upper and Lower Bounds on the Length of Alternating Towers.- LaxF: Side Conditions and External Evidence as Monads.- The monoid of queue actions.- Undecidable properties of self-affine sets and multi-tape automata.- Complexity and Expressivity of Uniform One-Dimensional Fragment with Equality.- A Unifying Approach for Multistack Pushdown Automata.- Definability and Transformations for Cost Logics and Automatic Structures.- Generalised Lyndon-Schützenberger Equations.- Complexity of Equivalence and Learning for Multiplicity Tree Automata.- Monadic datalog and regular tree pattern queries.- Model Checking Concurrent Recursive Programs using Temporal Logics.- Decidability of the interval temporal logic AABB over the rationals.- Reachability in Pushdown Register Automata.- A Generalization of the Łos-Tarski Preservation Theorem over Classes of Finite Structures.- Determinising Parity Automata.- Tight Bounds for Complementing Parity Automata.- On Infinite Words Determined by Indexed Languages.- A Pumping Lemma for Two-Way Finite Transducers.- Tractability Frontier for Dually-Closed Ord-Horn Quantified Constraint Satisfaction Problems.- The Dynamic Descriptive Complexity of k-Clique.