COMPLEXITY RESULTS FOR 2-WAY AND MULTI-PEBBLE AUTOMATA AND THEIR LOGICS

Authors
GLOBERMAN N HAREL D
Citation
N. Globerman et D. Harel, COMPLEXITY RESULTS FOR 2-WAY AND MULTI-PEBBLE AUTOMATA AND THEIR LOGICS, Theoretical computer science, 169(2), 1996, pp. 161-184
Citations number
22
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
Journal title
Theoretical computer science → ACNP
ISSN journal
03043975
Volume
169
Issue
2
Year of publication
1996
Pages
161 - 184
Database
ISI
SICI code
0304-3975(1996)169:2<161:CRF2AM>2.0.ZU;2-J
Abstract
Two-way and multi-pebble automata are considered (the latter appropria tely restricted to accept only regular languages), and enriched with a dditional features, such as nondeterminism and concurrency. We investi gate the succinctness of such machines, and the extent to which this s uccinctness carries over to make the reasoning problem in propositiona l dynamic logic more difficult. The two main results establish that ea ch additional pebble provides inherent exponential power on both front s.