The Navigational Power of Web Browsers

Journal article (2010)
Department
Software Technology (EEMCS) (TU Delft)
Copyright: © 2010 The Author(s). This article is published with open access at Springerlink.com
DOI: https://doi.org/doi:10.1007/s00224-010-9294-3
More Info
expand_more

Published Date

05-10-2010

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Source:

Theory of Computing Systems, 50(2)2012

Faculty

Electrical Engineering, Mathematics and Computer Science

Department

Software Technology

Abstract

We investigate the computational capabilities of Web browsers, when equipped with a standard finite automaton. We observe that Web browsers are Turingcomplete. 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.

Files

Bielecki2010.pdf
(pdf | 0.573 Mb)