A Robust Theory of Series Parallel Graphs
summary
Defines synchronized series-parallel graphs (SSPG) as two-terminal DAGs with sequential and unordered parallel composition plus a synchronization edge, and gives automata that match them. Shows nondeterministic and deterministic acceptors are equally expressive and equivalent to MSO and the graded μ-calculus. Gives a determinization that maps n-state, k-counting machines to deterministic machines with 2^{n^2} states and kn counting complexity, proves tightness, and gives polynomial-time membership, emptiness, and inclusion procedures.
AI-written summary · about
chapters (12)
- 0:00Start
- 0:28Distributed Stream Processing
- 1:11Stream as a Linear Sequence
- 1:46Illustrative Example: Taxis
- 3:17Key Based Partitioning + Ordering
- 4:01Key Based Partitioning + Global Punctuation
- 4:43Guiding Questions
- 5:26Temporal Integrity Constraints
- 7:40SSPG Characteristics
- 10:05(Deterministic) SSPGA Definition
- 12:58Counting Complexity Example
- 17:47Summary
related talks
01h 05mGraph Algorithms in the MPC Model
30mScalable Graph-Parallel Inference Algorithms and Systems
20mThe Complexity of Infinite-Horizon General-Sum Stochastic Games
35mCommunicating Sequential Processes
18mSureDistrib: Verifying Almost-Sure Termination of Composite Asynchronous Byzantine(…)
20mSPORE: Combining Symmetry and Partial Order Reduction
28mReasoning about Distributed Reconfigurable Systems
13mSharding the State Machine: Automated Modular Reasoning for Complex Concurrent System