descriptionPublicationkeyboard_double_arrow_right Article 05 Oct 2010 English Publisher:Springer Science and Business Media LLCJournal:Theory of Computing Systems, volume 50, pages 213-240 (issn: 1432-4350, eissn: 1433-0490,

Authors: Bielecki, M. (author); Hidders, J. (author); Paredaens, J. (author); Spielmann, M. (author); Tyszkiewicz, J. (author); Van den Bussche, J. (author);

doi: 10.1007/s00224-010-9294-3

handle: 10067/962200151162165141 , 1942/11656

The Navigational Power of Web Browsers

- Summary
- Subjects
- Metrics

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.

Related Organizations

Delft University of Technology
Netherlands
Transnational University Limburg
Belgium
Hasselt University
Belgium
University of Warsaw
Poland
University of Antwerp
Belgium

Keywords

Computer. Automation, Navigational problem, Web browser - Computational completeness - Computational complexity - Expressive power - Navigational problem - Click complexity, Computational completeness, web browser; computational completeness; computational complexity; expressive power; navigational problem; click complexity, Expressive power, Web browser, Theoretical Computer Science, Computational complexity, Click complexity, Computational Theory and Mathematics, Mathematics

Impact byBIP!

	citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	0
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average