Spreadsheets are among the most commonly used applications for data management and analysis. They combine data processing with very diverse supplementary features: statistics, visualization, reporting, linear programming solvers, Web queries periodically downloading data from external sources, etc. However, the spreadsheet paradigm of computation still lacks sufficient analysis. In this article, we demonstrate that a spreadsheet can implement all data transformations definable in SQL, merely by utilizing spreadsheet formulas. We provide a query compiler, which translates any given SQL query into a worksheet of the same semantics, including NULL values. Thereby, database operations become available to the users who do not want to migrate to a database. They can define their queries using a high-level language and then get their execution plans in a plain vanilla spreadsheet. The functions available in spreadsheets impose limitations on the algorithms one can implement. In this paper, we offer O(n log2n) sorting spreadsheet, using a non-constant number of rows, and, surprisingly, Depth-First-Search and Breadth-First-Search on graphs.

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.

MOTIVATION: Taverna workbench is an environment for construction, visualization and execution of bioinformatic workflows that integrates specialized tools available on the Internet. It already supports major bioinformatics services and is constantly gaining popularity. However, its user interface requires considerable effort to learn, and sometimes requires programming or scripting experience from its users. We have integrated Taverna with OpenOffice Calc, making the functions of the scientific workflow system available in the spreadsheet. In CalcTav, one can define workflows using the spreadsheet interface and analyze the results using the spreadsheet toolset. RESULTS: Technically, CalcTav is a plugin for OpenOffice Calc, which provides the functionality of Taverna available in the form of spreadsheet functions. Even basic familiarity with spreadsheets already suffices to define and use spreadsheet workflows with Taverna services. The data processed by the Taverna components is automatically transferred to and from spreadsheet cells, so all the visualization and data analysis tools of OpenOffice Calc are available to the workflow creator within one, consistent user interface. AVAILABILITY: CalcTav is available under GPLv2 from http://code.google.com/p/calctav/ CONTACT: [email protected].

Spreadsheets are among the most commonly used applications for data management and analysis. Perhaps they are even among the most widely used computer applications of all kinds. However, the spreadsheet paradigm of computation still lacks sufficient analysis.

This paper contains the English version of my Master's thesis [6] written about 22 years ago under supervision of Jerzy Tiuryn. Its main result is the proof of PTIME-completeness of the type reconstruction problem for simply typed lambda calculus. Ab

UNLABELLED: Taverna workbench is an environment for construction, visualization and execution of bioinformatic workflows that integrate specialized tools available through the internet. It is gaining popularity fast, because of supporting the most important bioinformatic services and its simple, yet robust graphical notation. Here we present XQTav-an extension of Taverna that provides full integration with XQuery (the query language for XML) engine. XQTav allows execution of XQuery scripts in Taverna workflow diagrams. All existing Taverna processors can be accessed in the XQuery scripts. This provides an alternative way of specifying subworkflows in Taverna and is useful when one deals with query-like algorithms (e.g. filters and inner joins). Moreover, XQtav may be used to automatically generate an XQuery script that is equivalent to Taverna's workflow. This constitutes another way of creating and enacting bioinformatic workflows: overall structure of a diagram is drawn in Taverna environment, XQuery code is generated and possibly adjusted by hand. It can be executed by XQuery engines or incorporated into other software environments. AVAILABILITY: XQtav is an open source software. It may be downloaded from http://xqtav.sourceforge.net/. The page also contains various tutorials and examples, including the one described in this report.

We introduce and investigate a distributed computation model for querying the Web. Web queries are computed by interacting automata running at different nodes in the Web. The automata which we are concerned with can be viewed as register automata equipped with an additional communication component. We identify conditions necessary and sufficient for systems of automata to compute Web queries, and investigate the computational power of such systems.

We consider two kinds of reflective relational machines: the usual ones, which use first order queries, and existential reflective machines, which use only first order existential queries. We compare these two computation models. We build on already existing results for standard relational machines, obtained by Abiteboul, Pa-padimitriou and Vianu [2], so we prove only results for existential machines. First we show that for both standard and existential reflective machines the set of polynomial time computable Boolean queries consists precisely of all 𝒫𝒮𝒫𝒜𝒞ℰ computable queries. Then we go further and compare which classes of algorithms both kinds of machines represent. Unless 𝒫𝒮𝒫𝒜𝒞ℰ = 𝒫 𝒩𝒫 , there are 𝒫𝒮𝒫𝒜𝒞ℰ queries which cannot be computed by polynomial time existential reflective machines which use only polynomial amount of relational memory, while it is possible for standard reflective machines. We conclude that existential reflective machines, being equivalent in computational power to unrestricted machines, implement substantially worse algorithms than the latter. Concerning deciding 𝒫 classes of structures, every fixpoint query can be evaluated by a polynomial time unrestricted reflective machine using constant number of variables, while existential reflective machines need [n/2] variables to implement the graph connectivity query. So again the algorithms represented by existential reflective machines are worse. Finally, for each k we get a characterization of the Δ k+1 p level in the polynomial time hierarchy in terms of reflective relational machines which use either Π k 0 or Σ k p queries.

Let L/sub /spl infin//spl omega///sup /spl omega// be the infinitary language obtained from the first-order language of graphs by closure under conjunctions and disjunctions of arbitrary sets of formulas, provided only finitely many distinct variables occur among the formulas. Let p(n) be the edge probability of the random graph on n vertices. Previous articles have shown that when p(n) is constant or p(n)=n/sup -/spl alpha// and /spl alpha/>1, then every sentence in L/sub /spl infin//spl omega///sup /spl omega// has probability that converges as n gets large; however, when p(n)=n/sup -/spl alpha// and /spl alpha/<1 is rational, then there are first-order sentences whose probability does not converge. This article completes the picture for L/sub /spl infin//spl omega///sup /spl omega// and random graphs with edge probability of the form n/sup -/spl alpha//. It is shown that if /spl alpha/ is irrational, then every sentence in L/sub /spl infin//spl omega///sup /spl omega// has probability that converges to 0 or 1. It is also shown that if /spl alpha/=1, then there are sentences an the deterministic transitive closure logic (and therefore in L/sub /spl infin//spl omega///sup /spl omega//), whose probability does not converge.