waashk/dblp huggingface dataset:
all-to-all personalized exchange in generalized shuffle-exchange networks. an all-to-all communication algorithm is said to be optimal if it has the smallest communication delay. previous all-to-all personalized exchange algorithms are mainly for hypercube, mesh, and torus. in yang and wang (2000) [13], yang and wang proved that a multistage interconnection network (min) is a better choice for implementing all-to-all personalized exchange and they proposed optimal all-to-all personalized exchange algorithms for mins. in massini (2003) [9], massini proposed a new optimal algorithm for mins, which is independent of the network topology. do notice that the algorithms in [9] and [13] work only for mins with the unique path property (meaning that there is a unique path between each pair of source and destination) and satisfying n=2^n, in which n is the number of processors, 2 means all the switches are of size 2x2, and n is the number of stages. in padmanabhan (1991) [10], padmanabhan proposed the generalized shuffle-exchange network (gsen), which is a generalization of the shuffle-exchange network. since a gsen does not have the unique path property, the algorithms in [9] and [13] cannot be used. the purpose of this paper is to consider the all-to-all personalized exchange problem in gsens. an optimal algorithm and several bounds will be proposed.
error-repair parsing schemata. robustness, the ability to analyze any input regardless of its grammaticality, is a desirable property for any system dealing with unrestricted natural language text. error-repair parsing approaches achieve robustness by considering ungrammatical sentences as corrupted versions of valid sentences. in this article we present a deductive formalism, based on sikkel's parsing schemata, that can be used to define and relate error-repair parsers and study their formal properties, such as correctness. this formalism allows us to define a general transformation technique to automatically obtain robust, error-repair parsers from standard non-robust parsers. if our method is applied to a correct parsing schema verifying certain conditions, the resulting error-repair parsing schema is guaranteed to be correct. the required conditions are weak enough to be fulfilled by a wide variety of popular parsers used in natural language processing, such as cyk, earley and left-corner.
deterministic solutions to qsat and q3sat by spiking neural p systems with pre-computed resources. in this paper we continue previous studies on the computational efficiency of spiking neural p systems, under the assumption that some pre-computed resources of exponential size are given in advance. specifically, we give a deterministic solution for each of two well known pspace-complete problems: qsat and q3sat. in the case of qsat, the answer to any instance of the problem is computed in a time which is linear with respect to both the number n of boolean variables and the number m of clauses that compose the instance. as for q3sat, the answer is computed in a time which is at most cubic in the number n of boolean variables.
single-machine scheduling under the job rejection constraint. in this paper, we consider single-machine scheduling problems under the job rejection constraint. a job is either rejected, in which case a rejection penalty has to be paid, or accepted and processed on the single machine. however, the total rejection penalty of the rejected jobs cannot exceed a given upper bound. the objective is to find a schedule such that a given criterion f is minimized, where f is a non-decreasing function on the completion times of the accepted jobs. we analyze the computational complexities of the problems for distinct objective functions and present pseudo-polynomial-time algorithms. in addition, we provide a fully polynomial-time approximation scheme for the makespan problem with release dates. for other objective functions related to due dates, we point out that there is no approximation algorithm with a bounded approximation ratio.
on convex complexity measures. khrapchenko's classical lower bound n^2 on the formula size of the parity function f can be interpreted as designing a suitable measure of sub-rectangles of the combinatorial rectangle f^-^1(0)xf^-^1(1). trying to generalize this approach we arrived at the concept of convex measures. we prove the negative result that convex measures are bounded by o(n^2) and show that several measures considered for proving lower bounds on the formula size are convex. we also prove quadratic upper bounds on a class of measures that are not necessarily convex.
combinatorics of labelling in higher-dimensional automata. the main idea for interpreting concurrent processes as labelled precubical sets is that a given set of n actions running concurrently must be assembled to a labelled n-cube, in exactly one way. the main ingredient is the non-functorial construction called the labelled directed coskeleton. it is defined as a subobject of the labelled coskeleton, the latter coinciding in the unlabelled case with the right adjoint to the truncation functor. this non-functorial construction is necessary since the labelled coskeleton functor of the category of labelled precubical sets does not fulfil the above requirement. we prove in this paper that it is possible to force the labelled coskeleton functor to be well behaved by working with labelled transverse symmetric precubical sets. moreover, we prove that this solution is the only one. a transverse symmetric precubical set is a precubical set equipped with symmetry maps and with a new kind of degeneracy map called transverse degeneracy. finally, we also prove that the two settings are equivalent from a directed algebraic topological viewpoint. to illustrate, a new semantics of the calculus of communicating systems (ccs), equivalent to the old one, is given.
runtime analysis of a binary particle swarm optimizer. we investigate the runtime of a binary particle swarm optimizer (pso) for optimizing pseudo-boolean functions f:{0,1}^n->r. the binary pso maintains a swarm of particles searching for good solutions. each particle consists of a current position from {0,1}^n, its own best position and a velocity vector used in a probabilistic process to update its current position. the velocities for a particle are then updated in the direction of its own best position and the position of the best particle in the swarm. we present a lower bound for the time needed to optimize any pseudo-boolean function with a unique optimum. to prove upper bounds we transfer a fitness-level argument that is well-established for evolutionary algorithms (eas) to pso. this method is applied to estimate the expected runtime for the class of unimodal functions. a simple variant of the binary pso is considered in more detail for the test function onemax, showing that there the binary pso is competitive to eas. an additional experimental comparison reveals further insights.
a fluid analysis framework for a markovian process algebra. markovian process algebras, such as pepa and stochastic @p-calculus, bring a powerful compositional approach to the performance modelling of complex systems. however, the models generated by process algebras, as with other interleaving formalisms, are susceptible to the state space explosion problem. models with only a modest number of process algebra terms can easily generate so many states that they are all but intractable to traditional solution techniques. previous work aimed at addressing this problem has presented a fluid-flow approximation allowing the analysis of systems which would otherwise be inaccessible. to achieve this, systems of ordinary differential equations describing the fluid flow of the stochastic process algebra model are generated informally. in this paper, we show formally that for a large class of models, this fluid-flow analysis can be directly derived from the stochastic process algebra model as an approximation to the mean number of component types within the model. the nature of the fluid approximation is derived and characterised by direct comparison with the chapman-kolmogorov equations underlying the markov model. furthermore, we compare the fluid approximation with the exact solution using stochastic simulation and we are able to demonstrate that it is a very accurate approximation in many cases. for the first time, we also show how to extend these techniques naturally to generate systems of differential equations approximating higher order moments of model component counts. these are important performance characteristics for estimating, for instance, the variance of the component counts. this is very necessary if we are to understand how precise the fluid-flow calculation is, in a given modelling situation.
partially dynamic efficient algorithms for distributed shortest paths. we study the dynamic version of the distributed all-pairs shortest paths problem. most of the solutions given in the literature for this problem, either (i) work under the assumption that before dealing with an edge operation, the algorithm for the previous operation has to be terminated, that is, they are not able to update shortest paths concurrently, or (ii) concurrently update shortest paths, but their convergence can be very slow (possibly infinite) due to the looping and counting infinity phenomena. in this paper, we propose partially dynamic algorithms that are able to concurrently update shortest paths. we experimentally analyze the effectiveness and efficiency of our algorithms by comparing them against several implementations of the well-known bellman-ford algorithm.
on generic context lemmas for higher-order calculi with sharing. this paper proves several generic variants of context lemmas and thus contributes to improving the tools for observational semantics of deterministic and non-deterministic higher-order calculi that use a small-step reduction semantics. the generic (sharing) context lemmas are provided for may- as well as two variants of must-convergence, which hold in a broad class of extended process- and extended lambda calculi, if the calculi satisfy certain natural conditions. as a guide-line, the proofs of the context lemmas are valid in call-by-need calculi, in call-by-value calculi if substitution is restricted to variable-by-variable and in process calculi like variants of the @p-calculus. for calculi employing beta-reduction using a call-by-name or call-by-value strategy or similar reduction rules, some iu-variants of ciu-theorems are obtained from our context lemmas. our results reestablish several context lemmas already proved in the literature, and also provide some new context lemmas as well as some new variants of the ciu-theorem. to make the results widely applicable, we use a higher-order abstract syntax that allows untyped calculi as well as certain simple typing schemes. the approach may lead to a unifying view of higher-order calculi, reduction, and observational equality.
csp is a retract of ccs. automata theory provides two ways of defining an automaton: either by its transition system, defining its states and events, or by its language, the set of sequences (traces) of events in which it can engage. for many classes of automaton, these forms of definition have been proved equivalent. for example, there is a well-known isomorphism between regular languages and finite deterministic automata. this paper suggests that for (demonically) the non-deterministic automata (as treated in process algebra), the appropriate link between transition systems and languages may be a retraction rather than an isomorphism. a pair of automata, defined in the tradition of ccs by their transition systems, may be compared by a pre-ordering based on some kind of simulation or bisimulation, for example, weak, strong, or barbed. automata defined in the tradition of csp are naturally ordered by set inclusion of their languages (often called refinement); variations in ordering arise from different choices of basic event, including for example, refusals and divergences. in both cases, we characterise a theory by its underlying transition system and its choice of ordering. our treatment is therefore wholly semantic, independent of the syntax and definition of operators of the calculus. we put forward a series of retractions relating the above-mentioned versions of csp to their corresponding ccs transition models. a retraction is an injection that is (with respect to the chosen ordering) monotonic, increasing and idempotent (up to equivalence). it maps the nodes of a transition system of its source theory to those of a system that has been saturated by additional transitions. each retraction will be defined by a transition rule, in the style of operational semantics; the proofs use the familiar technique of co-induction, often abbreviated by encoding in the relational calculus. the aim of this paper is to contribute to unification of theories of reactive system programming. more practical benefits may follow. for example, we justify a method to improve the efficiency of model checking based on simulation. furthermore, we show how model checking of a transition network fits consistently with theorem-proving tools, which reason directly about specifications and designs that are expressed in terms of sets of sequences of observable events.
approximating minimum power covers of intersecting families and directed edge-connectivity problems. given a (directed) graph with costs on the edges, the power of a node is the maximum cost of an edge leaving it, and the power of the graph is the sum of the powers of its nodes. let g=(v,e) be a graph with edge costs {c(e):e@?e} and let k be an integer. we consider problems that seek to find a min-power spanning subgraph g of g that satisfies a prescribed edge-connectivity property. in the min-powerk-edge-outconnected subgraph problem we are given a root r@?v, and require that g contains k pairwise edge-disjoint rv-paths for all v@?v-r. in the min-powerk-edge-connected subgraph problem g is required to be k-edge-connected. for k=1, these problems are at least as hard as the set-cover problem and thus have an @w(ln|v|) approximation threshold. for k=@w(n^@e), they are unlikely to admit a polylogarithmic approximation ratio [15]. we give approximation algorithms with ratio o(kln|v|). our algorithms are based on a more general o(ln|v|)-approximation algorithm for the problem of finding a min-power directed edge-cover of an intersecting set-family; a set-family f is intersecting if x@?y,x@?y@?f for any intersecting x,y@?f, and an edge set i covers f if for every x@?f there is an edge in i entering x.
finding common structured patterns in linear graphs. a linear graph is a graph whose vertices are linearly ordered. this linear ordering allows pairs of disjoint edges to be either preceding (
game authority for robust and scalable distributed selfish-computer systems. distributed algorithm designers often assume that system processes execute the same predefined software. alternatively, when they do not assume that, designers turn to non-cooperative games and seek an outcome that corresponds to a rough consensus when no coordination is allowed. we argue that both assumptions are inapplicable in many real distributed systems, e.g., the internet, and propose designing self-stabilizing and byzantine fault-tolerant distributed game authorities. once established, the game authority can secure the execution of any complete information game. as a result, we reduce costs that are due to the processes' freedom of choice. namely, we reduce the price of malice.
incremental learning with temporary memory. in the inductive inference framework of learning in the limit, a variation of the bounded example memory (bem) language learning model is considered. intuitively, the new model constrains the learner's memory not only in how much data may be stored, but also in how long those data may be stored without being refreshed. more specifically, the model requires that, if the learner commits an example x to memory, and x is not presented to the learner again thereafter, then eventually the learner forgetsx, i.e., eventually x no longer appears in the learner's memory. this model is called temporary example memory (tem) learning. many interesting results concerning the tem-learning model are presented. for example, there exists a class of languages that can be identified by memorizing k+1 examples in the tem sense, but that cannot be identified by memorizing k examples in the bem sense. on the other hand, there exists a class of languages that can be identified by memorizing just one example in the bem sense, but that cannot be identified by memorizing any number of examples in the tem sense. results are also presented concerning the special case of learning classes of infinite languages.
characterizing geometric patterns formable by oblivious anonymous mobile robots. in a system in which anonymous mobile robots repeatedly execute a ''look-compute-move'' cycle, a robot is said to be oblivious if it has no memory to store its observations in the past, and hence its move depends only on the current observation. this paper considers the pattern formation problem in such a system, and shows that oblivious robots can form any pattern that non-oblivious robots can form, except that two oblivious robots cannot form a point while two non-oblivious robots can. therefore, memory does not help in forming a pattern, except for the case in which two robots attempt to form a point. related results on the pattern convergence problem are also presented.
active learning in heteroscedastic noise. we consider the problem of actively learning the mean values of distributions associated with a finite number of options. the decision maker can select which option to generate the next observation from, the goal being to produce estimates with equally good precision for all the options. if sample means are used to estimate the unknown values then the optimal solution, assuming that the distributions are known up to a shift, is to sample from each distribution proportional to its variance. no information other than the distributions' variances is needed to calculate the optimal solution. in this paper we propose an incremental algorithm that asymptotically achieves the same loss as an optimal rule. we prove that the excess loss suffered by this algorithm, apart from logarithmic factors, scales as n^-^3^/^2, which we conjecture to be the optimal rate. the performance of the algorithm is illustrated on a simple problem.
an improved approximation algorithm for the maximum tsp. in this paper, we consider the maximum traveling salesman problem with @c-parameterized triangle inequality for @c@?[12,1), which means that the edge weights in the given complete graph g=(v,e,w) satisfy w(uv)@?@c@?(w(ux)+w(xv)) for all distinct nodes u,x,v@?v. for the maximum traveling salesman problem with @c-parameterized triangle inequality, r. hassin and s. rubinstein gave a constant factor approximation algorithm with polynomial running time, they achieved a performance ratio @c only for @c@?[12,57) in [8], which is the best known result. we design a k@c+1-2@ck@c-approximation algorithm for the maximum traveling salesman problem with @c-parameterized triangle inequality by using a similar idea but very different method to that in [11], where k=min{|c"i||i=1,2,...,m},c"1,c"2,...,c"m is an optimal solution of the minimum cycle cover in g, which is better than the @c-approximation algorithm for almost all @c@?[12,1).
complex network dimension and path counts. large complex networks occur in many applications of computer science. the complex network zeta function and the graph surface function have been used to characterize these networks and to define a dimension for complex networks. in this work we present three new results related to the complex network dimension. first, we show the relationship of the concept to kolmogorov complexity. second, we show how the definition of complex network dimension can be reformulated by defining the concept for a single node, and then defining the complex network dimension as the supremum over all nodes. this makes the concept work better for formally infinite graphs. third, we study interesting parallels to zeta dimension, a notion originally from number theory which has found connections to theoretical computer science. these parallels lead to a deeper insight into the complex network dimension, e.g., the formulation in terms of the entropy and a theorem relating dimension to connectivity.
prequential randomness and probability. this paper studies dawid's prequential framework from the point of view of the algorithmic theory of randomness. our first main result is that two natural notions of randomness coincide. one notion is the prequential version of the measure-theoretic definition due to martin-lof, and the other is the prequential version of the game-theoretic definition due to schnorr and levin. this is another manifestation of the close relation between the two main paradigms of randomness. the algorithmic theory of randomness can be stripped of its algorithmic aspect and still give meaningful results; the measure-theoretic paradigm then corresponds to kolmogorov's measure-theoretic probability and the game-theoretic paradigm corresponds to game-theoretic probability. our second main result is that measure-theoretic probability coincides with game-theoretic probability on all analytic (in particular, borel) sets.
dynamic programming based algorithms for set multicover and multiset multicover problems. given a universe n containing n elements and a collection of multisets or sets over n, the multiset multicover (msmc) problem or the set multicover (smc) problem is to cover all elements at least a number of times as specified in their coverage requirements with the minimum number of multisets or sets. in this paper, we give various exact algorithms for these two problems with or without constraints on the number of times a multiset or set may be chosen. first, we show that the msmc without multiplicity constraints problem can be solved in o^*((b+1)^n|f|) time and polynomial space, where b is the maximum coverage requirement and |f| denotes the total number of given multisets over n. (the o^* notation suppresses a factor polynomial in n.) to our knowledge, this is the first known exact algorithm for the msmc without multiplicity constraints problem. second, by combining dynamic programming and the inclusion-exclusion principle, we can exactly solve the smc without multiplicity constraints problem in o((b+2)^n) time. compared with two recent results, in [q.-s. hua, y. wang, d. yu, f.c.m. lau, set multi-covering via inclusion-exclusion, theoretical computer science, 410 (38-40) (2009) 3882-3892] and [j. nederlof, inclusion exclusion for hard problems, master thesis, utrecht university, the netherlands, 2008], respectively, ours is the fastest exact algorithm for the smc without multiplicity constraints problem. finally, by directly using dynamic programming, we give the first known exact algorithm for the msmc or the smc with multiplicity constraints problem in o((b+1)^n|f|) time and o^*((b+1)^n) space. this algorithm can also be easily adapted as a constructive algorithm for the msmc without multiplicity constraints problem.
average complexity of the jiang-wang-zhang pairwise tree alignment algorithm and of a rna secondary structure alignment algorithm. we prove that the average complexity of the pairwise ordered tree alignment algorithm of jiang, wang and zhang is in o(nm), where n and m stand for the sizes of the two trees, respectively. we show that the same result holds for the average complexity of pairwise comparison of rna secondary structures, using a set of biologically relevant operations.