Search

We propose a model for multi-user data-driven communicating Web applications. An arbitrary number of users may access the application concurrently through Web sites and Web services. A Web service may have an arbitrary number of instances. The interaction between users and Web application is data-driven. Synchronous communication is done by shared access to the database and global application state. Private information may be stored in a local state. Asynchronous communication is done by message passing. A version of first-order linear time temporal logic (LTL-FO) is proposed to express behavioral properties of Web applications. The model is used to formally specify a significant fragment of an e-business application. Some of its desirable properties are expressed as LTL-FO formulas. We study a decision problem, namely whether the model satisfies an LTL-FO formula. We show the undecidability of the unrestricted verification problem and discuss some restrictions that ensure decidability. [ABSTRACT FROM AUTHOR]

A language L is prefix-convex if, whenever words u and w are in L with u a prefix of w, then every word v which has u as a prefix and is a prefix of w is also in L. Similarly, we define suffix-, factor-, and subword-convex languages, where by subword we mean subsequence. Together, these languages constitute the class of convex languages which contains interesting subclasses, such as ideals, closed languages (including factorial languages) and free languages (including prefix-, suffix-, and infix-codes, and hypercodes). There are several advantages of studying the class of convex languages and its subclasses together. These classes are all definable by binary relations, in fact, by partial orders. Closure properties of convex languages have been studied in this general framework of binary relations. The problems of deciding whether a language is convex of a particular type have been analyzed together, and have been solved by similar methods. The state complexities of regular operations in subclasses of convex languages have been examined together, with considerable economies of effort. This paper surveys the recent results on convex languages with an emphasis on complexity issues. [ABSTRACT FROM AUTHOR]

Overview Modern symbolic logic, including axiomatic set theory, developed out of the works of Boole, Peirce, Cantor, and Frege in the nineteenth century. The contours of the subject as it is known today, however, were largely established in the decade between 1928 and 1938. During those years the scope of the discipline was expanded, both through clarification of the distinction between syntax and semantics and through recognition of different logical systems, in contrast to the conception of logic as a universal system within which all reasoning must be carried out. At the same time the primary focus of logical investigation was narrowed to the study of first-order logic (then called the ‘restricted functional calculus’), in which quantification is allowed only over the elements of an underlying structure, not over subsets thereof. The former development made possible the formulation and resolution of metasystematic questions, such as the consistency or completeness of axiomatic theories, while the latte, by isolating a more tractable logical framework, facilitated the derivation of theorems. Both developments led to the study of model-theoretic issues, such as the compactness of logical systems and the existence of non-isomorphic models of arithmetic and set theory. In addition, questions concerning definability and decidability by axiomatic or algorithmic means were given precise mathematical formulations through the definition of the class of recursive functions and the enunciation of Church's Thesis (that the recursive functions are exactly those intuitively characterised as being effectively computable). Formal proofs of indefinability and undecidability theorems thereby became possible, with profound implications for Hilbert's proof theory and for the subsequent development of computer science. [ABSTRACT FROM AUTHOR]