Mathematical Foundations of Computer Science 2014: 39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, Part I

Front Matter....Pages -
Partial-Observation Stochastic Reachability and Parity Games....Pages 1-4
Random Deterministic Automata....Pages 5-23
Communication Complexity Theory: Thirty-Five Years of Set Disjointness....Pages 24-43
What Does the Local Structure of a Planar Graph Tell Us About Its Global Structure?....Pages 44-49
Choiceless Polynomial Time on Structures with Small Abelian Colour Classes....Pages 50-62
Sofic-Dyck Shifts....Pages 63-74
A Logical Characterization of Timed (non-)Regular Languages....Pages 75-86
Asymptotic Monadic Second-Order Logic....Pages 87-98
Towards Efficient Reasoning Under Guarded-Based Disjunctive Existential Rules....Pages 99-110
Alternating Parity Krivine Automata....Pages 111-122
Advances in Parametric Real-Time Reasoning....Pages 123-134
Universal Lyndon Words....Pages 135-146
Subword Complexity and Decomposition of the Set of Factors....Pages 147-158
Cyclic Complexity of Words....Pages 159-170
Classifying Recognizable Infinitary Trace Languages Using Word Automata....Pages 171-182
Bounded Variable Logic, Parameterized Logarithmic Space, and Savitch’s Theorem....Pages 183-195
An Algebraic Characterization of Unary Two-Way Transducers....Pages 196-207
Size-Change Abstraction and Max-Plus Automata....Pages 208-219
Alternating Vector Addition Systems with States....Pages 220-231
Information Rate of Some Classes of Non-regular Languages: An Automata-Theoretic Approach....Pages 232-243
Relating Nominal and Higher-Order Rewriting....Pages 244-255
Expressivity and Succinctness of Order-Invariant Logics on Depth-Bounded Structures....Pages 256-266
Two Recursively Inseparable Problems for Probabilistic Automata....Pages 267-278
Monadic Second-Order Logic with Arbitrary Monadic Predicates....Pages 279-290
Transforming Two-Way Alternating Finite Automata to One-Way Nondeterministic Automata....Pages 291-302
Measure Properties of Game Tree Languages....Pages 303-314
On Upper and Lower Bounds on the Length of Alternating Towers....Pages 315-326
 L ax F : Side Conditions and External Evidence as Monads....Pages 327-339
The Monoid of Queue Actions....Pages 340-351
Undecidable Properties of Self-affine Sets and Multi-tape Automata....Pages 352-364
Complexity and Expressivity of Uniform One-Dimensional Fragment with Equality....Pages 365-376
A Unifying Approach for Multistack Pushdown Automata....Pages 377-389
Definability and Transformations for Cost Logics and Automatic Structures....Pages 390-401
Generalised Lyndon-Schützenberger Equations....Pages 402-413
Complexity of Equivalence and Learning for Multiplicity Tree Automata....Pages 414-425
Monadic Datalog and Regular Tree Pattern Queries....Pages 426-437
Model Checking Concurrent Recursive Programs Using Temporal Logics....Pages 438-450
Decidability of the Interval Temporal Logic $\\mathsf{A\\bar{A}B\\bar{B}}$ over the Rationals....Pages 451-463
Reachability in Pushdown Register Automata....Pages 464-473
A Generalization of the Łoś-Tarski Preservation Theorem over Classes of Finite Structures....Pages 474-485
Determinising Parity Automata....Pages 486-498
Tight Bounds for Complementing Parity Automata....Pages 499-510
On Infinite Words Determined by Indexed Languages....Pages 511-522
A Pumping Lemma for Two-Way Finite Transducers....Pages 523-534
Tractability Frontier for Dually-Closed Ord-Horn Quantified Constraint Satisfaction Problems....Pages 535-546
The Dynamic Descriptive Complexity of k -Clique....Pages 547-558
Back Matter....Pages -