Please use this identifier to cite or link to this item:
Title: Parameterized complexity of some problems in concurrency and verification
Researcher: Praveen, M
Guide(s): Lodaya, Kamal
Keywords: Petri Nets
Upload Date: 24-Sep-2012
University: Homi Bhabha National Institute
Completed Date: July, 2011
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.
Pagination: 116p.
Appears in Departments:Department of Mathematical Sciences

Files in This Item:
File Description SizeFormat 
01_title.pdfAttached File116.44 kBAdobe PDFView/Open
02_acknowledgements.pdf55.76 kBAdobe PDFView/Open
03_abstract.pdf64.04 kBAdobe PDFView/Open
04_contents.pdf132.51 kBAdobe PDFView/Open
05_chapter 1.pdf243.15 kBAdobe PDFView/Open
06_chapter 2.pdf450.66 kBAdobe PDFView/Open
07_chapter 3.pdf290.5 kBAdobe PDFView/Open
08_chapter 4.pdf421.14 kBAdobe PDFView/Open
09_chapter 5.pdf391.81 kBAdobe PDFView/Open
10_chapter 6.pdf422.06 kBAdobe PDFView/Open
11_chapter 7.pdf425.44 kBAdobe PDFView/Open
12_chapter 8.pdf206.31 kBAdobe PDFView/Open
13_bibliography.pdf126.37 kBAdobe PDFView/Open

Items in Shodhganga are protected by copyright, with all rights reserved, unless otherwise indicated.

Altmetric Badge: