waashk/dblp huggingface dataset:
iterated relabeling tree transducers. in this paper we consider the closure uci(rel) of the class of relabeling tree transformations, under u=union, c=composition and i=iteration. we give a characterization of uci(rel) in terms of a short expression built up from rel with composition and iteration. we also give a characterization of uci(rel) in terms of one-step rewrite relations of very simple term rewrite systems. we give a similar characterization of uc(frel+), where frel+ is the class consisting of the transitive closures of all functional relabeling tree transformations. finally we show that uci(rel)=uci(frel).
minimal length test vectors for multiple-fault detection. a methodology for circuit testing is proposed for detecting multiple circuit faults in the course of a minimal length "guided tour" of the circuit transition structure. deriving a test vector to guide this tour through an n state subsystem with at most i inputs possible in situ at each state, corresponds to solving an open tour multigraph version of the "chinese postman" problem, in which out-degrees are bounded by i. in this case, the length l of a minimal length open tour is shown to satisfy l ≤ in2; a minimal length open tour is computable in o(n3 + ni) steps for undirected multigraphs and o(n3 + (ni)2logn/logi) steps for directed multigraphs, both one-time costs, using weighted matching and bipartite weighted matching, respectively. an open tour can result in a test vector as much as ½ shorter than the test vector associated with a closed tour, without any loss in error detection. examples show that for a directed graph, the length of a minimal length open tour may be as great as n3/6 for i = n, or ω(n2) when i is bounded, while in an undirected multigraph, a minimal length tour requires no more than n - 3 repeated state transitions. this mitigates in favor of "mixed" circuits in which certain transitions are reversible and need be tested in only one direction.the practicality of this approach rests with the ability to apply it separately to small sub-systems, in conjunction with symbolic testing of inter-subsystem coordination. the former is feasible with existing commercial technologies, such as electron beam scanning, while the latter is feasible with a finite-state model-checker.in summary, the proposed methodology comprises three steps: 1. decompose a circuit into subsystems sufficiently small to be model-checked exhaustively; 2. perform symbolic tests of inter-subsystem coordination and conclude that if each subsystem is correctly implemented, then the entire circuit will behave as required; 3. for each circuit subsystem, exercise every realizable transition through a minimal length (open) tour, comparing the actual transitions with those of the specification.
deciding sequentiability of finite-state transducers by finite-state pattern-matching. sequentiality (input-side determinism) is a desirable property of finite-state transducers: such transducers are optimal for time efficiency. not all transducers are sequentiable and those that are may not be sequential. sequentialization algorithms of finite-state transducers do not recognize whether a transducer is sequentiable or not and simply do not ever halt when it is not. choffrut proved that sequentiality of finite-state transducers is decidable. béal et al. (in: d. gonnet, g. panario, a. viola (eds.), proceedings of latin 2000, lecture notes in computer science, vol. c1776, springer, heidelberg, 2000, p. 397) have proposed squaring to decide sequentiality. we propose a different procedure, which, with ε-closure extension, is able to handle letter transducers with arbitrary ε-ambiguities, too. our algorithm is more economical than squaring, in terms of size. in different cases of non-sequentiability, necessary and sufficient conditions of one of the four possible ambiguity classes of the transducer can be observed. these ambiguities can be mapped bijectively to particular basic patterns in the structure of the transducer. the non-presence of both the infinitely ambiguous and the unboundedly ambiguous patterns is the condition of sequentiability. these patterns can be recognized, using finite-state methods, in any transducer. the method shows both sequentiability and, if present, sequentiality on the given side of the transducer.
approximation algorithms for facility location problems with a special class of subadditive cost functions. in this article we focus on approximation algorithms for facility location problems with subadditive costs. as examples of such problems, we present three facility location problems with stochastic demand and exponential servers, respectively inventory. we present a (1 + ε, 1)-reduction of the facility location problem with subadditive costs to the soft capacitated facility location problem, which implies the existence of a 2(1 + ε)-approximation algorithm. for a special subclass of subadditive functions, we obtain a 2-approximation algorithm by reduction to the linear cost facility location problem.
linear constructions for dna codes. in this paper we translate in terms of coding theory constraints that are used in designing dna codes for use in dna computing or as bar-codes in chemical libraries. we propose new constructions for dna codes satisfying either a reverse-complement constraint, a gc-content constraint, or both, that are derived from additive and linear codes over four-letter alphabets. we focus in particular on codes over gf (4), and we construct new dna codes that are in many cases better (sometimes far better) than previously known codes. we provide updated tables up to length 20 that include these codes as well as new codes constructed using a combination of lexicographic techniques and stochastic search.
uniform test of algorithmic randomness over a general space. the algorithmic theory of randomness is well developed when the underlying space is the set of finite or infinite sequences and the underlying probability distribution is the uniform distribution or a computable distribution. these restrictions seem artificial. some progress has been made to extend the theory to arbitrary bernoulli distributions (by martin-löf) and to arbitrary distributions (by levin). we recall the main ideas and problems of levin's theory, and report further progress in the same framework. the issues are the following: • allow non-compact spaces (like the space of continuous functions, underlying the brownian motion). • the uniform test (deficiency of randomness) dp(x) (depending both on the outcome x and the measure p) should be defined in a general and natural way. • see which of the old results survive: existence of universal tests, conservation of randomness, expression of tests in terms of description complexity, existence of a universal measure, expression of mutual information as "deficiency of independence". • the negative of the new randomness test is shown to be a generalization of complexity in continuous spaces; we show that the addition theorem survives.the paper's main contribution is introducing an appropriate framework for studying these questions and related ones (like statistics for a general family of distributions).
comparing logics for rewriting: rewriting logic, action calculi and tile logic. the large diffusion of concurrent and distributed systems has spawned in recent years a variety of new formalisms, equipped with features for supporting an easy specification of such systems. the aim of our paper is to analyze three proposals, namely rewriting logic, action calculi and tile logic, chosen among those formalisms designed for the description of rule-based systems. for each of these logics we first try to understand their foundations, then we briefly sketch some applications. the overall goal of our work is to find out a common layout where these logics can be recast, thus allowing for a comparison and an evaluation of their specific features.
on separating the erew and crew pram models. in [6], snir proposed the selection problem (searching in a sorted table) to show that the crew pram is strictly more powerful than the erew pram. this problem defines a partial function, that is, one that is defined only on a restricted set of inputs. recognizing whether an arbitrary input belongs to this restricted set is hard for both crew and erew prams. the existence of a total function that exhibits the power of the crew model over the erew model was an open problem. here we solve this problem by generalizing the selection problem to a decision tree problem which is defined on a full domain and to which snir''s lower bound applies.
on the submodular matrix representation of a digraph. we reexamine the class of (0,±1) matrices called submodular, which we introduced in (ann. discrete math. 15 (1982) 189). our key idea in this paper is to define, for each submodular matrix m, a corresponding digraph g whose nodes are the columns of m. our principal results are as follows: (a) a graph-theoretic interpretation of the polyhedron p(m) = {x: x ≥ 0, mx ≥ - 1}, and (b) for a given g, the description of a submodular matrix contained in all submodular matrices representing g.
structure and complexity of extreme nash equilibria. we study extreme nash equilibria in the context of a selfish routing game. specifically, we assume a collection of n users, each employing a mixed strategy, which is a probability distribution over m parallel identical links, to control the routing of its own assigned traffic. in a nash equilibrium, each user selfishly routes its traffic on those links that minimize its expected latency cost. the social cost of a nash equilibrium is the expectation, over all random choices of the users, of the maximum, over all links, latency through a link.we provide substantial evidence for the fully mixed nash equilibrium conjecture, which states that the worst nash equilibrium is the fully mixed nash equilibrium, where each user chooses each link with positive probability. specifically, we prove that the fully mixed nash equilibrium conjecture is valid for pure nash equilibria. furthermore, we show, that under a certain condition, the social cost of any nash equilibrium is within a factor of 2h(1 + ε) of that of the fully mixed nash equilibrium, where h is the factor by which the largest user traffic deviates from the average user traffic.considering pure nash equilibria, we provide a ptas to approximate the best social cost, we give an upper bound on the worst social cost and we show that it is n p-hard to approximate the worst social cost within a multiplicative factor better than 2 - 2/(m + 1).
a format for semantic equivalence comparison. this paper presents a new format for process algebras, the extended tyft/tyxt format which generalises the tyft/tyxt format of groote and vaandrager. the format differs from most previous formats in that the labels on transitions are treated as many-sorted terms. bisimulation is a congruence for all operators defined by extended transition system specifications in this format.when one extended transition system specification is summed with another, the resulting bisimulation can either identify more terms (an abstracting extension up to bisimulation) or fewer terms (a refining extension up to bisimulation) than the original bisimulation on the individual system. the notions of abstracting extension and refining extension are defined, and two theorems are presented giving conditions required for achieving each type of extension. these results provide a way to compare different semantic equivalences defined for different process algebras.finally, an application of this theory to semantic equivalence comparison is given for a new result relating castellani's pomset equivalence and krishan's multiprocessor equivalence.
iterative bayes. naive bayes is a well-known and studied algorithm both in statistics and machine learning. bayesian learning algorithms represent each concept with a single probabilistic summary. in this paper we present an iterative approach to naive bayes. the iterative bayes begins with the distribution tables built by the naive bayes. those tables are iteratively updated in order to improve the probability class distribution associated with each training example. in this paper we argue that iterative bayes minimizes a quadratic loss function instead of the 0-1 loss function that usually applies to classification problems. experimental evaluation of iterative bayes on 27 benchmark data sets shows consistent gains in accuracy. an interesting side effect of our algorithm is that it shows to be robust to attribute dependencies.
prediction algorithms and confidence measures based on algorithmic randomness theory. this paper reviews some theoretical and experimental developments in building computable approximations of kolmogorov's algorithmic notion of randomness. based on these approximations a new set of machine learning algorithms have been developed that can be used not just to make predictions but also to estimate the confidence under the usual iid assumption.
characterization of networks supporting multi-dimensional linear interval routing schemes. an interval routing scheme (irs) is a well-known, space efficient routing strategy for routing messages in a distributed network. in this scheme, each node of the network is assigned an integer label and each link at each node is labeled with an interval. the interval assigned to a link e at a node v indicates the set of destination addresses of the messages which should be forwarded through e at v. a multi-dimensional interval routing scheme (mirs) is a generalization of irs in which each node is assigned a multi-dimensional label (which is a list of d integers for the d-dimensional case). the labels assigned to the links of the network are also multi-dimensional (a list of d 1-dimensional intervals). the class of networks supporting linear irs (in which the intervals are not cyclic) is already known for the one-dimensional case (13th annu. acm symp. principles of distributed computing (podc), acm press, new york, august 1994, pp. 216-224). in this paper, we generalize this result and completely characterize the class of networks supporting linear mirs (or mlirs) for a given number of dimensions d. we show that by increasing d, the class of networks supporting mlirs is strictly expanded. we also give a characterization of the class of networks supporting strict mlirs (which ia an mlirs is which the interval assigned to the links incident to a node v, does not contain the label of v).
state space reduction for process algebra specifications. data-flow analysis to identify "dead" variables and reset them to an "undefined" value is an effective technique for fighting state explosion in the enumerative verification of concurrent systems. although this technique is well-adapted to imperative languages, it is not directly applicable to value-passing process algebras, in which variables cannot be reset explicitly due to the single-assignment constraints of the functional programming style. this paper addresses this problem by performing data-flow analysis on an intermediate model (petri nets extended with state variables) into which process algebra specifications can be translated automatically. it also addresses important issues such as avoiding the introduction of useless reset operations and handling shared read-only variables that child processes inherit from their parents.
connectionist computations of intuitionistic reasoning. the construction of computational models with provision for effective learning and added reasoning is a fundamental problem in computer science. in this paper, we present a new computational model for integrated reasoning and learning that combines intuitionistic reasoning and neural networks. we use ensembles of neural networks to represent intuitionistic theories, and show that for each intuitionistic theory and intuitionistic modal theory there exists a corresponding neural network ensemble that computes a fixed-point semantics of the theory. this provides a massively parallel model for intuitionistic reasoning. in our model, the neural networks can be trained from examples to adapt to new situations using standard neural learning algorithms, thus providing a unifying foundation for intuitionistic reasoning, knowledge representation, and learning.
learning in varieties of the form vli from positive data. grammatical inference and finite semigroup theory are continuously developing. nevertheless it seems that they are not interacting too much. we propose in this paper an inference method for languages that belong to varieties of the form v*li. many well known families of languages like locally testable, reversible, dot-depth one, etc. are of that form. the method unifies existing algorithms for inference of some of those families and can be applied to some others that had not been inferred yet. it uses a result about the cascade product in which one of the factors is a transducer and the second is the automaton obtained by inferring the base case of the family using the transduction of the sample as input.
bilateral locally testable languages. we give an algebraic characterization of a new variety of languages that will be called bilateral locally testable languages and denoted as blt. given k > 0, the membership of a word x to a blt (k-bt) language can be decided by means of exploring the segments of length k of x, as well as considering the order of appearance of those segments when we scan the prefixes and the suffixes of x. in this paper, we also characterize the syntactic semigroup of blt languages in terms of the equations of the variety they belong to, as well as in terms of the join of two previously studied varieties.
power simulation and its relation to traces and failures refinement. there are two quite distinct approaches commonly used when giving meaning to process algebra expressions: an operational semantics, often associated with the ccs language, defines an equivalence between terms by considering whether each can simulate the other; a denotational semantics, often associated with csp, provides a mapping, recursively defined over the structure of the language, taking each term into a carefully chosen collection of set-theoretic objects. (the traces and failures models are well-known examples of such semantic domains.) we present a formal link between the two approaches, consisting in defining a variant of the bisimulation equivalence that naturally gives rise to the traces and failures ordering. we have no way at present to extend this result to the failures/divergence model.
modelling dynamic web data. we introduce the xdπ calculus, a peer-to-peer model for reasoning about dynamic web data. web data is not just stored statically. rather it is referenced indirectly, for example using hyperlinks, service calls, or scripts for dynamically accessing data, which require the complex coordination of data and processes between sites. the xdπ calculus models this coordination by integrating the xml data structure with process orchestration techniques associated with the distributed pi-calculus. we study behavioural equivalences for xdπ, to analyze the various possible patterns of data and process interaction.
implicit surface visualization of reconstructed biological molecules. an implicit surface of a density function is the set of points at which the value of the function is equal to a fixed threshold. an object that is defined as the collection of points at which the density function value is above the threshold can be visualized by displaying the implicit surface. some methods for the reconstruction of biological macromolecules from their electron microscopic projections produce density functions that are specified by a linear combination of smoothly-varying radially-symmetric basis functions of finite support, also known as blobs. when density functions are determined by such a blob representation, the implicit surfaces are smoothly varying and the normal at any point on such a surface can be analytically calculated. this property can be utilized to produce high-quality visualizations by raycasting. while raycasting tends to be computationally expensive, we present a methodology that uses techniques of computer graphics and image processing to significantly reduce the cost of visualization.
the generalized weil pairing and the discrete logarithm problem on elliptic curves. we review the construction of a generalization of the weil pairing, which is nondegenerate and bilinear, and use it to construct a reduction from the discrete logarithm problem on elliptic curves to the discrete logarithm problem in finite fields. we show that the new pairing can be computed efficiently for curves with trace of frobenius congruent to 2 modulo the order of the base point. this leads to an efficient reduction for this class of curves. the reduction is as simple to construct as that of menezes et al. (ieee trans. inform. theory, 39, 1993), and is provably equivalent to that of frey and rück (math. comput. 62 (206) (1994) 865).
algorithmic combinatorics based on slicing posets. a combinatorial problem usually requires enumerating, counting or ascertaining existence of structures that satisfy a given property b in a set of structures l. this paper describes a technique based on a generalization of birkhoff's theorem of representation of finite distributive lattices that can be used for solving such problems mechanically and efficiently. specifically, we give an efficient (polynomial time) algorithm to enumerate, count or detect structures that satisfy b when the total set of structures is large but the set of structures satisfying b is small. we illustrate our techniques by analyzing problems in integer partitions, set families, and set of permutations.
regular component decomposition of regular languages. a language is regular if it can be recognized by a finite automaton. according to the pumping lemma, every infinite regular language contains a regular subset of the form uv+w, where u, v, w are words and v is not empty. it is known that every regular language can be expressed as (∪i∈iuivi+wi) ∪f, where i is an index set, ui, wi∈a*,vi∈a+,i∈i and f is a finite set of words over the alphabet a. this expression is called a regular component decomposition of the language. a language is called regular component splittable if it can be expressed as a disjoint union of regular components and a finite set. a language which has a regular component decomposition with finite index is called a finite regular component representable language. it has been shown that every finite regular component representable language is regular component splittable by shyr and yu in (discrete appl. math. 82 (1998) 219). they conjectured that every regular language is regular component splittable in (acta math. hung. 78(3) (1998) 251). the conjecture is proved in this paper.
space efficient search for maximal repetitions. we study here a problem of finding all maximal repetitions in a string of length n. we show that the problem can be solved in time o(n log n) in the presence of constant extra space and general (unbounded) alphabets. subsequently we show that in the model with a constant size alphabet the problem can be solved in time o(n) with a help of o(n) extra space. previously best known algorithms require linear additional space in both models.