Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/14816
Title: | Graph Reachability and Pebble Automata over Infinite Alphabets | Authors: | TAN, Tony | Issue Date: | 2013 | Source: | ACM Transactions on Computational Logic, 14 (3), (Art. N° 19) | 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. | Notes: | Reprint Address: Tan, T (reprint author) - Hasselt Univ, Diepenbeek, Belgium. E-mail Addresses:ptony.tan@gmail.com | Keywords: | Pebble automata; graph reachability; infinite alphabets | Document URI: | http://hdl.handle.net/1942/14816 | ISSN: | 1529-3785 | e-ISSN: | 1557-945X | DOI: | 10.1145/2499937.2499940 | ISI #: | 000323892900003 | Category: | A1 | Type: | Journal Contribution | Validations: | ecoom 2014 |
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.