{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T10:12:01Z","timestamp":1648894321691},"reference-count":9,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2008,8]]},"abstract":"<jats:p> 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 NC<jats:sup>i<\/jats:sup>. 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\u2013bounded complexity hierarchy based on channel complexity, lying between P and PSPACE which seems to be incomparable to the standard polynomial\u2013time alternating hierarchy. <\/jats:p>","DOI":"10.1142\/s0129054108006029","type":"journal-article","created":{"date-parts":[[2008,8,6]],"date-time":"2008-08-06T06:30:40Z","timestamp":1218004240000},"page":"887-913","source":"Crossref","is-referenced-by-count":0,"title":["WIRELESS MOBILE COMPUTING AND ITS LINKS TO DESCRIPTIVE COMPLEXITY"],"prefix":"10.1142","volume":"19","author":[{"given":"JI\u0158\u00cd","family":"WIEDERMANN","sequence":"first","affiliation":[{"name":"Institute of Computer Science, Academy of Sciences of the Czech Republic, Pod Vod\u00e1renskou v\u011b\u017e\u00ed 2, 182 07 Prague 8, Czech Republic"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"DANA","family":"PARDUBSK\u00c1","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Comenius University, Mlynsk\u00e1 dolina, 842 48 Bratislava, Slovakia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1145\/322234.322243"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00033-9"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(91)90098-H"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"rf5","unstructured":"R.\u00a0Karp and V.\u00a0Ramachandran, Handbook of Theoretical Computer Science\u00a0A, ed. J.\u00a0van Leeuwen (Elsevier Science Publishers, Amsterdam, 1990)\u00a0pp. 870\u2013941."},{"key":"rf6","doi-asserted-by":"crossref","unstructured":"P.\u00a0van Emde Boas, Handbook of Theoretical Computer Science\u00a0A, ed. J.\u00a0van Leeuwen (Elsevier Science Publishers, Amsterdam, 1990)\u00a0pp. 1\u201366.","DOI":"10.1016\/B978-0-444-88071-0.50006-0"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03927-4"},{"key":"rf8","first-page":"499","volume":"25","author":"Wiedermann J.","journal-title":"Elektronische Informationsverarbeitung und Kybernetik"},{"key":"rf11","unstructured":"J.\u00a0Wiedermann and D.\u00a0Pardubsk\u00e1, New Computational Paradigms: Changing Conceptions of What Is Computable, eds. B.\u00a0Cooper, B.\u00a0L\u00f6we and A.\u00a0Sorbi (Springer-Verlag, New York, 2008)\u00a0p. 560."}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054108006029","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T11:23:55Z","timestamp":1565177035000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054108006029"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,8]]},"references-count":9,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2008,8]]}},"alternative-id":["10.1142\/S0129054108006029"],"URL":"https:\/\/doi.org\/10.1142\/s0129054108006029","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,8]]}}}