Mathematical Foundations of Computer Science 2015

Name: Mathematical Foundations of Computer Science 2015 | 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part I
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part I

Giuseppe F. Italiano Giovanni Pighizzini Donald T. Sannella(Editor)

Springer (Publisher)

Published on 10. August 2015

XXVI, 459 pages

E-Book

PDF with digital watermarking

System requirements

978-3-662-48057-1 (ISBN)

€53.49incl. 7% vat

System requirements

for PDF with digital watermarking

E-Book Single Licence

Available for download

Description

More details

Other editions

Content

Intro
Preface
Conference Organization
Invited Contributions
Modular Reasoning for Behavior-Preserving Data Structure Refactorings
Minimal and Monotone Minimal Perfect Hash Functions
Equational Properties of Fixed Point Operations in Cartesian Categories: An Overview
Reversible and Irreversible Computations of Deterministic Finite-State Devices
Robust Inference and Local Algorithms
Contents - Part I
Contents - Part II
Invited Contributions
Minimal and Monotone Minimal Perfect Hash Functions
1 Introduction
2 Definitions and Notation
3 Generalities
4 Minimal Perfect Hash Functions
4.1 The MWHC Construction
4.2 Hash, Displace and Compress
5 Monotone Minimal Perfect Hash Functions
5.1 Longest Common Prefixes
5.2 Z-Fast Tries
6 Conclusions
References
Equational Properties of Fixed Point Operations in Cartesian Categories: An Overview
1 Introduction
2 Models
3 Axiomatization
4 Analysis of the Axioms
5 Implicational Axiomatizations
6 Relative Axiomatization
7 Adding Residuation
References
Reversible and Irreversible Computations of Deterministic Finite-State Devices
1 Introduction
2 Preliminaries and the Notion of Logical Reversibility
3 Size of Reversible Finite Automata
3.1 Trade-Offs
3.2 Decidability
4 Queues and Pushdown Stores
4.1 Computational Capacity
4.2 Decidability and Closure Properties
References
Robust Inference and Local Algorithms
1 Introduction
1.1 Motivating Scenarios
1.2 Model: Overview
1.3 Results: Highlights
1.4 Algorithmic Techniques
2 Related Work
3 Model
4 Main Results
References
Logic, Semantics, Automata and Theory of Programming
Uniform Generation in Trace Monoids
1 Introduction
2 Warm-Up: Uniform Measure for Commuting Alphabets
3 Uniform and Sub-uniform Measures for Trace Monoids
4 Uniform Generation of Finite Traces
References
When Are Prime Formulae Characteristic?
1 Introduction
2 Process Semantics Defined Logically
2.1 Characteristic and Prime Formulae
3 Characterization by Primality for Logical Preorders
3.1 Paths to Decomposability
4 Application to Finitely Many Processes
5 Application to Semantics in van Glabbeek's Spectrum
5.1 Finite Characterization
5.2 Existence of
6 Conclusions
References
Stochastization of Weighted Automata
1 Introduction
2 Preliminaries
3 Motivation
3.1 A WFA-Based Approach to Reasoning About Online Algorithms
3.2 Approximated Determinization
4 Stochastization of General WFAs
5 Stochastization of Constant Ambiguous WFAs
References
Algebraic Synchronization Criterion and Computing Reset Words
1 Introduction
2 Algebraic Synchronization Criterion
3 The Cerný Conjecture and Random Automata
4 Synchronizing Finite Prefix Codes
5 Finding Reset Words of the Bounded Lengths
5.1 Synchronizing Quasi-Eulerian Automata
5.2 Synchronizing Quasi-One-Cluster Automata
References
Recurrence Function on Sturmian Words: A Probabilistic Study
1 Introduction
2 The Recurrence Function of Sturmian Words
3 Probabilistic Model and Main Results
3.1 Position
3.2 Probabilistic Model
3.3 Results for a Constant Position
3.4 Results When the Sequence k 0
4 Strategy for the Proofs.
4.1 Smooth Sequences
4.2 The Dynamical System and the Perron-Frobenius Operator
4.3 Smooth Random Variables and Perron-Frobenius Operator
4.4 Asymptotic Study of Smooth Variables
5 Conclusion
References
Exponential-Size Model Property for PDL with Separating Parallel Composition
1 Introduction
2 Propositional Dynamic Logic with Separating Parallel Composition (PPDL)
3 Fischer-Ladner Closure
3.1 Placeholders and Marking Functions
3.2 Fischer-Ladner Closure
4 Threads, Twines and Neat Models
5 Neat Model Property
5.1 Unraveling
5.2 Pruning
6 Piecewise Filtration
7 Conclusion
References
A Circuit Complexity Approach to Transductions
1 Preliminaries
2 Circuit Frameworks for Variable-Length Functions
2.1 Noninversability
2.2 Output Length as a Parameter
3 Separability, Definability, and Lm-Varieties of Stamps
4 The Transductions in
5 An Application to and
6 Discussion and Limitations
References
Locally Chain-Parsable Languages
1 Introduction
2 Preliminaries
3 Chain-Driven Automata
4 Locally Chain-Parsable Languages
4.1 Extended Chains, Conflicts and Decidability of the LCP Property
4.2 Basic Properties of Local Chain-Parsable Languages
5 LCPL Versus Operator-Precedence and Input-Driven Languages
6 Related Work and Conclusions
References
Classes of Languages Generated by the Kleene Star of a Word
1 Introduction
2 Recognisability and the Profinite Monoid
3 The Languages u*
4 Equational Characterisations of L, Lq and Bq
4.1 Equational Characterisations of Algebraic Structures of Regular Languages
4.2 Characterisations of L, Lq and Bq
5 The Case of the Boolean Algebra B
5.1 Equivalence Classes Over N and Profinite Numbers
5.2 Characterisation of B
6 Decidability
7 The Case of a Unary Alphabet
8 Conclusion
References
Relating Paths in Transition Systems: The Fall of the Modal Mu-Calculus
1 Introduction
2 Preliminary Notions
3 Expressive Completeness Issues
4 Tree Automata for the jumping -calculus
5 Games and the jumping -calculus
6 Conclusion and Perspectives
References
Weighted Automata and Logics on Graphs
1 Introduction
2 Graph Acceptors
3 Weighted Graph Automata
4 A Nivat Theorem for Weighted Graph Automata
5 Weighted Logics for Graphs
6 Words, Trees, and Other Structures
7 Conclusion
References
Longest Gapped Repeats and Palindromes
1 Introduction
2 Preliminaries
3 Lower and Upper Bounded Gap
4 Lower Bounded Gap
5 Long Armed Repeats and Palindromes
References
Quasiperiodicity and Non-computability in Tilings
1 Introduction
2 Self-simulating Tilings (Reminder)
2.1 Implementing Some Given Tile Set with a Large Enough Zoom Factor
2.2 A Self-similar Tile Set: Implementing Itself
3 Quasiperiodicity and Aperiodicity
3.1 Supplementary Features: What Else We Can Assume on the Fixed-Point Tiling
4 Proof of Theorem??
5 From Aperiodicity to Non-computability
References
The Transitivity Problem of Turing Machines
1 Introduction
2 Definitions
2.1 Turing Machines
2.2 Topological and Symbolic Dynamics
2.3 Turing Machines Seen as Dynamical Systems
3 Transitivity of Turing Machines
3.1 Characterizing Transitivity Properties
3.2 The SMART Machine
4 The Complexity of Topological Transitivity
4.1 Construction Techniques
4.2 Undecidability of Transitivities
5 The Complexity of Minimality
References
Strong Inapproximability of the Shortest Reset Word
1 Introduction
2 Preliminaries
3 Simple Hardness Result
4 Hardness with Ratio n
5 Hardness with Ratio n1-
References
Finitary Semantics of Linear Logic and Higher-Order Model-Checking
1 Introduction
2 Higher-Order Recursion Schemes and the Y-Calculus
3 MSO and Alternating Parity Tree Automata
4 The Scott Semantics of Linear Logic
5 A Finitary Interpretation of the Simply-Typed -calculus
6 The recursion operator Y
7 Decidability of the Selection Problem
8 Conclusions and Perspectives
References
Complexity of Propositional Independence and Inclusion Logic
1 Introduction
2 Preliminaries
2.1 Syntax and Semantics
2.2 Auxiliary Operators
2.3 Satisfiability, Validity, and Model Checking in Team Semantics
3 Complexity of Satisfiability and Validity
3.1 The Logics PL[c] and PL[]
3.2 The Logics PL[ c,] and PL[,]
4 Complexity of Model Checking
5 Conclusion
References
Modal Inclusion Logic: Being Lax is Simpler than Being Strict
1 Introduction
2 Preliminaries
3 Computational Complexity
3.1 Upper Bound for Lax Semantics
3.2 Lower Bound for Lax Semantics
3.3 Upper Bound for Strict Semantics
3.4 Lower Bound for Strict Semantics
4 Conclusion
References
Differential Bisimulation for a Markovian Process Algebra
1 Introduction
2 Preliminaries: FEPA
3 Differential Bisimulation and ODE Lumpability
4 Computing Differential Bisimilarity
5 Related Work
6 Conclusion
References
On the Hardness of Almost--Sure Termination
1 Introduction
2 Preliminaries
3 Probabilistic Programs
4 Expected Outcomes and Termination Probabilities
5 The Hardness of Computing Expected Outcomes
6 The Hardness of Deciding Probabilistic Termination
7 Conclusion
References
Graphs Identified by Logics with Counting
1 Introduction
2 Preliminaries
2.1 Relational Structures and Partially Oriented Graphs
3 Inversion
3.1 Inversion for Graphs
3.2 Inversion for Finite Relational Structures
4 Characterization of the Graphs Identified by C2
5 General Finite Structures
6 Higher Dimensions
References
Synchronizing Automata with Extremal Properties
1 Introduction
2 A Series with Quadratically Extendable Subsets
3 Relaxing the Extension Property
3.1 Image Extending Conjecture
3.2 Separating States
4 Slowly Synchronizing Automata on a Ternary Alphabet
References
Ratio and Weight Quantiles
1 Introduction
2 Theoretical Foundations
3 Ratio and Weight Decision Problems
4 Computing Ratio and Weight Quantiles
4.1 Weight Quantiles
4.2 Ratio Quantiles
5 Conclusions
References
Precise Upper and Lower Bounds for the Monotone Constraint Satisfaction Problem
1 Introduction
2 Preliminaries
2.1 Constraint Languages and Functions
2.2 Cores of Constraint Languages
2.3 The Monotone Constraint Satisfaction Problem
2.4 Closure Operators on Functions and Relations
2.5 Restricted Closure Operators on Functions and Relations
3 The Complexity of Monotone Constraint Satisfaction
3.1 Partial Endomorphisms and CV-reductions
3.2 Intervals of Strong Partial Endomorphism Monoids
4 Upper and Lower Bounds for the Complexity of Monotone Constraint Satisfaction
5 Concluding Remarks
References
Definability by Weakly Deterministic Regular Expressions with Counters is Decidable
1 Introduction
2 Preliminaries
3 Normal Form
4 Looping Subexpression
5 Non-Looping Subexpression
6 Iterators
7 Upper Bounds for Counters
8 Upper Bound
9 Lower Bound
10 Conclusion
References
On the Complexity of Reconfiguration in Systems with Legacy Components
1 Introduction
2 Formalising the Reconfiguration Problem
3 Solving the Reconfiguration Problem
4 The Reconfiguration Problem Is PSpace-hard
5 Related Work and Conclusions
References
Eliminating Recursion from Monadic Datalog Programs on Trees
1 Introduction
2 Preliminaries
3 Equivalence
4 Boundedness
5 Boundedness vs Equivalence
6 Conclusions
References
Computability on the Countable Ordinals and the Hausdorff-Kuratowski Theorem (Extended Abstract)
1 Introduction
1.1 Represented Spaces
1.2 Weihrauch Reducibility
2 Representations of the Space of Countable Ordinals
3 Computability on COrd
4 Computability on COrdK
5 COrdM and Boundedness
6 Computability on COrdHL
7 A Non-deceiving Representation of COrd?
8 The Computable Hausdorff-Kuratowski Theorem
References
Emergence on Decreasing Sandpile Models
1 Introduction
2 Static Study of the Fixed Points
3 Dynamic Study of the Fixed Points
4 Conclusions and Perspectives
References
Lost in Self-Stabilization
1 Introduction
1.1 The Result
1.2 Contexts
2 The Model
2.1 Configurations and Associated Words
2.2 Local Transition Rules
3 The Specific Transition Rule
4 Analysis
4.1 Results
5 Conclusion and Open Questions
References
Equations and Coequations for Weighted Automata
1 Introduction
2 Preliminaries
3 Free and Cofree Construction for Weighted Automata
4 Duality Between Equations and Coequations
5 Linear Equations and Coequations
6 Conclusion
References
Author Index

System requirements

Save as PDF Copy link into clipboard

Schweitzer Fachinformationen

Mathematical Foundations of Computer Science 2015

Description

More details

Other editions

Additional editions

Content

System requirements