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

Page view(s)

52
checked on May 27, 2022

Download(s)

94
checked on May 27, 2022

Google ScholarTM

Check

Altmetric


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