waashk/dblp huggingface dataset:
an analytical approach to the inference of summary data of additive type. summary data take the form of a triple that consists of a summary attribute, a category and a numeric value. the inference problem of summary data consists in deciding whether or not a summary data of interest is evaluable (i.e., can be computed) from a given set of summary data. we address the special case of the inference problem with homogeneous summary data (i.e., summary data with the same summary attribute), where the summary attribute is of additive nature. owing to additivity, one can model the information content of the given summary data by a linear equation system whose variables are constrained to take their values from the domain of the summary attribute. we state two evaluability criteria, one for a real or integral summary attribute, and the other for a nonnegative-real or nonnegative-integral summary attribute. using the two evaluability criteria, we show that our inference problem can be solved in strongly polynomial time for a real or integral or nonnegative real summary attribute, and is co>i>np-complete for a nonnegative-integral summary attribute. moreover, we prove that, given a summary data of interest that is not evaluable, even in the (simplest) case that the summary attribute is of a real type, finding an evaluable summary data whose category is maximally contained in (or minimally contains) the category of the summary data of interest is an np-hard problem.
classification of rotations on the torus t. we consider rotations on the torus , and we classify them with respect to the complexity functions. in dimension one, a minimal rotation can be coded by a sturmian word. a sturmian word has complexity n+1 by the morse-hedlund theorem. here we make a generalization in dimension two.
approximation algorithms for maximum cut with limited unbalance. we consider the problem of partitioning the vertices of a weighted graph into two sets of sizes that differ at most by a given threshold b, so as to maximize the weight of the crossing edges. for b equal to 0 this problem is known as max bisection, whereas for b equal to the number n of nodes it is the maximum cut problem. we present polynomial time randomized approximation algorithms with non trivial performance guarantees for its solution. the approximation results are obtained by extending the methodology used by y. ye for max bisection and by combining this technique with another one that uses the algorithm of goemans and williamson for the maximum cut problem. when b is equal to zero the approximation ratio achieved coincides with the one obtained by y. ye; otherwise it is always above this value and tends to the value obtained by goemans and williamson as b approaches the number n of nodes.
extracting constrained 2-interval subsets in 2-interval sets. 2-interval sets were used in [s. vialette, pattern matching over 2-intervals sets, in: proc. 13th annual symposium combinatorial pattern matching, cpm 2002, in: lecture notes in computer science, vol. 2373, springer-verlag, 2002, pp. 53-63; s. vialette, on the computational complexity of 2-interval pattern matching, theoret. comput. sci. 312 (2-3) (2004) 223-249] for establishing a general representation for macroscopic describers of rna secondary structures. in this context, we have a 2-interval for each legal local fold in a given rna sequence, and a constrained pattern made of disjoint 2-intervals represents a putative rna secondary structure. we focus here on the problem of extracting a constrained pattern in a set of 2-intervals. more precisely, given a set of 2-intervals and a model r describing if two disjoint 2-intervals in a solution can be in precedence order (<), be allowed to nest () and/or be allowed to cross (), we consider the problem of finding a maximum cardinality subset of disjoint 2-intervals such that any two 2-intervals in agree with r. the different combinations of restrictions on model r alter the computational complexity of the problem, and need to be examined separately. in this paper, we improve the time complexity of [s. vialette, on the computational complexity of 2-interval pattern matching, theoret. comput. sci. 312 (2-3) (2004) 223-249] for model r={} by giving an optimal o(nlogn) time algorithm, where n is the cardinality of the 2-interval set . we also give a graph-like relaxation for model r={,} that is solvable in time. finally, we prove that the considered problem is np-complete for model r={<,} even for same-length intervals, and give a fixed-parameter tractability result based on the crossing structure of .
optimal parameters for search using a barrier tree markov model. the performance, on a given problem, of search heuristics such as simulated annealing and descent with variable mutation can be described as a function of, and optimised over, the parameters of the heuristic (e.g. the annealing or mutation schedule). we describe heuristics as markov processes; the search for optimal parameters is then rendered feasible by the use of level-accessible barrier trees for state amalgamation. results are presented for schedules minimising ''where-you-are'' and ''best-so-far'' cost, over binary perceptron, spin-glass and max-sat problems. we also compute first-passage time for several ''toy heuristics'', including constant-temperature annealing and fixed-rate mutation search.
the magnus-derek game. we introduce a new combinatorial game between two players: magnus and derek. initially, a token is placed at position 0 on a round table with n positions. in each round of the game magnus chooses the number of positions for the token to move, and derek decides in which direction, + (clockwise) or - (counterclockwise), the token will be moved. magnus aims to maximize the total number of positions visited during the course of the game, while derek aims to minimize this quantity. we define f^*(n) to be the eventual size of the set of visited positions when both players play optimally. we prove a closed form expression for f^*(n) in terms of the prime factorization of n, and provide algorithmic strategies for magnus and derek to meet this bound. we note the relevance of the game for a mobile agent exploring a ring network with faulty sense of direction, and we pose variants of the game for future study.
complexity theory for splicing systems. this paper proposes a notion of time complexity in splicing systems. the time complexity of a splicing system at length n is defined to be the smallest integer t such that all the words of the system having length n are produced within t rounds. for a function t from the set of natural numbers to itself, the class of languages with splicing system time complexity t(n) is denoted by spltime[f(n)]. this paper presents fundamental properties of spltime and explores its relation to classes based on standard computational models, both in terms of upper bounds and in terms of lower bounds. as to upper bounds, it is shown that for any function t(n)spltime[t(n)] is included in 1-nspace[t(n)]; i.e., the class of languages accepted by a t(n)-space-bounded non-deterministic turing machine with one-way input head. expanding on this result, it is shown that 1-nspace[t(n)] is characterized in terms of splicing systems: it is the class of languages accepted by a t(n)-space uniform family of extended splicing systems having production time o(t(n)) with the additional property that each finite automaton appearing in the family of splicing systems has at most a constant number of states. as to lower bounds, it is shown that for all functions t(n)>=logn, all languages accepted by a pushdown automaton with maximal stack height t(|x|) for a word x are in spltime[t(n)]. from this result, it follows that the regular languages are in spltime[o(logn)] and that the context-free languages are in spltime[o(n)].
single machine scheduling with release dates and job delivery to minimize the makespan. in single machine scheduling with release dates and job delivery, jobs are processed on a single machine and then delivered by a capacitated vehicle to a single customer. only one vehicle is employed to deliver these jobs. the vehicle can deliver at most c jobs at a shipment. the delivery completion time of a job is defined as the time at which the delivery batch containing the job is delivered to the customer and the vehicle returns to the machine. the objective is to minimize the makespan, i.e., the maximum delivery completion time of the jobs. when preemption is allowed to all jobs, we give a polynomial-time algorithm for this problem. when preemption is not allowed, we show that this problem is strongly np-hard for each fixed c>=1. we also provide a 53-approximation algorithm for this problem, and the bound is tight.
bisimulation relations for weighted automata. bisimulation is a well known equivalence relation for discrete event systems and has been extended to probabilistic and stochastic systems. this paper introduces a general definition of bisimulation which can be applied to finite automata where weights and labels are assigned to transitions. it is shown that this general view contains several known bisimulations as special cases and defines naturally equivalences for different classes of models. apart from the well known forward bisimulation, also backward bisimulation is introduced and it is shown that both types of bisimulation preserve different types of results. furthermore it is shown that forward and backward bisimulation are congruences according to commonly known composition operations for automata.
the 2nd-order conditional 3-coloring of claw-free graphs. a 2nd-order conditionalk-coloring of a graph g is a proper k-coloring of the vertices of g such that every vertex of degree at least 2 in g will be adjacent to vertices with at least 2 different colors. the smallest number k for which a graph g can have a 2nd-order conditional k-coloring is the 2nd-order conditional chromatic number, denoted by @g"d(g). in this paper, we investigate the 2nd-order conditional 3-colorings of claw-free graphs. first, we prove that it is np-complete to determine if a claw-free graph with maximum degree 3 is 2nd-order conditionally 3-colorable. second, by forbidding a kind of subgraphs, we find a reasonable subclass of claw-free graphs with maximum degree 3, for which the 2nd-order conditionally 3-colorable problem can be solved in linear time. third, we give a linear time algorithm to recognize this subclass of graphs, and a linear time algorithm to determine whether it is 2nd-order conditionally 3-colorable. we also give a linear time algorithm to color the graphs in the subclass by 3 colors.
predecessor existence problems for finite discrete dynamical systems. we study the predecessor existence problem for finite discrete dynamical systems. given a finite discrete dynamical system s and a configuration c, the predecessor existence (or pre) problem is to determine whether there is a configuration c^' such that s has a transition from c^' to c. in addition to the decision version, we also study the following variants: the #-predecessor existence (or #pre) problem-counting the number of predecessors, the unique-predecessor existence (or upre) problem-deciding whether there is a unique predecessor and the ambiguous-predecessor existence (or apre) problem-given a configuration c and a predecessor c^' of c, deciding whether there is a different predecessor c^'' of c. general techniques are presented for simultaneously characterizing the computational complexity of the pre problem and its three variants. our hardness results are based on the concept of simultaneous reductions: single transformations that can be used to simultaneously prove the hardness of the different variants of the pre problem for their respective complexity classes. our easiness results are based on dynamic programming and they extend the previous results on pre problem for one-dimensional cellular automata. the hardness results together with the easiness results provide a tight separation between easy and hard instances. further, the results imply similar bounds for other classes of finite discrete dynamical systems including discrete hopfield and recurrent neural networks, concurrent state machines, systolic networks and one- and two-dimensional cellular automata. our results extend the earlier results of green, sutner and orponen on the complexity of the predecessor existence problem and its variants.
the complexity of fixed point models of trust in distributed networks. in this paper we consider the complexity of some problems arising in a fixed point model of trust in large-scale distributed systems, based on the notion of trust structures introduced by carbone, nielsen and sassone; a set of trust levels with two distinct partial orderings. in the trust model, a global trust state exists as the least fixed point of a collection of local policy functions of nodes in the network. we first show that it is possible to efficiently compute a single component of the global trust state using a simple, robust and totally asynchronous distributed algorithm. we complement this with a lower bound which shows that, if the policies are unrestricted then communication and time linear in the number of distinct trust levels is required in the worst case. we then consider the notion of distributed proof carrying requests previously introduced as a means of safely approximating the global trust state without computing its exact value. we present a new result that enables us to give a continuum of proof carrying protocols, the previously known protocol being one extreme of this. the theorem allows us to generate protocols that can prove all possible trust values (previously, it was only possible to prove trust values representing 'not too much bad behaviour'). however, we show that such a general protocol may not be efficient - it is np-hard to construct an approximately minimal size proof in our model, and in the worst case the nodes must communicate almost as much data as if they were to compute the global trust state from scratch. the implications of our negative results are that it may be necessary to restrict the policy language in order to efficiently implement a fixed point model of trust in a distributed network.
formalising java rmi with explicit code mobility. this paper presents an object-oriented, java-like core language with primitives for distributed programming and explicit code mobility. we apply our formulation to prove the correctness of several optimisations for distributed programs. our language captures crucial but often hidden aspects of distributed object-oriented programming, including object serialisation, dynamic class downloading and remote method invocation. it is defined in terms of an operational semantics that concisely models the behaviour of distributed programs using machinery from calculi of mobile processes. type safety is established using invariant properties for distributed runtime configurations. we argue that primitives for explicit code mobility offer a programmer fine-grained control of type-safe code distribution, which is crucial for improving the performance and safety of distributed object-oriented applications.
a formal semantics for protocol narrations. protocol narrations are a widely-used informal means to describe, in an idealistic manner, the functioning of cryptographic protocols as a single intended sequence of cryptographic message exchanges among the protocol's participants. protocol narrations have also been informally ''turned into'' a number of formal protocol descriptions, e.g., using the spi-calculus. in this paper, we propose a direct formal operational semantics for protocol narrations that fixes a particular and, as we argue, well-motivated interpretation on how the involved protocol participants are supposed to execute. based on this semantics, we explain and formally justify a natural and precise translation of narrations into spi-calculus. an optimised translation has been implemented in ocaml, and we report on case studies that we have carried out using the tool.
a semantic framework for open processes. we propose a general methodology for analysing the behaviour of open systems modelled as coordinators, i.e., open terms of suitable process calculi. a coordinator is understood as a process with holes or placeholders where other coordinators and components (i.e., closed terms) can be plugged in, thus influencing its behaviour. the operational semantics of coordinators is given by means of a symbolic transition system, where states are coordinators and transitions are labeled by spatial/modal formulae expressing the potential interaction that plugged components may enable. behavioural equivalences for coordinators, like strong and weak bisimilarities, can be straightforwardly defined over such a transition system. different from other approaches based on universal closures, i.e., where two coordinators are considered equivalent when all their closed instances are equivalent, our semantics preserves the openness of the system during its evolution, thus allowing dynamic instantiation to be accounted for in the semantics. to further support the adequacy of the construction, we show that our symbolic equivalences provide correct approximations of their universally closed counterparts, coinciding with them over closed components. for process calculi in suitable formats, we show how tractable symbolic semantics can be defined constructively using unification.
a framework for analyzing probabilistic protocols and its application to the partial secrets exchange. we propose a probabilistic variant of the pi-calculus as a framework to specify randomized security protocols and their intended properties. in order to express and verify the correctness of the protocols, we develop a probabilistic version of the testing semantics. we then illustrate these concepts on an extended example: the partial secret exchange, a protocol which uses a randomized primitive, the oblivious transfer, to achieve fairness of information exchange between two parties.
a program logic for resources. we introduce a reasoning infrastructure for proving statements about resource consumption in a fragment of the java virtual machine language (jvml). the infrastructure is based on a small hierarchy of program logics, with increasing levels of abstraction: at the top there is a type system for a high-level language that encodes resource consumption. the infrastructure is designed to be used in a proof-carrying code (pcc) scenario, where mobile programs can be equipped with formal evidence that they have predictable resource behaviour. this article focuses on the core logic in our infrastructure, a vdm-style program logic for partial correctness, which can make statements about resource consumption alongside functional behaviour. we establish some important results for this logic, including soundness and completeness with respect to a resource-aware operational semantics for the jvml. we also present a second logic built on top of the core logic, which is used to express termination; it too is shown to be sound and complete. we then outline how high-level language type systems may be connected to these logics. the entire infrastructure has been formalized in isabelle/hol, both to enhance the confidence in our meta-theoretical results, and to provide a prototype implementation for pcc. we give examples to show the usefulness of this approach, including proofs of resource bounds on code resulting from compiling high-level functional programs.
concurrent reachability games. we consider concurrent two-player games with reachability objectives. in such games, at each round, player 1 and player 2 independently and simultaneously choose moves, and the two choices determine the next state of the game. the objective of player 1 is to reach a set of target states; the objective of player 2 is to prevent this. these are zero-sum games, and the reachability objective is one of the most basic objectives: determining the set of states from which player 1 can win the game is a fundamental problem in control theory and system verification. there are three types of winning states, according to the degree of certainty with which player 1 can reach the target. from type-1 states, player 1 has a deterministic strategy to always reach the target. from type-2 states, player 1 has a randomized strategy to reach the target with probability 1. from type-3 states, player 1 has for every real @e>0 a randomized strategy to reach the target with probability greater than 1-@e. we show that for finite state spaces, all three sets of winning states can be computed in polynomial time: type-1 states in linear time, and type-2 and type-3 states in quadratic time. the algorithms to compute the three sets of winning states also enable the construction of the winning and spoiling strategies.
open bisimulation, revisited. in the context of the @p-calculus, open bisimulation is prominent and popular due to its congruence properties and its easy implementability. motivated by the attempt to generalise it to the spi-calculus, we offer a new, more refined definition and show how far it coincides with the original one.
separation of synchronous and asynchronous communication via testing. one of the early results concerning the asynchronous @p-calculus which significantly contributed to its popularity is the capability of encoding the output prefix of the (choiceless) @p-calculus in a natural and elegant way. encodings of this kind were proposed by honda and tokoro, by nestmann and (independently) by boudol. we investigate whether the above encodings preserve de nicola and hennessy's testing semantics. in this sense, it turns out that, under some general conditions, no encoding of the output prefix is able to preserve the must testing. this negative result is due to (a) the non-atomicity of the sequences of steps which are necessary in the asynchronous @p-calculus to mimic synchronous communication, and (b) testing semantics' sensitivity to divergence.
causality versus true-concurrency. category theory has been successfully employed to structure the confusing set-up of models and equivalences for concurrency: winskel and nielsen have related the standard models via adjunctions and (co)reflections while joyal et al. have defined an abstract notion of equivalence, known as open map bisimilarity. one model has not been integrated into this framework: the causal trees of darondeau and degano. here we fill this gap. in particular, we show that there is an adjunction from causal trees to event structures, which we bring to light via a mediating model, that of event trees. further, we achieve an open map characterization of history preserving bisimilarity: the latter is captured by the natural instantiation of the abstract bisimilarity for causal trees.
the size of higman-haines sets. we show that for the family of church-rosser languages the higman-haines sets, which are the sets of all scattered subwords of a given language and the sets of all words that contain some word of a given language as a scattered subword, cannot be effectively constructed, although both these sets are regular for any language. this nicely contrasts the result on the effectiveness of the higman-haines sets for the family of context-free languages. the non-effectiveness is based on a non-recursive trade-off result between the language description mechanism of church-rosser languages and the corresponding higman-haines sets, which in turn is also valid for all supersets of the language family under consideration, and in particular for the family of recursively enumerable languages. finally for the family of regular languages we prove an upper and a matching lower bound on the size of the higman-haines sets in terms of nondeterministic finite automata.