Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/11656| Title: | The navigational power of Web browsers | Authors: | Bielecki, M Hidders, Jan Paredaens, Jan SPIELMANN, Marc Tyszkiewicz, Jerzy VAN DEN BUSSCHE, Jan |
Issue Date: | 2012 | Publisher: | SPRINGER, 233 SPRING ST, NEW YORK, NY 10013 USA | Source: | THEORY OF COMPUTING SYSTEMS, 50(2), p. 213-240 | Abstract: | We investigate the computational capabilities of Web browsers, when equipped with a standard finite automaton. We observe that Web browsers are Turing-complete. We introduce the notion of a navigational problem, and investigate the complexity of solving Web queries and navigational problems by Web browsers, where complexity is measured by the number of clicks. | Notes: | A preliminary report of part of this research was presented at ICALP 2002. | Keywords: | Web browser - Computational completeness - Computational complexity - Expressive power - Navigational problem - Click complexity;web browser; computational completeness; computational complexity; expressive power; navigational problem; click complexity | Document URI: | http://hdl.handle.net/1942/11656 | ISSN: | 1432-4350 | e-ISSN: | 1433-0490 | DOI: | 10.1007/s00224-010-9294-3 | ISI #: | 000299090700001 | Rights: | © The Author(s) 2010. This article is published with open access at Springerlink.com | Category: | A1 | Type: | Journal Contribution | Validations: | ecoom 2013 |
| Appears in Collections: | Research publications |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| art%3A10.1007%2Fs00224-010-9294-3.pdf | Published version | 792.68 kB | Adobe PDF | View/Open |
Page view(s)
62
checked on Sep 7, 2022
Download(s)
112
checked on Sep 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.