Catálogo de publicaciones - libros

Shannon’s theory of information stands on a probabilistic representation of events that convey information, e.g., sending messages over a communication channel. Kolmogorov argues that information is a more fundamental concept which exists also in problems with no underlying stochastic model, for instance, the information contained in an algorithm or in the genome. In a classic paper he defines the discrete entropy of a finite set which establishes a combinatorial based definition of the information (:y) conveyed by a variable x (taking a binary string value ) about the unknown value of a variable y. The current paper extends Kolmogorov’s definition of information to a more general setting where given ‘x= ’ there may still be uncertainty about the set of possible values of y. It then establishes a combinatorial based description complexity of and introduces a novel concept termed , similar to -widths in approximation theory. This forms the basis of new measures of cost and efficiency of information which give rise to a new framework whereby information of any input source, e.g., sample-based, general side-information or a hybrid of both, is represented and computed according to a single common formula. As an application, we consider the space of Boolean functions where input strings correspond to descriptions of properties of classes of Boolean functions.

We investigate deterministically simulating (i.e., solving the membership problem for) nondeterministic finite automata (NFA), relying solely on the NFA’s resources (states and transitions). Unlike the standard NFA simulation, involving an algorithm which stores at each step all the states reached nondeterministically while reading the input, we consider deterministic finite automata (DFA) with lookahead, which choose the “right” NFA transitions based on a fixed number of input symbols read ahead. This concept, known as , arose in a formal study of web services composition and its subsequent practical applications. Here we answer several related questions, such as and . In particular, we show that only finite languages have the property that all of their NFA’s have delegators. This implies, among others, that delegation is a machine property, rather than a language property. We also prove that the existence of lookahead delegators for unambiguous NFA is decidable, thus partially solving an open problem. Finally, we show that finding delegators (even for a given buffer size) is hard in general, and is efficient for unambiguous NFA, and we give an algorithm and a compact characterization for NFA delegation in general.

Hierarchical Mobile IPv6 (HMIPv6) has been proposed by Internet Engineering Task Force (IETF) to compensate for such problems as handover latency and signaling overheads in employing Mobile IPv6 (MIPv6). However, HMIPv6 causes load concentration at a particular MAP and longer handover latency when inter-domain handover occurs. In order to solve such problems, this paper establishes a virtual domain (VD) of a higher layer MAP and proposes a MAP changing scheme. The mobile node (MN) changes the routing path between an MN and a correspondent node (CN) according to the mobile position and the direction of the MN before inter-domain handover occurs. We simulate the performance of the MAP changing scheme and compare with HMIPv6. We also analyze the MAP changing scheme through numerical modeling in comparison with other schemes.

Restarting automata were introduced to model the linguistic concept of . In recent years there was a growing effort to study classes of formal languages that are generated by different variants of these automata. We follow this line of research and generalize the model to a more complex data structure: free term algebras (or trees). Many of the known results about restarting automata on strings carry over to the new model. We study the expressive power of restarting tree automata and prove some closure properties.

An important problem in complexity theory is to find polynomial time constructible hitting sets for Boolean functions in different standard models. This would have consequences for the relationship between deterministic and probabilistic computations in the respective models. Using the result by Alon, Goldreich, Håstad, and Peralta (1992) we provide a polynomial time constructible hitting set for restricted read-once branching programs of width 3. The restriction excludes only one from all patterns of level-to-level transitions in a normalized form of 3-width 1-branching programs. In fact, our technique works for a slightly more general class of such programs. Although this restriction seems to be relatively strong our proof reveals the core of difficulties and thus represents the first step for proving the result for less restricted models.

Formal translation directed by parallel parsing is presented here. The translator follows the traditional translation scheme – the input grammar is extended by output symbols that are added into appropriate right-hand sides of grammar rules. The translation algorithm is based on the intermediate results provided by the parallel parser. The correct sequence of output symbols is obtained from the intermediate results using the parallel prefix sum, the segmented parallel prefix sum, and parallel sorting steps. The translation algorithm presented here is suitable for all translations with (,) input grammars. The asymptotical parallel time of the translation algorithm is .

Multicast has great advantages in data forwarding. But the number of forwarding states becomes huge in routers when there are large numbers of multicast groups in the network, which may cause explosions of state information and control information. Aggregated multicast is a novel approach to reducing multicast state numbers. It enables multicast groups to share a single distribution tree so that the tree management overhead at core routers can be reduced. Aggregated Multicast can actually be attributed to minimal set cover problem, which is an NP-complete problem. To solve it this paper proposes a self-adaptive Lagrange Relaxation Algorithm, which can achieve global optimal solution. Simulation results show that this algorithm is better than the conventional greedy algorithm in that it improves aggregation degree and reduces multicast state number.

Service Composition is one of the pillars under Service Oriented Architecture. BPEL becomes the de-facto standard within this area. A key aspect when aggregating business processes using BPEL is to realize a compensation-based reliable service composition, often referred to as BPEL LRT(Long Running Transaction). But there lacks precise modeling on how to combine BPEL control flow with long running transactions. The paper presents a formal language named BPTX, which is a simplified version of BPEL at syntactic level and offers effective directions to underlying transaction coordinator as semantics. The paper also proposes an optimization not contained in traditional transaction processing: detect the failure destiny of a branch and react to it as early as possible.

This paper investigates the operational semantics of framed temporal logic programs. To this end, a framed temporal logic programming language called Framed Tempura is employed. The evaluation rules for both the arithmetic and boolean expressions are defined. The semantic equivalence rules for the reduction of a program within a state is formalized. Furthermore, the congruence and transition rules between configurations for the reduction of programs are also specified. Thus, the executable behavior of framed programs can be captured in an operational way. In addition, the consistency of the operational semantics and the minimal model semantics based on model theory is proved.

The dependency pair method is a powerful method for automatically proving termination of rewrite systems. When used with traditional simplification orders like LPO and KBO, argument filterings play a key role. In this paper we propose an encoding of argument filterings in propositional logic. By incorporating propositional encodings of simplification orders, the search for suitable argument filterings is turned into a satisfiability problem. Preliminary experimental results show that our logic-based approach is significantly faster than existing implementations.