Multi-stack automata reachability: A New Tractable Subclass

Channel:
Microsoft Research
Subscribers:
344,000
Published on ● Video Link: https://www.youtube.com/watch?v=SHFt4gJcTP0


Duration: 1:00:53
291 views
3

Abstracted concurrent programs with recursion are best viewed as multi-stack automata. Reachability of multi-stack automata is undecidable, and several approaches to handle restricted reachability have been developed (e.g. bounded context-switching reachability is decidable).   Building on work on visibly pushdown automata, we define a new powerful class of multi-stack automata that have a decidable reachability problem. We show that if automata are restricted so that they work in at most k phases, where in each phase only one stack can be popped (push transitions on all stacks are always permitted), then the reachability problem is decidable. In fact, we obtain a robust tractable subclass of context-sensitive languages, closed under all boolean operations and with decidable emptiness and inclusion.   Finally, we consider infinite automata (not to be confused with automata on infinite words), which are automata with an infinite number of states and transitions defined using stack automata as above. We show a surprising result that these automata precisely capture the complexity class 2ETIME.



Other Videos By Microsoft Research


2016-09-06Persuasive Games: The Expressive Power of Videogames           
2016-09-06In-Network, Physical Adaptation of Sensor Networks
2016-09-06Secure Virtual Architecture: A Novel Foundation for Operating System Security
2016-09-06Engineering Performance Using Control Theory: A One Day How-To: Theory Part 2
2016-09-06Effective Scientific Data Management through Provenance Collection
2016-09-06Unified Dimensionality Reduction: Formulation, Solution and Beyond
2016-09-06Engineering Performance Using Control Theory: A How-To: Control Analysis & Real world applications
2016-09-06A Real-World Test-bed for Mobile Adhoc Networks: Methodology, Experimentations, Simulation & Results
2016-09-06Fusion of Optical and Radio Frequency Techniques: Cameras, Projectors and Wireless Tags
2016-09-06Hierarchical Phrase-Based Translation with Suffix Arrays.
2016-09-06Multi-stack automata reachability: A New Tractable Subclass
2016-09-06Seduced by Success: How the Best Companies Survive the 9 Traps of Winning          
2016-09-06Everything is Miscellaneous: The Power of the New Digital Disorder
2016-09-06Accelerating High Performance Computing Applications with Reconfigurable Logic
2016-09-06Cooperative Data and Computation Partitioning for Distributed Architectures
2016-09-06Rate Control Protocol (RCP): Congestion Control to Make Flows Complete Quickly
2016-09-06Engineering Performance Using Control Theory: A One Day How-To: Introduction & Theory Part 1
2016-09-06Paths Beyond Local Search: A Tight Bound for Randomized Fixed-Point Computation
2016-09-06Interaction Design for One-Handed Use of Mobile Devices
2016-09-06Einstein: His Life and Universe
2016-09-06Virtual Reality Therapy: Using immersive virtual reality games to help reduce suffering


Tags:
microsoft research