waashk/dblp huggingface dataset:
two-group knapsack game. this paper presents a ''two-group knapsack game''. a number of investors colligate into two groups to bid on a common pool of potential projects. each investor has his/her own budget limit and a cost estimation for undertaking each possible project. each group represents a power by its market share. associated with each project, there is a potential profit that can be realized. investors in the same group hold an internal agreement of putting the group's collective interest ahead of the individual's interest and not bidding on the same project by more than one investor in the group. the profit of a particular project can be wholly taken by the sole bidder or shared proportionally by two bidders in different groups according to their group power. the objective of each group may be based not only on its own group profit but also on the other group's profit. assuming that each investor acts in a selfish manner with the best response to optimize its group's objective subject to the budget constraint, we show that a pure nash equilibrium exists under certain conditions. we also have some interesting findings of the ''price of anarchy'' (the ratio of the worst nash equilibrium to the social optimum) associated with a simplified version of the two-group knapsack game with three investors.
semigroup automata with rational initial and terminal sets. we consider a natural extension of the usual definition of m-automata (also known as extended automata or valence automata) which permits the automaton to utilise more of the structure of each monoid, and additionally allows us to define s-automata for s an arbitrary semigroup. in the monoid case, the resulting automata are equivalent to the valence automata with rational target sets which arise in the theory of regulated rewriting systems. we study these automata in the case where the register semigroup is completely simple or completely 0-simple, obtaining a complete characterisation of the classes of languages corresponding to such semigroups, in terms of their maximal subgroups. in the process, we obtain a number of results about rational subsets of rees matrix semigroups which are likely to be of independent interest.
pursuing a fast robber on a graph. the cops and robbers game as originally defined independently by quilliot and by nowakowski and winkler in the 1980s has been much studied, but very few results pertain to the algorithmic and complexity aspects of it. in this paper we prove that computing the minimum number of cops that are guaranteed to catch a robber on a given graph is np-hard and that the parameterized version of the problem is w[2]-hard; the proof extends to the case where the robber moves s time faster than the cops. we show that on split graphs, the problem is polynomially solvable if s=1 but is np-hard if s=2. we further prove that on graphs of bounded cliquewidth the problem is polynomially solvable for s@?2. finally, we show that for planar graphs the minimum number of cops is unbounded if the robber is faster than the cops.
analysis of particle interaction in particle swarm optimization. in this paper, we analyze the behavior of particle swarm optimization (pso) on the facet of particle interaction. we firstly propose a statistical interpretation of particle swarm optimization in order to capture the stochastic behavior of the entire swarm. based on the statistical interpretation, we investigate the effect of particle interaction by focusing on the social-only model and derive the upper and lower bounds of the expected particle norm. accordingly, the lower and upper bounds of the expected progress rate on the sphere function are also obtained. furthermore, the sufficient and necessary condition for the swarm to converge is derived to demonstrate the pso convergence caused by the effect of particle interaction.
codes and maximal monoids. some results are given on maximal monoids in the language of the soficsystem generated by a finite code of words.
on the problem of freeness of multiplicative matrix semigroups. the following problem looking as a high-school exercise hides an unexpected difficulty. do the matrices a=(2003)andb=(3505) satisfy any nontrivial equation with the multiplication symbol only? this problem was mentioned as open in cassaigne et al. [j. cassaigne, t. harju, j. karhumaki, on the undecidability of freeness of matrix semigroups, internat. j. algebra comput. 9 (3-4) (1999) 295-305] and in a book by blondel et al. [v. blondel, j. cassaigne, j. karhumaki, problem 10.3: freeness of multiplicative matrix semigroups, in: v. blondel, a. megretski (eds.), unsolved problems in mathematical systems and control theory, princeton university press, 2004, pp. 309-314] as an intriguing instance of a natural computational problem of deciding whether a given finitely generated semigroup of 2x2 matrices is free. in this paper we present a new partial algorithm for the latter which, in particular, easily finds that the following equation ab^1^0a^2ba^2ba^1^0=b^2a^6b^2a^2bababa^2b^2a^2bab^2 holds for the matrices above. our algorithm turns out quite practical and allows us to settle also other related open questions posed in the mentioned article.
a hierarchical strongly aperiodic set of tiles in the hyperbolic plane. we give a new construction of strongly aperiodic set of tiles in h^2, exhibiting a kind of hierarchical structure, simplifying the central framework of margenstern's proof that the domino problem is undecidable in the hyperbolic plane (margenstern (2008) [16]).
analyzing the dynamics of stigmergetic interactions through pheromone games. the concept of stigmergy provides a simple framework for interaction and coordination in multi-agent systems. however, determining the global system behavior that will arise from local stigmergetic interactions is a complex problem. in this paper we propose to use game theory to analyze stigmergetic interactions. we show that a system where agents coordinate by sharing local pheromone information can be approximated by a limiting pheromone game in which different pheromone vectors represent player strategies. this game view allows us to use established methods and solution concepts from game theory to describe the properties of stigmergy based systems. our goal is to provide a new framework to aid in the understanding and design of pheromone interactions. we demonstrate how we can use this system to determine the long term system behavior of a simple pheromone model, by analyzing the convergence properties of the pheromone update rule in the approximating game. we also apply this model to cases where multiple colonies of agents concurrently optimize different objectives. in this case a limiting colony game can be linked to colony level interactions to characterize the global system behavior.
an exact correspondence between a typed pi-calculus and polarised proof-nets. this paper presents an exact correspondence in typing and dynamics between polarised linear logic and a typed @p-calculus based on io-typing. the respective incremental constraints, one on geometric structures of proof-nets and one based on types, precisely correspond to each other, leading to the exact correspondence of the respective formalisms as they appear in olivier laurent (2003) [27] (for proof-nets) and kohei honda et al. (2004) [24] (for the @p-calculus).
a polynomial solution to the k-fixed-endpoint path cover problem on proper interval graphs. we study a variant of the path cover problem, namely, the k-fixed-endpoint path cover problem, or kpc for short. given a graph g and a subset t of k vertices of v(g), a k-fixed-endpoint path cover of g with respect to t is a set of vertex-disjoint paths p that covers the vertices of g such that the k vertices of t are all endpoints of the paths in p. the kpc problem is to find a k-fixed-endpoint path cover of g of minimum cardinality; note that, if t is empty (or, equivalently, k=0), the stated problem coincides with the classical path cover problem. the kpc problem generalizes some path cover related problems, such as the 1hp and 2hp problems, which have been proved to be np-complete. note that the complexity status for both 1hp and 2hp problems on interval graphs remains an open question (damaschke (1993) [9]). in this paper, we show that the kpc problem can be solved in linear time on the class of proper interval graphs, that is, in o(n+m) time on a proper interval graph on n vertices and m edges. the proposed algorithm is simple, requires linear space, and also enables us to solve the 1hp and 2hp problems on proper interval graphs within the same time and space complexity.
on the undecidability of the limit behavior of cellular automata. cellular automata (ca) are discrete dynamical systems and an abstract model of parallel computation. the limit set of a cellular automaton is its maximal topological attractor. a well-known result, due to kari, says that all nontrivial properties of limit sets are undecidable. in this paper we consider the properties of limit set dynamics, i.e. properties of the dynamics of ca restricted to their limit sets. there can be no equivalent of kari's theorem for limit set dynamics. anyway we show that there is a large class of undecidable properties of limit set dynamics, namely all properties of limit set dynamics which imply stability or the existence of a unique subshift attractor. as a consequence we have that it is undecidable whether the cellular automaton map restricted to the limit set is the identity map and whether it is closing, injective, expansive, positively expansive and transitive.
query-based verification of qualitative trends and oscillations in biochemical systems. we investigate the application of query-based verification to the analysis of behavioural trends of stochastic models of biochemical systems. we derive temporal logic properties which address specific behavioural questions, such as the likelihood for a species to reach a peak/deadlock state, or to exhibit monotonic/oscillatory trends. we introduce a specific modelling convention through which stochastic models of biochemical systems are made suitable to verification of the behavioural queries we define. based on the queries we identify, we define a classification procedure which, given a stochastic model, allows for identifying meaningful qualitative behavioural trends. we illustrate the proposed query-based classification on a number of simple abstract models of biochemical systems.
optimal bounds on finding fixed points of contraction mappings. the banach fixed-point theorem states that a contraction mapping on a complete metric space has a unique fixed point. given an oracle access to a finite metric space (m,d) and a contraction mapping f:m->m on it, we show that the fixed point of f can be found with an expected o(|m|) oracle queries. we also show that every randomized algorithm for finding a fixed point must make an expected @w(|m|) oracle queries to (m,d) and f for some finite metric space (m,d) and some contraction mapping f:m->m on it. as a generalization of the banach fixed-point theorem, the caristi-kirk fixed-point theorem gives weaker conditions on (m,d) and f guaranteeing the existence of a fixed point of f. we show that every randomized algorithm that finds a fixed point must make the expected @w(|m|) oracle queries to (m,d) and f for some finite metric space (m,d) and some function f:m->m satisfying the conditions of the caristi-kirk fixed-point theorem.
gödel's system tau revisited. the linear lambda calculus, where variables are restricted to occur in terms exactly once, has a very weak expressive power: in particular, all functions terminate in linear time. in this paper we consider a simple extension with natural numbers and a restricted iterator: only closed linear functions can be iterated. we show properties of this linear version of godel's tusing a closed reduction strategy, and study the class of functions that can be represented. surprisingly, this linear calculus offers a huge increase in expressive power over previous linear versions of t, which are 'closed at construction' rather than 'closed at reduction'. we show that a linear twith closed reduction is as powerful as t.
stability analysis of the reproduction operator in bacterial foraging optimization. in his seminal paper published in 2002, passino pointed out how individual and groups of bacteria forage for nutrients and how to model it as a distributed optimization process, which he named the bacterial foraging optimization algorithm (bfoa). one of the major operators of bfoa is the reproduction phenomenon of virtual bacteria, each of which models one trial solution of the optimization problem. during reproduction, the least healthy bacteria (with a lower accumulated value of the objective function in one chemotactic lifetime) die and the other healthier bacteria each split into two, which then starts exploring the search place from the same location. the phenomenon has a direct analogy with the selection mechanism of classical evolutionary algorithms. this paper attempts to model reproduction as a dynamics and then analyses the stability of the reproductive system very near to an equilibrium point, which in this case is an isolated optimum. it also finds conditions under which a stable reproduction event can take place, to direct a worse bacterium towards a better one. our analysis reveals that a stable reproduction event contributes to the quick convergence of the bacterial population near optima.
hybrid dynamics of stochastic programs. we provide stochastic concurrent constraint programming (sccp), a stochastic process algebra based on ccp, with a semantics in terms of hybrid automata. we associate with each sccp program both a stochastic and a non-deterministic hybrid automaton. then, we compare such automata with the standard stochastic semantics (given by a continuous time markov chain) and the one based on ordinary differential equations, obtained by a fluid-flow approximation technique. we discuss in detail two case studies: repressilator and the circadian clock, with particular regard to the robustness exhibited by the different semantic models and to the effect of discreteness in dynamical evolution of such systems.
using abstract interpretation to add type checking for interfaces in java bytecode verification. java interface types support multiple inheritance. because of this, the standard bytecode verifier ignores them, since it is not able to model the class hierarchy as a lattice. thus, type checks on interfaces are performed at run time. we propose a verification methodology that removes the need for run-time checks. the methodology consists of: (1) an augmented verifier that is very similar to the standard one, but is also able to check for interface types in most cases; (2) for all other cases, a set of additional simpler verifiers, each one specialized for a single interface type. we obtain these verifiers in a systematic way by using abstract interpretation techniques. finally, we describe an implementation of the methodology and evaluate it on a large set of benchmarks.
a trajectory-based strict semantics for program slicing. we define a program semantics that is preserved by dependence-based slicing algorithms. it is a natural extension, to non-terminating programs, of the semantics introduced by weiser (which only considered terminating ones) and, as such, is an accurate characterisation of the semantic relationship between a program and the slice produced by these algorithms. unlike other approaches, apart from weiser's original one, it is based on strict standard semantics which models the 'normal' execution of programs on a von neumann machine and, thus, has the advantage of being intuitive. this is essential since one of the main applications of slicing is program comprehension. although our semantics handles non-termination, it is defined wholly in terms of finite trajectories, without having to resort to complex, counter-intuitive, non-standard models of computation. as well as being simpler, unlike other approaches to this problem, our semantics is substitutive. substitutivity is an important property because it greatly enhances the ability to reason about correctness of meaning-preserving program transformations such as slicing.
probabilistic anonymity via coalgebraic simulations. there is a growing concern about anonymity and privacy on the internet, resulting in lots of work on formalization and verification of anonymity. in particular, the importance of probabilistic aspects of anonymity has recently been highlighted by many authors. several different notions of ''probabilistic anonymity'' have been studied so far, but proof methods for such probabilistic notions have not yet been elaborated. in this paper we introduce a simulation-based proof method for one notion of probabilistic anonymity introduced by bhargava and palamidessi, called strong probabilistic anonymity. the method is a probabilistic adaptation of the one by kawabe, sakurada et al. for non-deterministic anonymity; anonymity of a protocol is proved by finding a forward/backward simulation between certain automata. for the jump from non-determinism to probability we exploit a generic, coalgebraic theory of traces and simulations developed by hasuo, jacobs and sokolova. in particular, an appropriate notion of probabilistic simulation is obtained as an instantiation of the generic definition, for which soundness theorem comes for free. additionally, we show how we can use a similar idea to verify a weaker notion of probabilistic anonymity called probable innocence.
criteria for the matrix equivalence of words. this paper investigates the criteria for deciding whether two words are matrix equivalent. certain upper diagonal matrices, generally referred to as the parikh matrices, have been widely investigated because of their usefulness in computing the numbers of subword occurrences and thereby characterizing words by numbers. however, apart from the binary alphabet, not much is known about the properties of the matrix equivalent words, that is, words possessing the same matrix. the paper investigates both the general criteria, as well as the criteria valid in natural special cases. an exhaustive solution is obtained for ternary alphabets.
distributional analysis of swaps in quick select. we investigate the number of swaps made by quick select (a variant of quick sort for finding order statistics) to find an element with a randomly selected rank under realistic partition algorithms such as lomuto's or hoare's. this kind of grand average provides a smoothing over all individual distributions for specific fixed order statistics. the grand distribution for the number of swaps (when suitably scaled) is a perpetuity (a sum of products of independent mixed continuous random variables supported on the interval (0,1)). the tool for this proof is contraction in the wasserstein metric space, and identifying the limit as the fixed-point solution of a distributional equation. the same methodology carries over when quick select is commissioned to find an extremal order statistic (of a relatively small or relatively large rank) and the results are of similar nature. it is one of our purposes to show that analysis under different partition algorithms leads to different results.
a self-stabilizing algorithm for cut problems in synchronous networks. consider a synchronized distributed system where each node can only observe the state of its neighbors. such a system is called self-stabilizing if it reaches a stable global state in a finite number of rounds. allowing two different states for each node induces a cut in the graph. in each round, every node decides whether it is (locally) satisfied with the current cut. afterwards all unsatisfied nodes change sides independently with a fixed probability p. using different notions of satisfaction enables the computation of maximal and minimal cuts, respectively. we analyze the expected time until such cuts are reached on several graph classes and study the impact of the parameter p and the initial cut.
the pos/neg-weighted 1-median problem on tree graphs with subtree-shaped customers. in this paper we consider the pos/neg-weighted median problem on a tree graph where the customers are modeled as continua subtrees. we address the discrete and continuous models, i.e., the subtrees' boundary points are all vertices, or possibly inner points of an edge, respectively. we consider two different objective functions. if we minimize the overall sum of the minimum weighted distances of the subtrees from the facilities, there exists an optimal solution satisfying a generalized vertex optimality property, e.g., there is an optimal solution such that all facilities are located at vertices or the boundary points of the subtrees. based on this property we devise a polynomial time algorithm for the pos/neg-weighted 1-median problem on a tree with subtree-shaped customers.
preface. there have been a number of letters included in the forum of the communications of the association for computing machinery (acm) over the last two years which discuss various types of meetings with which the acm might or should become involved. a sizeable group of individuals have felt that, despite the large number of meetings sponsored by the acm and their sigs and sics as well as by other organizations, an appreciable part of the computer science community is not being adequately considered. much of the impetus for this type of a consideration was given originally by professor preston hammer, chairman of the department of computer science at pennsylvania state university, in a letter which he wrote in the november 1971 forum of the acm communications.
detecting synchronisation of biological oscillators by model checking. we define a subclass of timed automata, called oscillator timed automata, suitable to model biological oscillators. coupled biological oscillators may synchronise, as emerging behaviour, after a period of time in which they interact through physical or chemical means. we introduce a parametric semantics for their interaction that is general enough to capture the behaviour of different types of oscillators. we instantiate it both to the kuramoto model, a model of synchronisation based on smooth interaction, and to the peskin model of pacemaker cells in the heart, a model of synchronisation based on pulse interaction. we also introduce a logic, biological oscillators synchronisation logic (bosl), that is able to describe collective synchronisation properties of a population of coupled oscillators. a model checking algorithm is proposed for the defined logic and it is implemented in a model checker. the model checker can be used to detect synchronisation properties of a given population of oscillators. this tool might be the basic step towards the generation of suitable techniques to control and regulate the behaviour of coupled oscillators in order to ensure the reachability of synchronisation.