Automata, Languages and Programming

Probe Model
- Concurrency
- Axiomatizations for Probabilistic Bisimulation
- Noninterference for Concurrent Programs
- Distributed Controller Synthesis for Local Specifications
- A Distributed Abstract Machine for Safe Ambients
- Towards Quantitative Verification of Probabilistic Transition Systems
- Efficient Datastructures
- Efficient Generation of Plane Triangulations without Repetitions
- The Longest Common Subsequence Problem for Sequences with Nested Arc Annotations
- Visibility-Based Pursuit-Evasion in a Polygonal Region by a Searcher
- A New Method for Balancing Binary Search Trees
- Graph Algorithms
- Permutation Editing and Matching via Embeddings
- Testing Hypergraph Coloring
- Total Colorings of Degenerated Graphs
- Decidable Properties of Graphs of All-Optical Networks
- Majority Consensus and the Local Majority Rule
- Language Theory, Codes, and Automata
- Solvability of Equations in Free Partially Commutative Groups Is decidable
- Rational Transformations of Formal Power Series
- Combinatorics of Three-Interval Exchanges
- Decision Questions Concerning Semilinearity, Morphisms, and Commutation of Languages
- The Star Problem in Trace Monoids: Reductions Beyond C4
- The Trace Coding Problem Is Undecidable
- Combinatorics of Periods in Strings
- Minimal Tail-Biting Trellises for Certain Cyclic Block Codes Are Easy to Construct
- Model Checking and Protocol Analysis
- Effective Lossy Queue Languages
- Model Checking of Unrestricted Hierarchical State Machines
- Symbolic Trace Analysis of Cryptographic Protocols
- Tree Automata with One Memory, Set Constraints, and Ping-Pong Protocols
- Fair Simulation Relations, Parity Games, and State Space Reduction for Büchi Automata
- Hypergraphs in Model Checking: Acyclicity and Hypertree-Width versus Clique-Width
- From Finite State Communication Protocols to High-Level Message Sequence Charts
- Networks and Routing
- Fractional Path Coloring with Applications to WDM Networks
- Performance Aspects of Distributed Caches Using TTL-Based Consistency
- Routing in Trees
- Online Packet Routing on Linear Arrays and Rings
- Faster Gossiping on Butterflies
- Reasoning and Verification
- Realizability and Verification of MSC Graphs
- Reasoning about Sequential and Branching Behaviours of Message Sequence Graphs
- A Set-Theoretic Framework for Assume-Guarantee Reasoning
- Foundations for Circular Compositional Reasoning
- Scheduling
- A PTAS for Minimizing Weighted Completion Time on Uniformly Related Machines
- The Buffer Minimization Problem for Multiprocessor Scheduling with Conflicts
- On Minimizing Average Weighted Completion Time of Multiprocessor Tasks with Release Dates
- On the Approximability of Average Completion Time Scheduling under Precedence Constraints
- Secure Computation
- Optimistic Asynchronous Multi-party Contract Signing with Reduced Number of Rounds
- Information-Theoretic Private Information Retrieval: A Unified Construction
- Secure Multiparty Computation of Approximations
- Secure Games with Polynomial Expressions
- Specification and Deduction
- On the Completeness of Arbitrary Selection Strategies for Paramodulation
- An Axiomatic Approach to Metareasoning on Nominal Algebras in HOAS
- Knuth-Bendix Constraint Solving Is NP-Complete
- Amalgamation in CASL via Enriched Signatures
- Structural Complexity
- Lower Bounds for the Weak Pigeonhole Principle Beyond Resolution
- Time and Space Bounds for Reversible Simulation
- Finite-State Dimension
- The Complexity of Computing the Size of an Interval
- Communication Gap for Finite Memory Devices
- Separating Quantum and Classical Learning