Search

This paper presents a parallel artificial immune system designed for graph coloring. The algorithm is based on the clonal selection principle. Each processor operates on its own pool of antibodies and a migration mechanism is used to allow processors to exchange information. Experimental results show that migration improves the performance of the algorithm. The experiments were performed using a high performance cluster on a set of well-established graph instances available on the Web. [ABSTRACT FROM AUTHOR]

We introduce the notion of net-slice to describe a subnet of a marked Petri net Σ that approximates Σ's temporal behaviour with respect to a set of places P. We consider slices Σ′ whose set of places comprises the places referred to by a CTL* formula φ. If Σ is fair w.r.t. the transitions of a slice, Σ ⊧ φ can be verified and falsified by examining the slice, given φ is a CTL* formula built without using the next-time operator. Verification of LTL$_{\textrm{-\tiny{X}}}$ formulas is thus possible under these very weak fairness assumptions, though LTL formulas using next-time can be falsified. [ABSTRACT FROM AUTHOR]

The need for data privacy motivates the development of new methods that allow to protect data minimizing the disclosure risk without losing valuable statistical information. In this paper, we propose a new protection method for numerical data called Ordered Neural Networks (ONN). ONN presents a new way to protect data based on the use of Artificial Neural Networks (ANNs). The main contribution of ONN is a new strategy for preprocessing data so that the ANNs are not capable of accurately learning the original data set. Using the results obtained by the ANNs, ONN generates a new data set similar to the original one without disclosing the real sensible values. We compare our method to the best methods presented in the literature, using data provided by the US Census Bureau. Our experiments show that ONN outperforms the previous methods proposed in the literature, proving that the use of ANNs is convenient to protect the data efficiently without losing the statistical properties of the set. [ABSTRACT FROM AUTHOR]

Growing need for information retrieval, information processing, and the associated need for navigation in existing information spaces resulted in several approaches that aim to improve efficiency of the respective user tasks. However, problems related to user navigation and orientation in large open information spaces still persist possibly due to increasing demands and the imperfections of individual approaches. We propose an integrated search and navigation solution that takes advantage of the faceted browsing paradigm and visual navigation in graphs both extended with support for automatic personalization based on user context also taking advantage of a user's social network. The proposed solution is primarily evaluated in the domain of scientific publications, i.e. digital libraries, with possible extensions to other application domains. [ABSTRACT FROM AUTHOR]

Over the last decade, Web and multimedia data have grown at a staggering rate. Users of new media now have great expectations of what they can see on the Web. In addition, most information retrieval systems, including Web search engines, use similarity ranking algorithms based on a vector space model to find relevant information in response to a user's request. However, the retrieved information is frequently irrelevant, because most of the current information systems employ index terms or other techniques that are variants of term frequency. This paper proposed a new approach, named "the dynamic multimedia presentations with a Generality Model," to offer a customized multi-modal presentation for an intended audience. Moreover, we proposed a new criterion, "generality," that provides an additional basis on which to rank retrieved documents. To support multi-modal presentation, our proposed story model created story structures that can be dynamically instantiated for different user requests from various multi-modal elements. The generality is a level of abstraction to retrieve results based on desired generality appropriate for a user's knowledge and interests. We compared traditional web news search functions and our story model by using usability test. The result shows that our multimedia presentation methodology is significantly better than the current search functions. We also compared our generality quantification algorithm with human judges' weighting of values to show that the developed algorithm is significantly correlated. [ABSTRACT FROM AUTHOR]

In this paper was proposed a method for the description of web pages using web patterns. We will explain what we mean by the term "web pattern". We will present a taxonomy web patterns and a description of some their types. In the description of web patterns we will focus on properties which are useful for automatic detection on web pages. As a result of the detection we get a description of a web page using found web patterns. The description can be used for reordering and clustering of a web page set. [ABSTRACT FROM AUTHOR]

Contemporary XML documents can be tens of megabytes long, and reducing their size, thus allowing to transfer them faster, poses a significant advantage for their users. In this paper, we describe a new XML compression scheme which outperforms the previous state-of-the-art algorithm, SCMPPM, by over 9% on average in compression ratio, having the practical feature of streamlined decompression and being almost twice faster in the decompression. Applying the scheme can significantly reduce transmission time/bandwidth usage for XML documents published on the Web. The proposed scheme is based on a semi-dynamic dictionary of the most frequent words in the document (both in the annotation and contents), automatic detection and compact encoding of numbers and specific patterns (like dates or IP addresses), and a back-end PPM coding variant tailored to efficiently handle long matching sequences. Moreover, we show that the compression ratio can be improved by additional 9% for the price of a significant slow-down. [ABSTRACT FROM AUTHOR]

XBW [10] is modular program for lossless compression that enables testing various combinations of algorithms. We obtained best results with XML parser creating dictionary of syllables or words combined with Burrows-Wheeler transform - hence the name XBW. The motivation for creating parser that handles non-valid XML and HTML files, has been system EGOTHOR [5] for full-text searching. On files of size approximately 20MB, formed by hundreds of web pages, we achieved twice the compression ratio of bzip2 while running only twice as long. For smaller files, XBW has very good results, compared with other programs, especially for languages with rich morphology such as Slovak or German. For any big textual files, our program has good balance of compression and run time. Program XBW enables use of parser and coder with any implemented algorithm for compression. We have implemented Burrows-Wheeler transform which together with MTF and RLE forms block compression, dictionary methods LZC and LZSS, and finally statistical method PPM. Coder offers choice of Huffman and arithmetic coding. [ABSTRACT FROM AUTHOR]

The development of structure analysis that constitutes the core part of social network analysis is continuously supported by the rapid expansion of different kinds of social networks available in the Internet. The network analyzed in this paper is built based on the email communication between people. Exploiting the data about this communication some personal social features can be discovered, including personal position that means individual importance within the community. The evaluation of position of an individual is crucial for user ranking and extraction of key network members. The new method of personal importance analysis is presented in the paper. It takes into account the strength of relationships between network members, its dynamic as well as personal position of the nearest neighbours. The requirements for the commitment function that reflects the strength of the relationship are also specified. In order to validate the proposed method, the dataset containing Enron emails is utilized; first to build the virtual social network and afterwards to assess the position of the network members. [ABSTRACT FROM AUTHOR]

In this paper we present a communicational proof-of-work - a new tool that can be used, among others, for filtering messages and limiting spam. Our idea can be regarded as an analogue of regular proofs-of-work introduced by Dwork and Naor. The idea presented in our paper is as follows: the prover has to provide a convincing evidence that he had communicated with other, randomly chosen entity. This approach is essentially different from previous proofs-of-work, because fulfilling this requirement does not depend on resources owned by the prover (e.g. sender) only. Thanks to this, even if the adversary (e.g. spammer) has an access to much more efficient computers, he does not have any important advantage over regular, honest users of the system. We also demonstrate some other applications of the presented idea as well as some extensions based on its combination with regular proofs-of-work. Together with algorithms we also briefly describe a proof of our concept i.e. working implementation. We present some experimental data and statistics obtained during tests of our application. [ABSTRACT FROM AUTHOR]

We have developed and implemented [1,2] infrastructure and RDF storage for the Semantic Web. When we filled it with data the need for some tool that could explore the data became evident. Unfortunately, none of existing solutions fulfills requirements imposed by the data and users expectations. This paper presents our RDF visualizer that was designed specifically to handle large RDF data by means of incremental navigation. A detailed description of the algorithm is given as well as actual results produced by the visualizer. [ABSTRACT FROM AUTHOR]

We present an algorithm for intelligent prediction of user requests in a system based on the services hosted by independent providers. Data extracted from requests is organized in a dynamically changing graph representing dependencies between operations and input arguments as well as between groups of arguments mutually coexisting in requests. The purpose of the system is to suggest the possible set of future requests basing on the last submitted request and the state of the graph. Additionally the response time may be shortened owing to the background executing and caching of the requests most likely to be asked. The knowledge extracted from the graph analysis reveals the mechanisms that govern the sequences of invoked requests. Such knowledge can help in semi-automatic generation of business processes. The algorithm is a part of ASK-IT (Ambient Intelligence System of Agents for Knowledge-based and Integrated Services for Mobility Impaired users) EU project. [ABSTRACT FROM AUTHOR]

Much research work has recently focused on the problem of representing historical information in XML. In this paper, we describe an ongoing work to represent XML changes. Our model is a three-dimensional XML-based model (3D_XML in short) for representing and querying histories of XML documents. The proposed model incorporates three time dimensions, valid time, transaction time, and efficacy time without extending the syntax of XML. We use XQuery to express complex temporal queries on the evolution of the document contents. We believe that native XML databases (NXDs) present a viable alternative to relational temporal databases when complex time dependent data has to be manipulated and stored. So NXDs will be our choice. [ABSTRACT FROM AUTHOR]

In this paper we describe the process of experimental ontology data set creation. Such a semantically enhanced data set is needed in experimental evaluation of applications for the Semantic Web. Our research focuses on various levels of the process of data set creation - data acquisition using wrappers, data preprocessing on the ontology instance level and adjustment of the ontology according to the nature of the evaluation step. Web application aimed at clustering of ontology instances is utilized in the process of experimental evaluation, serving both as an example of an application and visual presentation of the experimental data set to the user. [ABSTRACT FROM AUTHOR]

We consider the following problem: users of an organization wish to outsource the storage of sensitive data to a large database server. It is assumed that the server storing the data is untrusted so the data stored have to be encrypted. We further suppose that the manager of the organization has the right to access all data, but a member of the organization can not access any data alone. The member must collaborate with other members to search for the desired data. In this paper, we investigate the notion of threshold privacy preserving keyword search (TPPKS) and define its security requirements. We construct a TPPKS scheme and show the proof of security under the assumptions of intractability of discrete logarithm, decisional Diffie-Hellman and computational Diffie-Hellman problems. [ABSTRACT FROM AUTHOR]

A metaheuristic for solving complex problems is proposed. The introduced Sensitive Robot Metaheuristic (SRM) is based on the Ant Colony System optimization technique. The new model relies on the reaction of virtual sensitive robots to different stigmergic variables. Each robot is endowed with a particular stigmergic sensitivity level ensuring a good balance between search diversification and intensification. Comparative tests are performed on large-scale NP-hard robotic travel problems. These tests illustrate the effectiveness and robustness of the proposed metaheuristic. [ABSTRACT FROM AUTHOR]

Model complexity of feedforward neural networks is studied in terms of rates of variable-basis approximation. Sets of functions, for which the errors in approximation by neural networks with n hidden units converge to zero geometrically fast with increasing number n, are described. However, the geometric speed of convergence depends on parameters, which are specific for each function to be approximated. The results are illustrated by examples of estimates of such parameters for functions in infinite-dimensional Hilbert spaces. [ABSTRACT FROM AUTHOR]

A given set F of n×n matrices is said to be mortal if the n×n null matrix belongs to the free semigroup generated by F. It is known that the mortality problem for 3×3 matrices with integer entries is undecidable [7],[3]. In this paper we prove that the mortality problem is decidable for any set of 2×2 integer matrices whose determinants assume the values 0,±1. [ABSTRACT FROM AUTHOR]

This paper proposes a new hybrid method to formally verify whether the security specification of a target information system satisfies security functional requirements defined in ISO/IEC 15408 evaluation criteria for security. We classify at first the security functional requirements of ISO/IEC 15408 into two classes: static requirements concerning static properties and dynamic requirements concerning dynamic behavior of target systems, and then formalize the static requirements with Z notation and the dynamic requirements with temporal logic. Thus, we can verify static properties using theorem-proving and dynamic behavior using model-checking. As a result, developers can easily use the method to verify whether the security specification of a target information system satisfies both static and dynamic security functional requirements defined in ISO/IEC 15408. The new method is an evolution and improvement of our early verification method where only Z notation was adapted and to verify dynamic behavior of target systems is difficult. [ABSTRACT FROM AUTHOR]

This article presents additional necessary measures that enable us to use Pict as an object-capability programing language. It is desirable to be able to assess the worst possible threat that we—users—risk if we run a given program. If we know the threat, we are able to decide whether or not we are willing to risk running the program. The cost of a security audit that reveals such an assessment will be non-zero but it need not to be directly dependent on the size of the whole original program. It is possible to write programs in such a way that this analysis can be reliably performed on a fraction of the original program—on the trusted computing base. This technique does not always give the most accurate assessment but it gives sound and interesting assessment relatively cheaply. It does not prevent usage of other techniques that can further refine the initial assessment. [ABSTRACT FROM AUTHOR]

A party using encrypted communication or storing data in an encrypted form might be forced to show the corresponding plaintext. It may happen for law enforcement reasons as well as for evil purposes. Deniable encryption scheme introduced by Canetti et al. shows that cryptography can be used against revealing information: the owner of the data may decrypt it in an alternative way to a harmless plaintext. Moreover, it is impossible to check if there is another hidden plaintext. The scheme of Canetti is inefficient in the sense that it is a special purpose scheme and using it indicates that there is some hidden message inside. We show that deniable encryption can be implemented in a different way so that it does not point to exploiting deniable encryption. Moreover, it is quite straightforward, so it can be used for both good and evil purposes. Apart from that we show that even the special purpose original scheme can be extended to allow, in some circumstances, any "depth" of deniability. [ABSTRACT FROM AUTHOR]

We analyze the Threeballot voting system proposed recently by R. Rivest. We investigate the relation between the number of the candidates in a race and effectiveness of Strauss' attack. We also show that in a reasonable scenario it is impossible to reconstruct voters' preferences for a single race with two candidates. [ABSTRACT FROM AUTHOR]

Based on the principle that "the ultimate method to secure a network is to disconnect it", the Lock-Keeper technology has been known as an efficient approach to guarantee the high-level security and prevent online network attacks by physically separating the protected hosts or networks. Because of its simple idea and extensible architecture, the Lock-Keeper system can be easily and seamlessly integrated with other security methods or solutions to provide thorough protection for most actual network-based applications. This paper will propose an advanced strong authentication framework based on the Lock-Keeper. Thanks to Lock-Keeper's physical disconnection, all the credentials, privacies and policies required by the authentication mechanism can be securely stored and manipulated by being completely isolated with both the external and the internal networks. The whole authentication procedure can be performed in the clean and trusted Lock-Keeper GATE component. Based on the proposed framework, a prototypical platform is implemented in the Lock-Keeper to enhance the security of the Lock-Keeper Web Service module, which is one of important Lock-Keeper application modules, and can be applied to secure most web applications in Service-Oriented-Architecture environment. [ABSTRACT FROM AUTHOR]

This article describes the way how some amount of information can be stored into DNS, particularly in the cache of DNS server. Then it can be retrieved back, possibly by another host in the network. Based on this principle we can construct a communication channel, hidden in the usual traffic, or a memory medium. Considering this kind of media, some basic characteristics and limits, like capacity, transfer speed, error rate, persistence of information, etc., are discussed here. Simple algorithm deciding whether a bit in the memory has been set or not was proposed and implemented. Its performance and optimal setting was examined. The results show that under some circumstances error rates about 0.003, when retrieving the information, can be achieved. [ABSTRACT FROM AUTHOR]

In the paper, a new memetic algorithm for decision tree learning is presented. The proposed approach consists in extending an existing evolutionary approach for global induction of classification trees. In contrast to the standard top-down methods, it searches for the optimal univariate tree by evolving a population of trees. Specialized genetic operators are selectively applied to modify both tree structures and tests in non-terminal nodes. Additionally, a local greedy search operator is embedded into the algorithm, which focusses and speeds up the evolutionary induction. The problem of over-fitting is mitigated by suitably defined fitness function. The proposed method is experimentally validated and preliminary results show that the proposed approach is able to effectively induce accurate and concise decision trees. [ABSTRACT FROM AUTHOR]

Preferences can be used for information filtering and extraction to deliver the most relevant data to the user. Therefore the efficient integration of querying with preferences into standard database technology is an important issue. The paper resumes a logical framework for formulating preferences and their embedding into relational algebra through a single preference operator parameterized by a set of user preferences of sixteen various kinds and returning only the most preferred subsets of its argument relation. Most importantly, preferences between sets of elements can be expressed. To make a relational query language with the preference operator useful for practical applications, formal foundation for algebraic optimization, applying heuristics like push preference, has to be provided. Therefore abstract properties of the preference operator and a variety of algebraic laws describing its interaction with other relational algebra operators are presented. [ABSTRACT FROM AUTHOR]

We study some properties of quantum walks on the plane. First, we discuss the behavior of quantum walks when moving marked locations are introduced. Second, we present an exceptional case, when quantum walk fails to find any of the marked locations. [ABSTRACT FROM AUTHOR]

For a continuous-time quantum walk on a line the variance of the position observable grows quadratically in time, whereas, for its classical counterpart on the same graph, it exhibits a linear, diffusive, behaviour. A quantum walk, thus, propagates at a rate which is linear in time, as compared to the square root rate for a classical random walk. Indeed, it has been suggested that there are graphs that can be traversed by a quantum walker exponentially faster than by the classical random analogue. In this note we adopt the approach of exploring the conditions to impose on a Markov process in order to emulate its quantum counterpart: the central issue that emerges is the problem of taking into account, in the numerical generation of each sample path, the causative effect of the ensemble of trajectories to which it belongs. How to deal numerically with this problem is shown in a paradigmatic example. [ABSTRACT FROM AUTHOR]

We present quantum query and time complexity bounds for group testing problems. For a set S and a binary operation on S, we consider the decision problem whether a groupoid, semigroup or quasigroup is a group. Our quantum algorithms for these problems improve the best known classical complexity bounds. We also present upper and lower bounds for testing associativity, distributivity and commutativity. [ABSTRACT FROM AUTHOR]

In John Tantalo's on-line game Planarity the player is given a non-plane straight-line drawing of a planar graph. The aim is to make the drawing plane as quickly as possible by moving vertices. Pach and Tardos have posed a related problem: can any straight-line drawing of any planar graph with n vertices be made plane by vertex moves while keeping ${\Omega(n^\ensuremath{\varepsilon})}$ vertices fixed for some absolute constant $\ensuremath{\varepsilon} >0$? It is known that three vertices can always be kept (if n ≥ 5). We still do not solve the problem of Pach and Tardos, but we report some progress. We prove that the number of vertices that can be kept actually grows with the size of the graph. More specifically, we give a lower bound of $\Omega(\sqrt{\log n / \log \log n})$ on this number. By the same technique we show that in the case of outerplanar graphs we can keep a lot more, namely $\Omega(\sqrt{n})$ vertices. We also construct a family of outerplanar graphs for which this bound is asymptotically tight. [ABSTRACT FROM AUTHOR]

taDOM* protocols are designed to provide lock-based approach to handle multiple access to XML databases. The notion of taDOM+ protocol is formalized and generalized and a formal model of taDOM+ lock manager that is parameterized in the number of transactions and in the size of database is represented. An important class of safety properties of taDOM+ lock managers were proven to be checked by examining just a small number of finite-state instances of the parameterized model. Our results were applied to prove a generalized mutual exclusion property, known as repeatable-read, of taDOM2+ and taDOM3+ lock managers by model-checking. [ABSTRACT FROM AUTHOR]

We investigate the following problem: Given a list of n items and a function defined over lists of these items, generate a bounded amount of auxiliary information such that range queries asking for the value of the function on sub-lists can be answered within a certain time bound. For the function "mode" we improve the previously known time bound O(nεlogn) to O(nε) with space O(n2 − 2ε), where 0 ≤ ε< 1/2. We improve the space bound O(n2loglogn/logn) for an O(1) time bounded solution to O(n2/logn). For the function "median" the space bound O(n2loglogn/logn) is improved to O(n2log(k)n/logn) for an O(1) time solution, where k is an arbitrary constant and log(k) is the iterated logarithm. [ABSTRACT FROM AUTHOR]

We introduce the generalized notion of automata synchronization, so called partial synchronization, which holds for automata with partial transition function. We give a lower bound for the length of minimal synchronizing words for partial synchronizing automata. The difference, in comparison to the 'classical' synchronization, lies in the initial conditions: let $\mathcal{A}=(Q, A, \delta)$ be an automaton representing the dynamics of a particular system. In case of partial synchronization we assume that initial conditions (initial state of the system) can be represented by some particular states, that is by some P ⊂ Q, not necessarily by all possible states from Q. At first glance the above assumption limits our room for manoeuvre for constructing possibly long minimal synchronizing words (because of the lower number of states at the beginning). Unexpectedly this assumption allows us to construct longer minimal synchronizing words than in a standard case. In our proof we use Sperner's Theorem and some basic combinatorics. [ABSTRACT FROM AUTHOR]

A set K in the plane ℝ2 is basic if each continuous function $f \: K \to \mathbb R$ can be expressed as a sum f(x,y) = g(x) + h(y) with $g, h \: \mathbb R \to \mathbb R$ continuous functions. Analogously we define a digital set Kk in the digital plane to be basic if for each digital function $f: {K_k} \to {\mathbb R}$ there exist digital functions on the digital unit interval such that f(x,y) = g(x) + h(y) for each pixel (x,y) ∈ Kk. Basic subsets of the plane were characterized by Sternfeld and Skopenkov. In this paper we prove a digital analogy of this result. Moreover we explore the properties of digital basic sets, and their possible use in image analysis. [ABSTRACT FROM AUTHOR]

We investigate rational relations over trees. Our starting point is the definition of rational tree relations via rational expressions by Raoult (Bull. Belg. Math. Soc. 1997). We develop a new class of automata, called asynchronous tree automata, which recognize exactly these relations. The automata theoretic approach is convenient for the solution of algorithmic problems (like the emptiness problem). The second contribution of this paper is a new subclass of the rational tree relations, called separate-rational tree relations, defined via a natural restriction on asynchronous tree automata. These relations are closed under composition, preserve regular tree languages, and generate precisely the regular sets in the unary case (all these properties fail for the general model), and they are still more powerful than, for instance, the automatic tree relations. [ABSTRACT FROM AUTHOR]

This paper studies two problems on compressed strings described in terms of straight line programs (SLPs). One is to compute the length of the longest common substring of two given SLP-compressed strings, and the other is to compute all palindromes of a given SLP-compressed string. In order to solve these problems efficiently (in polynomial time w.r.t. the compressed size) decompression is never feasible, since the decompressed size can be exponentially large. We develop combinatorial algorithms that solve these problems in O(n4 logn) time with O(n3) space, and in O(n4) time with O(n2) space, respectively, where n is the size of the input SLP-compressed strings. [ABSTRACT FROM AUTHOR]

We investigate off-line Turing machines equipped with a two-way input-tape and one work-tape. It is shown that the Element Distinctness Problem (EDP) for m binary strings of length ℓ = O(m/log2m) can be solved in time O(m3/2ℓ1/2) and space O(m1/2ℓ1/2) on a nondeterministic machine. This is faster than the best sorting algorithm on the computational model and optimal if time and space are considered simultaneously. For deterministic machines we give an optimal algorithm that can sort m binary strings consisting of ℓ bits each in O(m3/2ℓ) steps, provided that ℓ = O(m1/4). By modifying the solution we obtain the time bound O(m3/2ℓ) and the space bound O(m1/2ℓ2) for the EDP. [ABSTRACT FROM AUTHOR]

An important role of a workflow system is to schedule and reschedule the workflow process and to allow the user to monitor and guide the overall progress of the workflow and its activities. This paper presents extensions of a rescheduling algorithm based on minimal graph cut. The initial approach allowed to find an optimal rescheduling, which changed the initial schedule by shortening and moving of activities. The new schedule had the lowest overall price, counted as the sum of prices of shortening activities. The extension presented in this paper allows several extensions, while keeping the optimality: handling several delayed activities, handling the price of moving an activity and handling the price of deadline violation. The rescheduling algorithm is used within an ontology-based workflow management system for the process of military exercise preparation in Centre of simulation technologies National Academy of Defence. [ABSTRACT FROM AUTHOR]

We consider infinite two-player games played on finite graphs where the winning condition (say for the first player) is given by a regular omega-language. We address issues of optimization in the construction of winning strategies in such games. Two criteria for optimization are discussed: memory size of finite automata that execute winning strategies, and - for games with liveness requests as winning conditions - "waiting times" for the satisfaction of requests. (For the first aspect we report on work of Holtmann and Löding, for the second on work of Horn, Wallmeier, and the author.) [ABSTRACT FROM AUTHOR]

Interaction systems are a formal model for component-based systems, where components are combined via connectors to form more complex systems. We compare interaction systems (IS) to the well-studied model of 1-safe Petri nets (1SN) by giving a translation map1: 1SN → IS and a translation map2: IS → 1SN, so that a 1-safe Petri net (an interaction system) and its according interaction system (1-safe Petri net) defined by the respective mapping are isomorphic up to some label relation R. So in some sense both models share the same expressiveness. Also, the encoding $\textit{map}_1$ is polynomial and can be used to reduce the problems of reachability, deadlock and liveness in 1SN to the problems of reachability, deadlock and liveness in IS, yielding PSPACE-hardness for these questions. [ABSTRACT FROM AUTHOR]

A server repeatedly transmits data items (pages) possibly with different speeds on a set of channels. The objective is to minimize energy consumption of the schedule. We adopt the common model that sending at speed s for t time units consumes t ·sα energy for a constant α ≥ 2. An individual window length is associated with each page. This length is a strict upper bound on the time between two consecutive broadcasts for that page. We present an easy to implement algorithm for the single channel case that obtains an approximation ratio of 3·4α. For the multi-channel case with identical channels an extension of this algorithm computes an 8α-approximation. Both algorithms run in low-order polynomial time. As our main tool for the analysis, we show that it suffices to consider periodic schedules as their energy density (total energy consumption per time unit) differs from the one of general schedules at most by (1 + ε) for an arbitrary constant ε> 0. [ABSTRACT FROM AUTHOR]

In this paper, we revisit the much studied problem of Pattern matching with Swaps (Swap Matching problem, for short). We first present a new graph-theoretic approach to model the problem, which opens a new and so far unexplored avenue to solve the problem. Then, using the model, we devise an efficient algorithm to solve the swap matching problem. The resulting algorithm is an adaptation of the classic shift-or algorithm. For patterns having length similar to the word-size of the target machine, the algorithm runs in O(nlogm) time, where n and m are the length of the text and the pattern respectively. [ABSTRACT FROM AUTHOR]

This paper focuses on tractable instances of interval data minmax regret graph problems. More precisely, we provide polynomial and pseudopolynomial algorithms for sets of particular instances of the interval data minmax regret versions of the shortest path, minimum spanning tree and weighted (bipartite) perfect matching problems. These sets are defined using a parameter that measures the distance from well known solvable instances. Tractable cases occur when the parameter is bounded by a constant. Two kinds of parameters are investigated, measuring either the distance from special weight structures or the distance from special graph structures. [ABSTRACT FROM AUTHOR]

We develop a Coq formalization of the matrix interpretation method, which is a recently developed, powerful approach to proving termination of term rewriting. Our formalization is a contribution to the CoLoR project and allows to automatically certify matrix interpretation proofs produced by tools for proving termination. Thanks to this development the combination of CoLoR and our tool, TPA, was the winner in 2007 in the new certified category of the annual Termination Competition. [ABSTRACT FROM AUTHOR]

We consider the problem of graph orientation on-line. Orientation of a graph is an assignment of direction to every edge, resulting with a directed graph. The optimal orientation of a graph G is the one which maximizes the number of ordered pairs (u,v) of vertices of G for which there is a directed path from u to v in the resulting directed graph. Graph orientation on-line is a game in which one of the players constructs a graph by adding vertices one by one, so that the graph is connected at all times, and the second one assigns direction to the newly added edges. The goal of the second player is to maximize the number of connected pairs in the orientation, while the first player is trying to minimize it. We present asymptotically optimal strategies for both players and state that the game with n turns has a $\Theta\left(n \frac{\log n}{\log \log n}\right)$ outcome. [ABSTRACT FROM AUTHOR]

A study of assisted problem solving formalized via decompositions of deterministic finite automata is initiated. The landscape of new types of decompositions of finite automata this study uncovered is presented. Languages with various degrees of decomposability between undecomposable and perfectly decomposable are shown to exist. [ABSTRACT FROM AUTHOR]

Filter models and (solutions of) recursive domain equations are two different ways of constructing lambda models. Many partial results have been shown about the equivalence between these two constructions (in some specific cases). This paper deepens the connection by showing that the equivalence can be shown in a general framework. We will introduce the class of disciplined intersection type theories and its four subclasses: natural split, lazy split, natural equated and lazy equated. We will prove that each class corresponds to a different recursive domain equation. For this result, we are extracting the essence of the specific proofs for the particular cases of intersection type theories and making one general construction that encompasses all of them. This general approach puts together all these results which may appear scattered and sometimes with incomplete proofs in the literature. [ABSTRACT FROM AUTHOR]

A model (consisting of rv-systems), a core programming language (for developing rv-programs), several specification and analysis techniques appropriate for modeling, programming and reasoning about interactive computing systems have been recently introduced by Stefanescu using register machines and space-time duality, see [13]. In [3,4,5,6] the authors have have introduced and studied structured programming techniques for rv-systems. The aim of the present paper is to define a scenario-based operational semantics for structured rv-programs and to offer a translation from structured rv-programs to rv-programs. The main technical result states that the translation is correct. This is part of an effort to get a running environment for structured rv-programs built up on top of rv-programs. [ABSTRACT FROM AUTHOR]

The advent of e-commerce, e-government, and the rapid expansion of world-wide connectivity demands end-user systems that adhere to well-defined security policies. In this context Trusted Computing (TC) aims at providing a framework and effective mechanisms that allow computing platforms and processes in a distributed IT system to gain assurance about each other's integrity/trustworthiness. An industrial attempt towards realization of TC is the initiative of the Trusted Computing Group (TCG), an alliance of a large number of IT enterprises. The TCG has published a set of specifications for extending conventional computer architectures with a variety of security-related features and cryptographic mechanisms. The TCG approach has not only been subject of research but also public debates and concerns. Currently, several prominent academic and industrial research projects are investigating trustworthy IT systems based on TC, virtualization technology, and secure operating system design. We highlight special aspects of Trusted Computing and present some current research and challenges. We believe that TC technology is indeed capable of enhancing the security of computer systems, and is another helpful means towards establishing trusted infrastructures. However, we also believe that it is not a universal remedy for all of the security problems we are currently facing in information societies. [ABSTRACT FROM AUTHOR]

We propose a new way of characterizing the complexity of online problems. Instead of measuring the degradation of output quality caused by the ignorance of the future we choose to quantify the amount of additional global information needed for an online algorithm to solve the problem optimally. In our model, the algorithm cooperates with an oracle that can see the whole input. We define the advice complexity of the problem to be the minimal number of bits (normalized per input request, and minimized over all algorithm-oracle pairs) communicated between the algorithm and the oracle in order to solve the problem optimally. Hence, the advice complexity measures the amount of problem-relevant information contained in the input. We introduce two modes of communication between the algorithm and the oracle based on whether the oracle offers an advice spontaneously (helper) or on request (answerer). We analyze the Paging and DiffServ problems in terms of advice complexity and deliver tight bounds in both communication modes. [ABSTRACT FROM AUTHOR]