The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
A fundamental goal of biology is to understand how living cells work. Recent developments in biotechnology and information processing have revolutionized this research field. Computational biology is a major component of this revolution and a fertile source of interesting problems related to algorithm design, combinatorics, statistics, combinatorial optimization, pattern recognition, data mining and...
Game-theoretic ideas have been used to model a wide range of computational notions over the past few years. This has led to some striking results of a foundational character, relating in porticular to definability and full abstraction. The first applications of these ideas, to program analysis and verification, have also begun to appear. We shall give an overview of what has been achieved, and try...
It was previously known that Max Clique cannot be approximated in polynomial time within n1-ε, for any constant ε > 0, unless NP = ZPP. In this paper, we extend the reductions used to prove this result and combine the extended reductions with a recent result of Samorodnitsky and Trevisan to show that clique cannot be approximated within $$ n^{1 - O} \left( {1/\sqrt {\log \log n} } \right) $$...
The independence number of a graph and its chromatic number are hard to approximate. It is known that, unless coRP = NP, there is no polynomial time algorithm which approximates any of these quantities within a factor of n1-ε for graphs on n vertices. We show that the situation is significantly better for the average case. For every edge probability p = p(n) in the range n−1/2+ε...
Safely adding computational effects to a multi-stage language has been an open problem. In previous work, a closed type constructor was used to provide a safe mechanism for executing dynamically generated code. This paper proposes a general notion of closed type as a simple approach to safely introducing computational effects into multi-stage languages. We demonstrate this approach formally in a core...
We describe SAFL, a call-by-value first-order functional language which is syntactically restricted so that storage may be statically allocated to fixed locations. Evaluation of independent sub-expressions happens in parallel—we use locking techniques to protect shared-use function definitions (i.e. to prevent unrestricted parallel accesses to their storage locations for argument and return values)...
We establish that the algorithmic complexity of the minimum spanning tree problem is equal to its decision-tree complexity. Specifically, we present a deterministic algorithm to find a minimum spanning forest of a graph with n vertices and m edges that runs in time O(T(m,n)) where T is the minimum number of edge-weight comparisons needed to determine the solution. The algorithm is quite simple and...
Thorup recently showed that single-source shortest-paths problems in undirected networks with n vertices, m edges, and edge weights drawn from 0,..., 2w - 1 can be solved in O(n + m) time and space on a unit-cost random-access machine with a word length of w bits. His algorithm works by traversing a so-called component tree. Two new related results are provided here. First, and most importantly, Thorup’s...
Given a node x at depth itd in a rooted tree LevelAncestor (x, i) returns the ancestor to x in depth d — i. We show how to maintain a tree under addition of new leaves so that updates and level ancestor queries are being performed in worst case constant time. Given a forest of trees with n nodes where edges can be added, m queries and updates take O(mα(m, n)) time. This solves two open problems (P...
Lax logical relations are a categorical generalisation of logical relations; though they preserve product types, they need not preserve exponential types. But, like logical relations, they are preserved by the meanings of all lambda-calculus terms.We show that lax logical relations coincide with the correspondences of Schoett, the algebraic relations of Mitchell and the pre-logical relations of Honsell...
We explain how recent developments in game semantics can be applied to reasoning about equivalence of terms in a non-trivial fragment of Idealized AupLGOL (IA) by expressing sets of complete plays as regular languages. Being derived directly from the fully abstract game semantics for IA, our method of reasoning inherits its desirable theoretical properties. The method is mathematically elementary...
We introduce the measurement idea in domain theory and then apply it to establish two fixed point theorems. The first is an extension of the Scott fixed point theorem which applies to nonmonotonic mappings. The second is a contraction principle for monotone maps that guarantees the existence of unique fixed points.
Distributed software systems are typically built according to a three layer conceptual structure: Objects on the lowest layer are clustered by components on the second layer, which themselves are located at nodes of a computer network on the third layer. Orthogonal to these three layers, an instance level and a type or schema level are distinguished when modeling these systems. Accordingly, the changes...
We study the complexity of proving the Pigeon Hole Principle (PHP) in a monotone variant of the Gentzen Calculus, also known as Geometric Logic. We show that the standard encoding of the PHP as a monotone sequent admits quasipolynomial-size proofs in this system. This result is a consequence of deriving the basic properties of certain quasipolynomial-size monotone formulas computing the boolean threshold...
The semantics of Statecharts macro steps, as introduced by Pnueli and Shalev, lacks compositionality. This paper first analyzes the compositionality problem and traces it back to the invalidity of the Law of the Excluded Middle. It then characterizes the semantics via a particular class of linear, intuitionistic Kripke models, namely stabilization sequences. This yields, for the first time in the...
We extend the algebraic approach of Meseguer and Montanari from ordinary place/transition Petri nets to contextual nets, covering both the collective and the individual token philosophy uniformly along the two interpretations of net behaviors.
Ordered binary decision diagrams (OBDDs) are nowadays the most common dynamic data structure or representation type for Boolean functions. Among the many areas of application are verification, model checking, and computer aided design. For many functions it is easy to estimate the OBDD size but asymptotically optimal bounds are only known in simple situations. In this paper, methods for proving asymptotically...
While deterministic finite automata seem to be well understood, surprisingly many important problems concerning nondeterministic finite automata (nfa’s) remain open. One such problem area is the study of different measures of nondeterminism in finite automata. Our results are: 1. There is an exponential gap in the number of states between unambiguous nfa’s and general nfa’s. Moreover, deterministic...
A long standing open problem in the theory of (Mazurkiewicz) traces has been the question whether LTL (Linear Time Logic) is expressively complete with respect to the first order theory. We solve this problem positively for finite and infinite traces and for the simplest temporal logic, which is based only on next and until modalities. Similar results were established previously, but they were all...
Interval Temporal Logic (ITL) is a formalism for reasoning about time periods. To date no one has proved completeness of a relatively simple ITL deductive system supporting infinite time and permitting infinite sequential iteration comparable to ω-regular expressions. We have developed a complete axiomatization for such a version of quantified ITL over finite domains and can show completeness...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.