Regular quantifiers in Logics (Record no. 48862)
[ view plain ]
| 000 -LEADER | |
|---|---|
| fixed length control field | 02775nam a2200265Ia 4500 |
| 008 - FIXED-LENGTH DATA ELEMENTS--GENERAL INFORMATION | |
| fixed length control field | 160627s2013||||xx |||||||||||||| ||und|| |
| 080 ## - UNIVERSAL DECIMAL CLASSIFICATION NUMBER | |
| Universal Decimal Classification number | HBNI Th64 |
| 100 ## - MAIN ENTRY--AUTHOR NAME | |
| Personal name | Sreejith, A.V. |
| Relator term | author |
| 245 ## - TITLE STATEMENT | |
| Title | Regular quantifiers in Logics |
| 260 ## - PUBLICATION, DISTRIBUTION, ETC. (IMPRINT) | |
| Year of publication | 2013 |
| 300 ## - PHYSICAL DESCRIPTION | |
| Number of Pages | 130p. |
| 502 ## - DISSERTATION NOTE | |
| Dissertation note | 2013 |
| 502 ## - DISSERTATION NOTE | |
| Degree Type | Ph.D |
| 502 ## - DISSERTATION NOTE | |
| Name of granting institution | HBNI |
| 520 3# - SUMMARY, ETC. | |
| Summary, etc | In this thesis, we study logic on words extended with regular quantifiers. Modulo counting quantifiers are one particular example of such quantifiers, which have been well studied in the past. These quantifiers can be generalized to group quantifiers and further to monoid quantifiers all being regular quantifiers. The logics we extend can be classified into two parts. In the first part, we look at logics which define regular languages like FO[<] and linear temporal logic (LTL). We extend these logics with the above mentioned regular quantifiers. In the second part, we look at regular quantifiers over a linear order and an addition function which respects the linear order. In the first part of our work, we show that LTL extended with modulo counting/ group operators (LTLgrp) and FO[<] extended with modulo counting/group quantifiers (FOgrp[<]), both accept the same set of languages. We then go on to show that the satisfiability and model checking for LTLgrp is PSPACE-complete. We also look at satisfiability of various fragments of this logic. Then we show that the two variable fragment of FOgrp[<] is EXPSPACE-complete. We also analyse certain important sublogics. In the second part of our work, we study first order logic with a linear order and the arithmetic predicate, +. We first show that the two variable fragment of FOmod[<,+] is undecidable. Then we show that over a unary alphabet satisfiability of FOmod[<,+] is 2EXPSPACE. Finally we investigate the expressive power of M[<,+], where M is a set of monoid quantifiers. We show, using the concept of a neutral letter [BIL+05], that the class of neutral letter languages definable in M[<,+] is equivalent to those definable in M[<]. Using the above claim, we are able to show that the logics M1[<,+] is different from M2[<,+], if the set of monoid quantifiers M1 and M2 are different. This lets us answer a conjecture of Roy and Straubing [RS07] that FO[<,+] and mod[<,+] are incomparable. We also show that given a regular language L, it is decidable whether L is definable in mod[<,+] or not. |
| 650 14 - SUBJECT ADDED ENTRY--TOPICAL TERM | |
| Topical Term | Computer Science |
| 653 10 - INDEX TERM--UNCONTROLLED | |
| Uncontrolled term | First Order Logic |
| 653 10 - INDEX TERM--UNCONTROLLED | |
| Uncontrolled term | HBNI Th64 |
| 653 10 - INDEX TERM--UNCONTROLLED | |
| Uncontrolled term | Linear Temporal Logic |
| 653 10 - INDEX TERM--UNCONTROLLED | |
| Uncontrolled term | Logics |
| 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/350 |
| 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 Th64 | 69861 | http://www.imsc.res.in/xmlui/handle/123456789/350 | THESIS & DISSERTATION |