The Navigational Power of Web Browsers
Michał Bielecki, Jan Hidders, Jan Paredaens, Marc Spielmann, Jerzy Tyszkiewicz, Jan Van den Bussche · Theory of Computing Systems · 2010
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.