University of Cambridge > Talks.cam > Logic and Semantics Seminar (Computer Laboratory) > Parameterized Complexity of some Problems in Concurrency and Verification

Parameterized Complexity of some Problems in Concurrency and Verification

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Bjarki Holm.

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.

This talk is part of the Logic and Semantics Seminar (Computer Laboratory) series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2020 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity