![[Search]](/static/images/search.gif){kind=small}
![[A-Z Index]](/static/images/az.gif){kind=small}
![[Contact]](/static/images/contact.gif){kind=small}
![[University of Cambridge]](/static/images/identifier2.gif){kind=small}
![[Talks.cam]](/static/images/talkslogosmall.gif)
Tuesday 30 August 2011, 14:00-15:00
Parameterized Complexity of some Problems in Concurrency and Verification
- đ¤ Speaker: Praveen Manjunatha, The Institute of Mathematical Sciences, Chennai
- đ Date & Time: Tuesday 30 August 2011, 14:00 - 15:00
- đ Venue: Room FW11, Computer Laboratory, William Gates Building
Questions? Contact
Bjarki Holm
Abstract
This talk will be about applying graph theoretic parameterized complexity notions to some logical decision problems that arise in concurrency and verification. First, we associate a graph with modal logic formulas in Conjunctive Normal Form and give parameterized complexity results for the satisfiability problem with treewidth as parameter. Second, we associate a graph with Petri nets, which are popularly used to model concurrent systems. Again, we give parameterized complexity results for model checking Petri nets, using treewidth and other stronger parameters of the associated graph.
Series This talk is part of the Logic and Semantics Seminar (Computer Laboratory) series.
Included in Lists
- All Talks (aka the CURE list)
- bld31
- Cambridge talks
- Computing and Mathematics
- Department of Computer Science and Technology talks and seminars
- Interested Talks
- Logic and Semantics Seminar (Computer Laboratory)
- Martin's interesting talks
- Room FW11, Computer Laboratory, William Gates Building
- School of Technology
- tcw57âs list
- Trust & Technology Initiative - interesting events
- yk373's list
- yk449
Note: Ex-directory lists are not shown.