WIRELESS MOBILE COMPUTING AND ITS LINKS TO DESCRIPTIVE COMPLEXITY

The Wireless Parallel Turing Machine (WPTM) is a new computational model recently introduced and studied by the authors. Its design captures important features of wireless mobile computing. In this paper we survey some results related to the descriptive complexity aspects of the new model. In partic...

Full description

Saved in:
Bibliographic Details
Published in:International journal of foundations of computer science 2008-08, Vol.19 (4), p.887-913
Main Authors: WIEDERMANN, JIŘÍ, PARDUBSKÁ, DANA
Format: Article
Language:English
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The Wireless Parallel Turing Machine (WPTM) is a new computational model recently introduced and studied by the authors. Its design captures important features of wireless mobile computing. In this paper we survey some results related to the descriptive complexity aspects of the new model. In particular, we show a tight relationship about (a) wireless parallel computing, (b) alternating, and (c) synchronized alternating Turing machines. This relationship opens, e.g., the road to circuit complexity by offering an elegant WPTM characterization of bounded-fan-in uniform circuit families, such as NC and NCi. The structural properties of computational graphs of WPTM computations inspire definitions of new complexity measures capturing important aspects of wireless computations: energy consumption and the number of broadcasting channels used during computation. These measures do not seem to have direct counterparts in alternating computations. We mention results related to these new structural measures, e.g., a polynomial time–bounded complexity hierarchy based on channel complexity, lying between P and PSPACE which seems to be incomparable to the standard polynomial–time alternating hierarchy.
ISSN:0129-0541
1793-6373
DOI:10.1142/S0129054108006029