Conjunctive Grammars and Synchronized Alternating Pushdown Automata

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


Duration: 1:12:22
220 views
5

Context-free languages combine expressiveness with polynomial parsing, making them very appealing for practical applications. In fact, they are possibly the most widely used class of languages in Computer Science. Thus, models of computation which slightly extend context-free models, without losing parsing efficiency, seem to have great potential for applications in fields such as Programming Languages, Formal Verification, Computational Linguistics, and Computational Biology, and are therefore of interest for theoretical research. Conjunctive Grammars are an example of such a model. Introduced in 2001, this grammar model extends Context-free Grammars by adding explicit intersection rules, while retaining polynomial parsing. We present a new automaton model, Synchronized Alternating Pushdown Automata (SAPDA), which is the first automaton counterpart shown for Conjunctive Grammars. The SAPDA model is a variation on Alternating Pushdown Automata which uses a limited form of synchronization to create localized parallel computations. In this talk, I will present both Conjunctive Grammars and Synchronized Alternating Pushdown Automata, discuss the relationship between them, and show some interesting examples of languages that they can accept. Joint work with Michael Kaminski.



Other Videos By Microsoft Research


2016-09-07Touch , Tabletop, and Tangible Blocks
2016-09-07Connected: The Surprising Power of Our Social Networks and How They Shape our Lives
2016-09-07Control Theory and Computing: An unconsummated union
2016-09-07Particle Packing Problems for Fun and Profit
2016-09-07Position-based Cryptography [1/2]
2016-09-07Improving diagramming software usability with automatic routing and placement tools
2016-09-07Enhancing Cloud SLA with Security: A secure, Searchable, and Practical Cloud Storage System
2016-09-07Contracting with Asymmetric Externalities
2016-09-07Elections and Strategic Voting: Condorcet and Borda
2016-09-07Building Systems That Enforce Measurable Security Goals
2016-09-07Conjunctive Grammars and Synchronized Alternating Pushdown Automata
2016-09-07Borrowing Brilliance: The Six Steps to Business Innovation by Building on the Ideas of Others
2016-09-07Automated reasoning in non-classical logics with the polarized inverse method
2016-09-07Where computer vision needs help from computer science
2016-09-07Parallel Programming with Chorus
2016-09-07Seeing Software
2016-09-07Efficient and Effective File Replication and Consistency Maintenance in P2P Systems
2016-09-07Where to Go: Interpreting Natural Directions Using Global Inference
2016-09-07Algorithms Meet Art, Puzzles, and Magic
2016-09-07Free: The Future of a Radical Price
2016-09-07Provably-Efficient Adaptive Scheduling with Parallelism Feedback


Tags:
microsoft research