Counter automata and classical logics for data words (Record no. 48847)
[ view plain ]
000 -LEADER | |
---|---|
fixed length control field | 02520nam a2200253Ia 4500 |
008 - FIXED-LENGTH DATA ELEMENTS--GENERAL INFORMATION | |
fixed length control field | 160627s2012||||xx |||||||||||||| ||und|| |
080 ## - UNIVERSAL DECIMAL CLASSIFICATION NUMBER | |
Universal Decimal Classification number | HBNI TH 42 |
100 ## - MAIN ENTRY--AUTHOR NAME | |
Personal name | Amaldev Manuel |
Relator term | author |
245 ## - TITLE STATEMENT | |
Title | Counter automata and classical logics for data words |
260 ## - PUBLICATION, DISTRIBUTION, ETC. (IMPRINT) | |
Year of publication | 2012 |
300 ## - PHYSICAL DESCRIPTION | |
Number of Pages | 136p. |
502 ## - DISSERTATION NOTE | |
Dissertation note | 2012 |
502 ## - DISSERTATION NOTE | |
Degree Type | Ph.D |
502 ## - DISSERTATION NOTE | |
Name of granting institution | HBNI |
520 3# - SUMMARY, ETC. | |
Summary, etc | 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 is briefly discussed here. On the automata side, after introducing two known models - Register automata and Data automata, a model of computation for data words is formulated viz., CCA(Class counting Automata). CCA is a finite state automaton equipped with countably infintely many counters where counters can be increased or reset. Decrement is not allowed to preserve decidability. The basic facts about this model is proved and its expressive power is compared with respect to the earlier models. It is shown that this automaton sits roughly in between register automata interms of expressiveness and complexity of decision problems. The author also studies several extensions some of which subsume earlier models. The second part, looks 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 considered, first-order structures with successors of two linear orders and proved that finite satisfiability of two-variable logic is decidable on these structures. Suitably defined automata is used for proving this result. Later, the above proof is generalised 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 k-boundedness on the preorder – and proved a similar result. |
650 14 - SUBJECT ADDED ENTRY--TOPICAL TERM | |
Topical Term | Computer Science |
653 10 - INDEX TERM--UNCONTROLLED | |
Uncontrolled term | Automata Theory |
653 10 - INDEX TERM--UNCONTROLLED | |
Uncontrolled term | HBNI Th 42 |
653 10 - INDEX TERM--UNCONTROLLED | |
Uncontrolled term | Logics |
720 1# - ADDED ENTRY--UNCONTROLLED NAME | |
Thesis Advisor | Ramanujam, R. |
Relator term | Thesis advisor [ths] |
856 ## - ELECTRONIC LOCATION AND ACCESS | |
Uniform Resource Identifier | http://www.imsc.res.in/xmlui/handle/123456789/316 |
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 TH 42 | 67178 | http://www.imsc.res.in/xmlui/handle/123456789/316 | THESIS & DISSERTATION |