Parameterized complexity of some problems in concurrency and verification (Record no. 48861)
[ view plain ]
| 000 -LEADER | |
|---|---|
| fixed length control field | 03082nam a2200277Ia 4500 |
| 008 - FIXED-LENGTH DATA ELEMENTS--GENERAL INFORMATION | |
| fixed length control field | 160627s2011||||xx |||||||||||||| ||und|| |
| 080 ## - UNIVERSAL DECIMAL CLASSIFICATION NUMBER | |
| Universal Decimal Classification number | HBNI Th39 |
| 100 ## - MAIN ENTRY--AUTHOR NAME | |
| Personal name | Praveen, M. |
| Relator term | author |
| 245 ## - TITLE STATEMENT | |
| Title | Parameterized complexity of some problems in concurrency and verification |
| 260 ## - PUBLICATION, DISTRIBUTION, ETC. (IMPRINT) | |
| Year of publication | 2011 |
| 300 ## - PHYSICAL DESCRIPTION | |
| Number of Pages | 145p. |
| 502 ## - DISSERTATION NOTE | |
| Dissertation note | 2011 |
| 502 ## - DISSERTATION NOTE | |
| Degree Type | Ph.D |
| 502 ## - DISSERTATION NOTE | |
| Name of granting institution | HBNI |
| 520 3# - SUMMARY, ETC. | |
| Summary, etc | Formal methods for the analysis of concurrent systems is 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 undecidability, 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 the 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 efficiently. 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 treewidth and pathwidth on the parameterized complexity of satisfiability of some logics used to specify properties of finite state concurrent systems. This is followed by parameterized complexity of some problems associated with synchronized transition systems and 1-safe Petri nets, which are compactly represented finite state systems. In the second part of the thesis, we look at general Petri nets (which are infinite state) and study the parameterized complexity of coverability, boundedness and extensions of these problems with respect to two parameters. |
| 650 14 - SUBJECT ADDED ENTRY--TOPICAL TERM | |
| Topical Term | Computer Science |
| 653 10 - INDEX TERM--UNCONTROLLED | |
| Uncontrolled term | Concurrency |
| 653 10 - INDEX TERM--UNCONTROLLED | |
| Uncontrolled term | HBNI Th39 |
| 653 10 - INDEX TERM--UNCONTROLLED | |
| Uncontrolled term | Parameterizations |
| 653 10 - INDEX TERM--UNCONTROLLED | |
| Uncontrolled term | Parameterized Complexity |
| 653 10 - INDEX TERM--UNCONTROLLED | |
| Uncontrolled term | Verification |
| 720 1# - ADDED ENTRY--UNCONTROLLED NAME | |
| Thesis Advisor | Kamal Lodaya |
| Relator term | Thesis advisor [ths] |
| 856 ## - ELECTRONIC LOCATION AND ACCESS | |
| Uniform Resource Identifier | http://www.imsc.res.in/xmlui/handle/123456789/272 |
| 942 ## - ADDED ENTRY ELEMENTS (KOHA) | |
| Koha item type | THESIS & DISSERTATION |
| Withdrawn status | Lost status | Damaged status | Not for loan | Current library | Full call number | Accession Number | Uniform Resource Identifier | Koha item type |
|---|---|---|---|---|---|---|---|---|
| IMSc Library | HBNI Th39 | 66495 | http://www.imsc.res.in/xmlui/handle/123456789/272 | THESIS & DISSERTATION |