waashk/dblp huggingface dataset:
dynamic matrix rank. we consider maintaining information about the rank of a matrix under changes of the entries. for nxn matrices, we show an upper bound of o(n^1^.^5^7^5) arithmetic operations and a lower bound of @w(n) arithmetic operations per element change. the upper bound is valid when changing up to o(n^0^.^5^7^5) entries in a single column of the matrix. we also give an algorithm that maintains the rank using o(n^2) arithmetic operations per rank one update. these bounds appear to be the first nontrivial bounds for the problem. the upper bounds are valid for arbitrary fields, whereas the lower bound is valid for algebraically closed fields. the upper bound for element updates uses fast rectangular matrix multiplication, and the lower bound involves further development of an earlier technique for proving lower bounds for dynamic computation of rational functions.
probabilistic and nondeterministic aspects of anonymity. the concept of anonymity comes into play in a wide range of situations, varying from voting and anonymous donations to postings on bulletin boards and sending emails. the protocols for ensuring anonymity often use random mechanisms which can be described probabilistically, while the agents' behavior may be totally unpredictable, irregular, and hence expressible only nondeterministically. formal definitions of the concept of anonymity have been investigated in the past either in a totally nondeterministic framework, or in a purely probabilistic one. in this paper, we investigate a notion of anonymity which combines both probability and nondeterminism, and which is suitable for describing the most general situation in which the protocol and the users can have both probabilistic and nondeterministic behavior. we also investigate the properties of the definition for the particular cases of purely nondeterministic users and purely probabilistic users. we formulate the notions of anonymity in terms of probabilistic automata, and we describe protocols and users as processes in the probabilistic @p-calculus, whose semantics is again based on probabilistic automata. throughout the paper, we illustrate our ideas by using the example of the dining cryptographers.
conservation of some dynamical properties for operations on cellular automata. we consider the family of all the cellular automata (ca) sharing the same local rule but having different memories. this family contains also all ca with memory m@?0 (one-sided ca) which can act both on a^z and on a^n. we study several set theoretical and topological properties for these classes. in particular, we investigate whether the properties of a given ca are preserved when considering the ca obtained by changing the memory of the original one (shifting operation). furthermore, we focus our attention on the one-sided ca acting on a^z, starting from the one-sided ca acting on a^n and having the same local rule (lifting operation). as a particular consequence of these investigations, we prove that the long-standing conjecture [surjectivity @? dense periodic orbits (dpo)] can be restated in several different (but equivalent) ways. furthermore, we give some results on properties conserved under the iteration of the ca global map.
relation between powers of factors and the recurrence function characterizing sturmian words. in this paper we use the relation of the index of an infinite aperiodic word and its recurrence function to give another characterization of sturmian words. as a by-product, we give a new proof of the theorem describing the index of a sturmian word in terms of the continued fraction expansion of its slope. this theorem was independently proved in [a. carpi, a. de luca, special factors, periodicity, and an application to sturmian words, acta inform. 36 (2000) 983-1006] and [d. damanik, d. lenz, the index of sturmian sequences, european j. combin. 23 (2002) 23-29].
backward and forward bisimulation minimization of tree automata. we improve on an existing [p.a. abdulla, j. hogberg, l. kaati, bisimulation minimization of tree automata, international journal of foundations of computer science 18(4) (2007) 699-713] bisimulation minimization algorithm for finite-state tree automata by introducing backward and forward bisimulation and developing minimization algorithms for them. minimization via forward bisimulation is also effective on deterministic tree automata, faster than the previous algorithm, and yields the minimal equivalent deterministic tree automaton. minimization via backward bisimulation generalizes the previous algorithm and can yield smaller automata but is just as fast. we demonstrate implementations of these algorithms on a typical task in natural language processing.
some remarks about stabilizers. we continue our study of stabilizers of infinite words over finite alphabets, begun in [d. krieger, on stabilizers of infinite words, theoret. comput. sci. 400 (2008), 169-181]. let w be an aperiodic infinite word over a finite alphabet, and let stab(w) be its stabilizer. we show that stab(w) can be partitioned into the monoid of morphisms that stabilize w by finite fixed points and the ideal of morphisms that stabilize w by iteration. we also settle a conjecture given in the paper mentioned above, by showing that in some cases stab(w) is infinitely generated. if the aforementioned ideal is nonempty, then it contains either polynomially growing morphisms or exponentially growing morphisms, but not both. moreover, in the polynomial case, the degree of the polynomial is fixed. we also show how to compute the polynomial degree from the dependency graph of a polynomially growing morphism.
reconstruction of graphs based on random walks. the analysis of complex networks is of major interest in various fields of science. in many applications we face the challenge that the exact topology of a network is unknown but we are instead given information about distances within this network. the theoretical approaches to this problem have so far been focusing on the reconstruction of graphs from shortest path distance matrices. often, however, movements in networks do not follow shortest paths but occur in a random fashion. in these cases an appropriate distance measure can be defined as the mean length of a random walk between two nodes - a quantity known as the mean first hitting time. in this contribution we investigate whether a graph can be reconstructed from its mean first hitting time matrix and put forward an algorithm for solving this problem. a heuristic method to reduce the computational effort is described and analyzed. in the case of trees we can even give an algorithm for reconstructing graphs from incomplete random walk distance matrices.
bio-pepa: a framework for the modelling and analysis of biological systems. in this work we present bio-pepa, a process algebra for the modelling and the analysis of biochemical networks. it is a modification of pepa, originally defined for the performance analysis of computer systems, in order to handle some features of biological models, such as stoichiometry and the use of general kinetic laws. bio-pepa may be seen as an intermediate, formal, compositional representation of biological systems, on which different kinds of analyses can be carried out. bio-pepa is enriched with some notions of equivalence. specifically, the isomorphism and strong bisimulation for pepa have been considered and extended to our language. finally, we show the translation of a biological model into the new language and we report some analysis results.
hardness and approximation of traffic grooming. traffic grooming is a central problem in optical networks. it refers to packing low rate signals into higher speed streams, in order to improve bandwidth utilization and reduce network cost. in wdm networks, the most accepted criterion is to minimize the number of electronic terminations, namely the number of sonet add-drop multiplexers (adms). in this article we focus on ring and path topologies. on the one hand, we provide an inapproximability result for traffic grooming for fixed values of the grooming factor g, answering affirmatively the conjecture of chow and lin [t. chow, p. lin, the ring grooming problem, networks 44 (2004), 194-202]. more precisely, we prove that ring traffic grooming for fixed g>=1 and path traffic grooming for fixed g>=2 are apx-complete. that is, they do not accept a ptas unless p=np. both results rely on the fact that finding the maximum number of edge-disjoint triangles in a tripartite graph (and more generally cycles of length 2g+1 in a (2g+1)-partite graph of girth 2g+1) is apx-complete. on the other hand, we provide a polynomial-time approximation algorithm for ring and path traffic grooming, based on a greedy cover algorithm, with an approximation ratio independent of g. namely, the approximation guarantee is o(n^1^/^3log^2n) for any g>=1, n being the size of the network. this is useful in practical applications, since in backbone networks the grooming factor is usually greater than the network size. finally, we improve this approximation ratio under some extra assumptions about the request graph.
an intermediate language for the stochastic simulation of biological systems. we introduce stochastic string multiset rewriting (ssmsr), and propose this formalism as an intermediate language for the simulation of biomolecular systems. higher level formalisms for biological systems description can be translated into ssmsr, and the features of ssmsr allow the development of efficient simulators. in this paper, we show the encoding into ssmsr of two formalisms for the description of biological systems, namely stochastic cls and the stochastic @p-calculus. we prove soundness and completeness of both the encodings.
estimation of state complexity of combined operations. it appears that the state complexity of each combined operation has its own special features. thus, it is important and practical to obtain good estimates for some commonly used general cases. in this paper, we consider the state complexity of combined boolean operations and give an exact bound for all of them in the case when the alphabet is not fixed. moreover, we show that for any fixed alphabet, this bound can be reached in infinitely many cases. we also consider the state complexity of multiple catenations. the state complexities are obtained in the cases of the catenations of three and four languages. an estimate for the catenation of an arbitrary number of languages is given, which is very close to the state complexities in the three and four languages cases.
on the complexity of constrained nash equilibria in graphical games. a widely accepted rational behavior for non-cooperative players is based on the notion of nash equilibrium. although the existence of a nash equilibrium is guaranteed in the mixed framework (i.e., when players select their actions in a randomized manner) in many real-world applications the existence of ''any'' equilibrium is not enough. rather, it is often desirable to single out equilibria satisfying some additional requirements (in order, for instance, to guarantee a minimum payoff to certain players), which we call constrained nash equilibria. in this paper, a formal framework for specifying these kinds of requirement is introduced and investigated in the context of graphical games, where a player p may directly be interested in some of the other players only, called the neighbors of p. this setting is very useful for modeling large population games, where typically each player does not directly depend on all the players, and representing her utility function extensively is either inconvenient or infeasible. based on this framework, the complexity of deciding the existence and of computing constrained equilibria is then investigated, in the light of evidencing how the intrinsic difficulty of these tasks is affected by the requirements prescribed at the equilibrium and by the structure of players' interactions. the analysis is carried out for the setting of mixed strategies as well as for the setting of pure strategies, i.e., when players are forced to deterministically choose the action to perform. in particular, for this latter case, restrictions on players' interactions and on constraints are identified, that make the computation of nash equilibria an easy problem, for which polynomial and highly-parallelizable algorithms are presented.
an (18/11)n upper bound for sorting by prefix reversals. the pancake problem asks for the minimum number of prefix reversals sufficient for sorting any permutation of length n. we improve the upper bound for the pancake problem to (18/11)n+o(1)~(1.6363)n.
on algorithmic analysis of transcriptional regulation by ltl model checking. studies of cells in silico can greatly reduce the need for expensive and prolonged laboratory experimentation. the use of model checking for the analysis of biological networks has attracted much attention recently. the practical limitations are still the size of the model, and the time needed to generate the state space. this paper is focused on the model checking approach for analysis of piecewise-linear deterministic models of genetic regulatory networks. firstly, the qualitative simulation algorithm of de jong et al. that builds the heart of genetic network analyzer (gna) is revisited and its time complexity is studied in detail. secondly, a novel algorithm that reduces the state space generation time is introduced. the new algorithm is developed as an abstraction of the original gna algorithm. finally, a fragment of linear time temporal logic for which the provided abstraction is conservative is identified. efficiency of the new algorithm when implemented in the parallel model checking environment is demonstrated on a set of experiments performed on randomly modified biological models. in general, the achieved results bring a new insight into the field of qualitative simulation emerging in the context of systems biology.
integration of a prediction mechanism with a sensor model: an anticipatory bayes filter. in the task of robot localization, bayes filters use two processes: the prediction step and the measurement-update step. briefly, the state transition model is responsible for prediction, and the sensor model is responsible for measurement updates. this paper presents a new approach to the sensor model, called the predictive sensor model, which utilizes a prediction mechanism to improve the efficiency of measurement updates in bayes filters. by adding sensorial anticipation, we extend the original bayes filter to an anticipatory bayes filter. we also propose an entropy-based place-segmentation method for automatic segmentation of sequentially collected visionsensor data. our place segmentation technique is most useful for node clustering in the process of constructing topological maps. our work was verified by experiments using observed data.
energetically consistent collisions in simulation of multibody systems. this paper presents a methodology for treating energy consistency when considering multiple simultaneous impacts and contacts with friction in the simulation of systems of multiple interconnected bodies. hard impact and contact is considered where deformation of the impacting surfaces is negligible. the proposed approach uses a discrete algebraic model of impact in conjunction with moment and tangential coefficients of restitution (cors) to develop a general impact law for determining post-impact velocities. this process depends on impulse-momentum theory, complementarity conditions, a principle of maximum dissipation, and the determination of contact forces. the proposed methodology also uses an energy-modifying cor to directly control the system's energy. the approach is illustrated on a bicycle-like structure.
a global self-localization technique utilizing local anomalies of the ambient magnetic field. magnetic field fluctuations in modern buildings arise from both natural and man-made sources, such as steel and reinforced concrete structures, electric power systems, electric and electronic appliances, and industrial devices. if the anomalies of the magnetic field inside the building are nearly static and they have sufficient local variability, they provide a unique magnetic fingerprint that can be utilized in global self-localization. in this article, a monte carlo localization (mcl) technique based on this hypothesis is proposed. the feasibility of the technique is demonstrated by presenting a series of global localization experiments conducted in four arbitrarily selected buildings, including a hospital. the experiment setup consists of a mobile robot instrumented with a 3-axis magnetometer and a computer. in addition, successful human self-localization experiments were conducted by using a wireless wearable magnetometer. the reported experiments suggest that the ambient magnetic field may remain sufficiently stable for longer periods of time, giving support for self-localization techniques utilizing the local deviations of the field.
a study of cooperative control of self-assembling robots in space with experimental validation. modular self-assembling on-orbit robotic and satellite systems can be more reliable, have lower launch costs, and be more easily repaired and refueled. however, when individual modules assemble, many challenges and opportunities make the control of the assembled system complex. these issues include changes in inertial properties, and redundancy of actuators and sensors. optimal control methods may be used to coordinate the control of the modules after assembly, insure good performance, and best utilize the combined resources of the assembly of modules. simulation and experimental results compare this cooperative algorithm's performance to that of an approach in which the control of the individual modules is not coordinated. cooperative optimal control methods prove well-suited for controlling redundant, modular space systems.
energy-efficient target tracking with a sensorless robot and a network of unreliable one-bit proximity sensors. existing target tracking algorithms require the tracker to have access to information-rich sensors, and may have difficulty recovering when the target is out of the tracker's sensing range. in this paper, we present a target tracking algorithm that combines an extremely simple mobile robot with a networked collection of wireless sensor nodes, each of which is equipped with an unreliable, limited-range, boolean sensor for detecting the target. the tracker maintains close proximity to the target using only information sensed by the network, and can effectively recover from temporarily losing track of the target. our approach combines a protocol for the sensor network that conserves energy by dynamically adjusting the time-to-live for packets it transmits with a reactive strategy for the tracker based on its information state. we present an implementation along with experimental results. our experimental results show that our system achieves both good tracking precision and low energy consumption.
control of a four-steering, planar five-bar linkage-walker. this paper introduces and describes a new type of wheeled locomotor referred to as a "four-steering, planar fivebar linkage-walker." this wheeled locomotor is a nonholonomic mechanical system that consists of five links, five rotational joints, and four steering systems. the five links coupled by the five joints form a closed-loop. the four steering systems are attached to four of the five links. each of the four links has its own steering system at its middle point. the wheeled locomotor transforms the rotations of the five joints into movement by using the four steering systems. this means that the wheeled locomotor performs undulatory locomotion in which it transforms a change in its internal shape into the generation of its net displacement. in addition, a virtual joint is added to one of the ends of the first link. the virtual joint couples the first link and a virtual link which has a virtual axle at its middle point and a virtual steering system at its end. it is proven that, by assuming the presence of such virtual mechanical elements, it is possible to convert the kinematic equation of the wheeled locomotor into a five-chain, single-generator chained form in differential geometry. based on chained form, a path-following feedback control method that enables the wheeled locomotor to follow a straight line is derived. the validity of the mechanical design of the wheeled locomotor, the transformation of its kinematic equation into chained form, and the path-following feedback control method is verified by computer simulation.
fat-based adaptive visual servoing for robots with time varying uncertainties. most present adaptive control strategies for visual servoing of robots have assumed that the unknown camera parameters, kinematics and dynamics of visual servoing system should be linearly parameterized in the regressor matrix form. this is because the limitation of the traditional adaptive design in which the uncertainties should be time-invariant such that all time varying terms in the visual servoing system are collected inside the regressor matrix. however, derivation of the regressor matrix is tedious. in this paper, a fat (function approximation technique) based adaptive controller is designed for visual servo robots without the need for the regressor matrix. a lyapunov-like analysis is used to justify the closed-loop stability and boundedness of internal signals. moreover, the upper bounds of tracking errors in the transient state are also derived. computer simulation results are presented to demonstrate the usefulness of the proposed scheme.
model-based and model-free reinforcement learning for visual servoing. to address the difficulty of designing a controller for complex visual-servoing tasks, two learning-based uncalibrated approaches are introduced. the first method starts by building an estimated model for the visual-motor forward kinematic of the vision-robot system by a locally linear regression method. afterwards, it uses a reinforcement learning method named regularized fitted q-iteration to find a controller (i.e. policy) for the system (model-based rl). the second method directly uses samples coming from the robot without building any intermediate model (model-free rl). the simulation results show that both methods perform comparably well despite not having any a priori knowledge about the robot.
effect of time delay on telesurgical performance. in the area of surgical robotics no standard means of performance evaluation has been established. thousands of surgeons have gone through the sages fls program, and the psychomotor skill portion of the program is considered the gold standard in laparoscopic skills evaluation. this research describes the use of the fls block transfer task to evaluate the performance of both surgeons and non-surgeons teleoperating under different time delay conditions on the university of washington raven surgical robot. time delays of 0ms, 250ms, and 500ms were used and a statistically significant difference in mean block transfer time as well as mean tool tip path length were shown. for this task no significant difference was shown between the surgeon and non-surgeon groups. clearly surgeon input and feedback is key to surgical robotic system development, but this result implies that nonsurgeon subjects can be tested for simple usability evaluations.
modeling and optimization of quadriglide, a schönflies motion generator module for 5-axis milling machine-tools. this paper introduces the quadriglide, a schönflies motion generator module for 5-axis machine-tools. the targeted application is high speed milling of long aeronautic parts, in particular thin ones, instead of toxic and dangerous chemical milling. quadriglide is described and its kinematics derived. then, a preliminary optimization is done to achieve the best actuation stiffness in a prescribed workspace with large tilting angles (θ = ±π/4). workspace plots of the optimized module are shown at the end of the paper.