
Mathematical Foundations of Computer Science 2015
Description
Alles über E-Books | Antworten auf Fragen rund um E-Books, Kopierschutz und Dateiformate finden Sie in unserem Info- & Hilfebereich.
More details
Other editions
Additional 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
File format: PDF
Copy protection: Watermark-DRM (Digital Rights Management)
System requirements:
- Computer (Windows; MacOS X; Linux): Use the free software Adobe Reader, Adobe Digital Editions, or any other PDF viewer of your choice (see eBook Help).
- Tablet/Smartphone (Android; iOS): Install the free app Adobe Digital Editions or another reading app for eBooks, e.g., PocketBook (see eBook Help).
- E-reader: Bookeen, Kobo, Pocketbook, Sony, Tolino and many more (only limited: Kindle).
The file format PDF always displays a book page identically on any hardware. This makes PDF suitable for complex layouts such as those used in textbooks and reference books (images, tables, columns, footnotes). Unfortunately, on the small screens of e-readers or smartphones, PDFs are rather annoying, requiring too much scrolling.
This eBook uses Watermark-DRM, a „soft” copy protection. This means that there are no technical restrictions to prevent illegal distribution. However, there is a personalised watermark embedded in the eBook that can be used to identify the purchaser of the eBook in the event of misuse and to provide evidence for legal purposes.
For more information, see our eBook Help page.