Please use this identifier to cite or link to this item:
http://hdl.handle.net/10603/4717
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.coverage.spatial | Mathematical Science | en_US |
dc.date.accessioned | 2012-09-17T11:03:16Z | - |
dc.date.available | 2012-09-17T11:03:16Z | - |
dc.date.issued | 2012-09-17 | - |
dc.identifier.uri | http://hdl.handle.net/10603/4717 | - |
dc.description.abstract | This thesis takes shape in the ongoing study of automata and logics for data words ? finite words labelled with elements from an infinite alphabet. The notion of data words is a natural way for modelling unboundedness arising in different areas of computation. The contribution of this thesis is two-fold, which we discuss briefly below. On the automata side, after introducing two known models ? Register automata and Data automata ? we formulate a model of computation for data words, namely Class Counting Automaton (CCA). CCA is a finite state automaton equipped with countably infinitely many counters where counters can be increased or reset. Decrement is not allowed to preserve decidability. We prove basic facts about this model and compare its expressive power with respect to the earlier models. It is shown that this automaton sits (roughly) in between register automata in terms of expressiveness and complexity of decision problems. We also study several extensions some of which subsume earlier models. In the second part we look at the two-variable logics (first-order logic restricted to two variable) on logical structures which correspond to data words, continuing the study initiated in [BDM+11]. First, it is shown that two-variable logic on structures with two linear orders and their successor relations is undecidable. Then we consider first-order structures with successors of two linear orders and show that finite satisfiability of two-variable logic is decidable on these structures. We use suitably defined automata for proving this result. Later, we generalize the above proof to the case of k-bounded ordered data words ? first-order structures with a linear successor and a total preorder with an additional restriction of kboundedness on the preorder ? and prove a similar result. A corollary of this result is that two-variable logic is decidable on structures with two successors and at most one order relation. The decidability results are sharpened by showing lower Bounds for decidable fragments. | en_US |
dc.format.extent | 136p. | en_US |
dc.language | English | en_US |
dc.relation | - | en_US |
dc.rights | university | en_US |
dc.title | Counter automata and classical logics for data words | en_US |
dc.title.alternative | - | en_US |
dc.creator.researcher | Amaldev, Manuel | en_US |
dc.subject.keyword | Petri nets | en_US |
dc.subject.keyword | Mathematical Science | en_US |
dc.description.note | Bibilography p.134-136 | en_US |
dc.contributor.guide | Ramanujam, R | en_US |
dc.publisher.place | Mumbai | en_US |
dc.publisher.university | Homi Bhabha National Institute | en_US |
dc.publisher.institution | Department of Mathematical Sciences | en_US |
dc.date.registered | n.d. | en_US |
dc.date.completed | October 2011 | en_US |
dc.date.awarded | 2011 | en_US |
dc.format.dimensions | - | en_US |
dc.format.accompanyingmaterial | None | en_US |
dc.type.degree | Ph.D. | en_US |
dc.source.inflibnet | INFLIBNET | en_US |
Appears in Departments: | Department of Mathematical Sciences |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
01_title.pdf | Attached File | 214.65 kB | Adobe PDF | View/Open |
02_certificate.pdf | 78.72 kB | Adobe PDF | View/Open | |
03_acknowledgements.pdf | 54.64 kB | Adobe PDF | View/Open | |
04_abstract.pdf | 112.86 kB | Adobe PDF | View/Open | |
05_contents.pdf | 188.14 kB | Adobe PDF | View/Open | |
06_list of figures.pdf | 204.39 kB | Adobe PDF | View/Open | |
07_chapter 1.pdf | 287.67 kB | Adobe PDF | View/Open | |
08_chapter 2.pdf | 340.96 kB | Adobe PDF | View/Open | |
09_chapter 3.pdf | 418.45 kB | Adobe PDF | View/Open | |
10_chapter 4.pdf | 495 kB | Adobe PDF | View/Open | |
11_chapter 5.pdf | 362.64 kB | Adobe PDF | View/Open | |
12_chapter 6.pdf | 510.35 kB | Adobe PDF | View/Open | |
13_chapter 7.pdf | 483.5 kB | Adobe PDF | View/Open | |
14_chapter 8.pdf | 240.93 kB | Adobe PDF | View/Open | |
15_bibliography.pdf | 129.12 kB | Adobe PDF | View/Open |
Items in Shodhganga are licensed under Creative Commons Licence Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0).
Altmetric Badge: