Parameterized complexity of some problems in concurrency and verification
Loading...
Date
item.page.authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Formal methods for the analysis of concurrent systems are an active area of research. Many mathematical models like Petri nets, communicating automata, automata with auxiliary storage like counters and stacks, rewrite systems and process algebras have been proposed for modelling concurrent infinite state systems. Efficient algorithms for analysis and the power to express interesting properties of concurrent systems are conflicting goals in these models. Having too much expressiveness results in undesirability, so it is important to get an insight into what kind of restrictions will lead to good analysis algorithms while retaining some expressive power. Restrictions like reversal boundedness in counter automata, disallowing cycles in network of push-down systems etc. lead to decidability in the respective models. In this thesis, we propose to use th framework of parameterized complexity to study the effect of various restrictions on the complexity of problems related to some models and logics of concurrent systems. Parameterized complexity works by trying to find efficient algorithms for instances of hard problems where one can identify structure that helps in analysis. A numerical parameter is associated with problem instances and algorithms are designed whose time and/or memory requirement is a fast growing function of the parameter, but growing slowly in terms of the size of the instance. On instances where the parameter is small, such algorithms run e_ciently. Apart from providing efficient algorithms, parameterized complexity provides a mathematically rigorous way of studying finer structure of the models under analysis.In the first part of this thesis, we look at the effect of well known graph parameters tree width and path width on the parameterized complexity of satisfability of some logics used to specify properties of finite state concurrent systems.