Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/14816
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | TAN, Tony | - |
dc.date.accessioned | 2013-03-26T13:41:36Z | - |
dc.date.available | 2013-03-26T13:41:36Z | - |
dc.date.issued | 2013 | - |
dc.identifier.citation | ACM Transactions on Computational Logic, 14 (3), (Art. N° 19) | - |
dc.identifier.issn | 1529-3785 | - |
dc.identifier.uri | http://hdl.handle.net/1942/14816 | - |
dc.description.abstract | Let D denote an infinite alphabet – a set that consists of infinitely many symbols. A word w = a0b0a1b1 · · ·anbn of even length over D can be viewed as a directed graph Gw whose vertices are the symbols that appear in w, and the edges are (a0, b0), (a1, b1), . . . , (an, bn). For a positive integer m, define a language Rm such that a word w = a0b0 · · ·anbn ∈ Rm if and only if there is a path in the graph Gw of length ≤ m from the vertex a0 to the vertex bn. We establish the following hierarchy theorem for pebble automata over infinite alphabet. For every positive integer k, (i) there exists a k-pebble automaton that accepts the language R2k−1 ; (ii) there is no k-pebble automaton that accepts the language R2k+1−2 . Using this fact, we establish the following main results in this paper: (a) a strict hierarchy of the pebble automata languages based on the number of pebbles; (b) the separation of monadic second order logic from the pebble automata languages; (c) the separation of one-way deterministic register automata languages from pebble automata languages. | - |
dc.language.iso | en | - |
dc.subject.other | Pebble automata; graph reachability; infinite alphabets | - |
dc.title | Graph Reachability and Pebble Automata over Infinite Alphabets | - |
dc.type | Journal Contribution | - |
dc.identifier.issue | 3 | - |
dc.identifier.volume | 14 | - |
local.format.pages | 31 | - |
local.bibliographicCitation.jcat | A1 | - |
dc.description.notes | Reprint Address: Tan, T (reprint author) - Hasselt Univ, Diepenbeek, Belgium. E-mail Addresses:ptony.tan@gmail.com | - |
local.type.refereed | Refereed | - |
local.type.specified | Article | - |
local.bibliographicCitation.artnr | 19 | - |
dc.identifier.doi | 10.1145/2499937.2499940 | - |
dc.identifier.isi | 000323892900003 | - |
item.fullcitation | TAN, Tony (2013) Graph Reachability and Pebble Automata over Infinite Alphabets. In: ACM Transactions on Computational Logic, 14 (3), (Art. N° 19). | - |
item.validation | ecoom 2014 | - |
item.accessRights | Open Access | - |
item.fulltext | With Fulltext | - |
item.contributor | TAN, Tony | - |
crisitem.journal.issn | 1529-3785 | - |
crisitem.journal.eissn | 1557-945X | - |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
tan_graph.pdf | Published version | 326.74 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.