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 SizeFormat 
art%3A10.1007%2Fs00224-010-9294-3.pdfPublished version792.68 kBAdobe PDFView/Open
Show full item record

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.