waashk/dblp huggingface dataset:
combinatory differential fields. combinatory differential fields arise if differential fields are augmented by operations which allow functions that are programmable in the usual recursive sense to be denoted. the present paper defines this concept. it is shown that every differential field whose field of constants is ordered can be extended to a combinatory field. we generalize the basic notions of the liouville-ritt-risch theory of closed-form solvability to combinatory field extensions and present some explorative examples of problems and solutions. &mdash;author's abstract
applications of graphical condensation for enumerating matchings and tilings. a technique called graphical condensation is used to prove various combinatorial identities among numbers of (perfect) matchings of planar bipartite graphs and tilings of regions. graphical condensation involves superimposing matchings of a graph onto matchings of a smaller subgraph, and then re-partitioning the united matching (actually a multigraph) into matchings of two other subgraphs, in one of two possible ways. this technique can be used to enumerate perfect matchings of a wide variety of planar bipartite graphs. applications include domino tilings of aztec diamonds and rectangles, diabolo tilings of fortresses, plane partitions, and transpose complement plane partitions.
completing comma-free codes. we prove that for every regular comma-free code there exists a maximal comma-free code containing it which is still regular and, moreover, we can effectively locate such a completion. in particular, we can decide whether a given regular comma-free code is maximal.
the differential lambda-calculus. we present an extension of the lambda-calculus with differential constructions. we state and prove some basic results (confluence, strong normalization in the typed case), and also a theorem relating the usual taylor series of analysis to the linear head reduction of lambda-calculus.
differential interaction nets. we introduce interaction nets for a fragment of the differential lambda-calculus and exhibit in this framework a new symmetry between the of course and the why not modalities of linear logic, which is completely similar to the symmetry between the tensor and par connectives of linear logic. we use algebraic intuitions for introducing these nets and their reduction rules, and then we develop two correctness criteria (weak typability and acyclicity) and show that they guarantee strong normalization. finally, we outline the correspondence between this interaction nets formalism and the resource lambda-calculus.
on a conjecture on bidimensional words. we prove that, given a double sequence w over the alphabet a (i.e. a mapping from z2 to a), if there exists a pair (n0, m0) ∈ z2 such that pw(n0, m0) < 1/100n0m0, then w has a periodicity vector, where pw is the complexity function in rectangles of w.
a multidimensional critical factorization theorem. the critical factorization theorem is one of the principal results in combinatorics on words. it relates local periodicities of a word to its global periodicity. in this paper we give a multidimensional extension of it. more precisely, we give a new proof of the critical factorization theorem, but in a weak form, where the weakness is due to the fact that we loose the tightness of the local repetition order. in exchange, we gain the possibility of extending our proof to the multidimensional case. indeed, this new proof makes use of the theorem of fine and wilf, that has several classical generalizations to the multidimensional case.
more on weighted servers or fifo is better than lru. we consider a generalized two-server problem on the uniform space in which servers have different costs. previous work focused on the case where the ratio between these costs was very large. we give results for varying ratios. for ratios below 2.2, we present a best possible algorithm which is trackless. we present a general lower bound for trackless algorithms depending on the cost ratio, proving that our algorithm is the best possible trackless algorithm up to a constant factor for any cost ratio. the results are extended for the case where we have two sets of servers with different costs.
the chord version for sonet adms minimization. we consider a problem which arises in optical routing. wdm/sonet rings are a network architecture used by telecommunications carriers for traffic streams. the dominant cost factor in such networks is the total number of add-drop multiplexers (adms) used. a list of traffic streams to be routed between pairs of nodes is given. in this paper we consider the problem where we need to assign a route and a wavelength to each traffic stream, minimizing the total number of used sonet adms. this is called the chord version of the sonet adms minimization problem, to denote the fact that the routing is not given a priori. the best previously known approximation algorithms for this problem have the performance guarantee of 3/2. we present an improved algorithm with performance guarantee of exactly 10/7 ≈ 1.42857. moreover, we study some natural heuristics for this problem, and give tight analysis of their approximation ratios.
the conference call search problem in wireless networks. cellular telephony systems, where locations of mobile users are unknown at some times, are becoming more common. in such systems, mobile users are roaming in a zone and a user reports its location only if it leaves the zone entirely. the conference call search (ccs) problem deals with tracking a set of mobile users in order to establish a call. to find a single roaming user, the system may need to search each cell where the user may be located. the goal is to identify the location of all users, within bounded time, satisfying some additional constraints on the search scheme.we consider cellular systems with n cells and m mobile users (cellular phones). the uncertain location of users is given by m probability distribution vectors. whenever the system needs to find the users, it conducts a search operation lasting at most d rounds. a request for a single search step specifies a user and a cell. in this search step, the cell is asked whether the given user is located there. in each round the system may perform an arbitrary number of such requests. an integer number b ≥ 1 bounds the number of distinct requests per cell in every round. the bound d results from quality of service considerations, whereas the bound b results from the wireless bandwidth allocated for signaling being scarce.every search step consumes expensive wireless links, which motivates search techniques minimizing the expected number of requests thus reducing the total search costs.we distinguish between oblivious, semi-adaptive and adaptive search protocols. an oblivious search protocol decides on all requests in advance, and stops only when all users are found. a semi-adaptive search protocol decides on all the requests in advance, but it stops searching for a user once it is found. an adaptive search protocol stops searching for a user once it has been found (and its search strategy may depend on the subsets of users that were found in each previous round). we establish the difference between those three search models. we show that for oblivious "single query per cell" systems (b = 1), and a tight environment (d = m), it is np-hard to compute an optimal solution (the case d = m = 2 was proven to be np-hard already by bar-noy and naor) and we develop a ptas for these cases (for fixed values of d = m). however, we show that semi-adaptive systems allow polynomial time algorithms. this last result also shows that the case b = 1 and d = m = 2 is polynomially solvable also for adaptive search systems, answering an open question of bar-noy and naor.
lower bounds for on-line single-machine scheduling. the problem of scheduling jobs that arrive over time on a single machine is well studied. we study the preemptive model and the model with restarts. we provide lower bounds for deterministic and randomized algorithms for several optimality criteria: weighted and unweighted total completion time, and weighted and unweighted total flow time. by using new techniques, we provide the first lower bounds for several of these problems, and we significantly improve the bounds that were known.
on stable cutsets in line graphs. we answer a question of brandstädt et al. by showing that deciding whether a line graph with maximum degree 5 has a stable cutset is np-complete. conversely, the existence of a stable cutset in a line graph with maximum degree at most 4 can be decided efficiently. the proof of our np-completeness result is based on a refinement on a result due to chvátal that recognizing decomposable graphs with maximum degree 4 is an np-complete problem. here, a graph is decomposable if its vertices can be colored red and blue in such a way that each color appears on at least one vertex but each vertex v has at most one neighbor having a different color from v. we also discuss some open problems on stable cutsets.
the complexity of the characterization of networks supporting shortest-path interval routing. interval routing is a routing method that was proposed in order to reduce the size of the routing tables by using intervals and was extensively studied and implemented. some variants of the original method were also defined and studied. the question of characterizing networks which support optimal (i.e., shortest path) interval routing has been thoroughly investigated for each of the variants and under different models, with only partial answers, both positive and negative, given so far. in this paper, we study the characterization problem under the most basic model (the one unit cost), and with the most restrictive memory requirements (one interval per edge). we prove that this problem is np-hard (even for the restricted class of graphs of diameter at most 3). our result holds for all variants of interval routing. it significantly extends some related np-hardness result, and implies that, unless p = np, partial characterization results of some classes of networks which support shortest path interval routing, cannot be pushed further to lead to efficient characterizations for these classes.
note on the game chromatic index of trees. we study edge coloring games defining the so-called game chromatic index of a graph. it has been reported that the game chromatic index of trees with maximum degree δ = 3 is at most δ + 1. we show that the same holds true in case δ ≥ 6, which would leave only the cases δ = 4 and 5 open.
on the complexity of fixed parameter clique and dominating set. we provide simple, faster algorithms for the detection of cliques and dominating sets of fixed order. our algorithms are based on reductions to rectangular matrix multiplication. we also describe an improved algorithm for diamonds detection.
decision lists and related boolean functions. we consider boolean functions represented by decision lists, and study their relationships to other classes of boolean functions. it turns out that the elementary class of 1-decision lists has interesting relationships to independently defined classes such as disguised horn functions, read-once functions, nested differences of concepts, threshold functions, and 2-monotonic functions. in particular, 1-decision lists coincide with fragments of the mentioned classes. we further investigate the recognition problem for this class, as well as the extension problem in the context of partially defined boolean functions (pdbfs). we show that finding an extension of a given pdbf in the class of 1-decision lists is possible in linear time. this improves on previous results. moreover, we present an algorithm for enumerating all such extensions with polynomial delay.
on the complexity of data disjunctions. we study the complexity of data disjunctions in disjunctive deductive databases (dddbs). a data disjunction is a disjunctive ground clause r(c-1pt1)...r(ck),k ≥ 2, which is derived from the database such that all atoms in the clause involve the same predicate r. we consider the complexity of deciding existence and uniqueness of a minimal data disjunction, as well as actually computing one, both for propositional (data) and nonground (program) complexity of the database. our results extend and complement previous results on the complexity of disjunctive databases, and provide newly developed tools for the analysis of the complexity of function computation.
learning one-variable pattern languages very efficiently on average, in parallel, and by asking queries. a pattern is a finite string of constant and variable symbols. the langauge generated by a pattern is the set of all strings of constant symbols which can be obtained from the pattern by substituting non-empty strings for variables. we study the learnability of one-variable pattern languages in the limit with respect to the update time needed for computing a new single hypothesis and the expected total learning time taken until convergence to a correct hypothesis. our results are as follows. first, we design a consistent and set-driven learner that, using the concept of descriptive patterns, achieves update time o(n2logn), where n is the size of the input sample. the best previously known algorithm for computing descriptive one-variable patterns requires time o(n4logn) (cf. angluin, j. comput. systems sci. 21 (1) (1980) 46-62). second, we give a parallel version of this algorithm that requires time o(logn) and o(n3/logn) processors on an erew-pram. third, using a modified version of the sequential algorithm as a subroutine, we devise a learning algorithm for one-variable patterns whose expected total learning time is o(l2logl) provided that sample strings are drawn from the target language according to a probability distribution with expected string length l. the probability distribution must be such that strings of equal length have equal probability, but can be arbitrary otherwise. thus, we establish the first algorithm for learning one-variable pattern languages having an expected total learning time that provably differs from the update time by a constant factor only. finally, we show how the algorithm for descriptive one-variable patterns can be used for learning one-variable patterns with a polynomial number of superset queries with respect to the one-variable patterns as query language.
convexity and logical analysis of data. a boolean function is called $k$-convex if for any pair $x,y$ of its true points at hamming distance at most $k$, every point ``between'''' $x$ and $y$ is also true. given a set of true points and a set of false points, the central question of logical analysis of data is the study of those boolean functions whose values agree with those of the given points. in this paper we examine data sets which admit $k$-convex boolean extensions. we provide polynomial algorithms for finding a $k$-convex extension, if any, and for finding the maximum $k$ for which a $k$-convex extension exists. we study the problem of uniqueness, and provide a polynomial algorithm for checking whether all $k$-convex extensions agree in a point outside the given data set. we estimate the number of $k$-convex boolean functions, and show that for small $k$ this number is doubly exponential. on the other hand, we also show that for large $k$ the class of $k$-convex boolean functions is pac-learnable.
progressive solutions to a parallel automata equation. in this paper, we consider the problem of deriving a component x of a system knowing the behavior of the whole system c and the other components a. the component x is derived by solving the parallel automata equation a ⋄ x ≃ c. we present an algorithm for deriving a largest progressive solution to the equation that combined with a does not block any possible action in c and we establish conditions that allow us to characterize all progressive solutions.
deterministic analysis of queueing systems with heterogeneous servers. using deterministic (sample-path) analysis, we generalize and extend fundamental properties of systems with &ldquo;stationary deterministic flows&rdquo; as introduced by gelenbe (1983) and gelenbe and finkel (1987). primarily, we provide conditions for stability and instability for general queueing models, and focus attention on multichannel queueing systems with servers that work at different rates. stability analysis is important in computer applications and usually precedes any further investigation of the system in question. our results complement and extend those of gelenbe and finkel by making weaker assumptions, allowing multichannel facilities with heterogeneous servers, and including more general queueing disciplines such as processor sharing and lcfs-pr. the key to our stability analysis is a deterministic version of the renewal-reward theorem which we call y=lx , and a relationship that shows the &ldquo;operational analysis&rdquo; definition of average service times, when considered as the observation period t&rarr;&infin; , coincides with the standard definition of average service times for all stable queueing systems. our analysis is completely deterministic and avoids any stochastic assumptions about the system under investigation; thus, it provides the practitioner with a method that often leads to a better and deeper understanding of the system under consideration. it also gives a powerful tool to determine which properties of the system are independent of the usually needed probabilistic assumptions. as an illustration, a sample-path relationship that gives the long-run average busy period (cycle) for a general queueing model is given and utilized to derive several well-known results under weaker conditions. &mdash;authors' abstract
a context-free and a 1-counter geodesic language for a baumslag-solitar group. we give a language of unique geodesic normal forms for the baumslag-solitar group bs(1,2) that is context-free and 1-counter. we discuss the classes of context-free, 1-counter and counter languages, and explain how they are inter-related.
pcf extended with real numbers. we extend the programming language pcf with a type for (total and partial) real numbers. by a partial real number we mean an element of a cpo of intervals, whose subspace of maximal elements (single-point intervals) is homeomorphic to the euclidean real line. we show that partial real numbers can be considered as &ldquo;continuous words&rdquo;. concatenation of continuous words corresponds to refinement of partial information. the usual basic operations cons, head and tail used to explicitly or recursively define functions on words generalize to partial real numbers. we use this fact to give an operational semantics to the above referred extension of pcf. we prove that the operational semantics is sound and complete with respect to the denotational semantics. a program of real number type evaluates to a head-normal form iff its value is different from &bottom; ; if its value is different from &bottom; then it successively evaluates to head-normal forms giving better and better partial results converging to its value. &mdash;author's abstract
symmetry groups for beta-lattices. we present a construction of symmetry plane-groups for quasiperiodic point-sets named beta-lattices. the framework is issued from beta-integers counting systems. beta-lattices are vector superpositions of beta-integers. when β > 1 is a quadratic pisot-vijayaraghavan algebraic unit, the set of beta-integers can be equipped with an abelian group structure and an internal multiplicative law. when β = (1 + √5)/2, 1 + √2 and 2 + √3, we show that these arithmetic and algebraic structures lead to freely generated symmetry plane-groups for beta-lattices. these plane-groups are based on repetitions of discrete adapted rotations and translations we shall refer to as "beta-rotations" and "beta-translations". hence beta-lattices, endowed with beta-rotations and beta-translations, can be viewed like lattices. the quasiperiodic function ρs(n), defined on the set of beta-integers as counting the number of small tiles between the origin and the nth beta-integer, plays a central part in these new group structures. in particular, this function behaves asymptotically like a linear function. as an interesting consequence, beta-lattices and their symmetries behave asymptotically like lattices and lattice symmetries, respectively.
a rewriting-based inference system for the nrl protocol analyzer and its meta-logical properties. the nrl protocol analyzer (npa) is a tool for the formal specification and analysis of cryptographic protocols that has been used with great effect on a number of complex real-life protocols. one of the most interesting of its features is that it can be used to reason about security in face of attempted attacks on low-level algebraic properties of the functions used in a protocol. indeed, it has been used successfully to either reproduce or discover a number of such attacks. in this paper we give for the first time a precise formal specification of the main features of the npa inference system: its grammar-based techniques for invariant generation and its backwards reachability analysis method. this formal specification is given within the well-known rewriting framework so that the inference system is specified as a set of rewrite rules modulo an equational theory describing the behavior of the cryptographic algorithms involved. we then use this formalization to prove some important meta-logical properties about the npa inference system, including the soundness and completeness of the search algorithm and soundness of the grammar generation algorithm. the formalization and soundness and completeness theorems not only provide also a better understanding of the npa as it currently operates, but provide a modular basis which can be used as a starting point for increasing the types of equational theories it can handle.
completeness in approximation classes beyond apx. we present a reduction that allows us to establish completeness results for several approximation classes mainly beyond apx. using it, we extend one of the basic results of s. khanna, r. motwani, m. sudan, and u. vazirani (on syntactic versus computational views of approximability, siam j. comput. 28 (1998) 164-191) by proving sufficient conditions for getting complete problems for the whole log-apx, the class of problems approximable within ratios that are logarithms of the size of the instance, as well as for any approximability class beyond apx. we also introduce a new approximability class, called poly-apx(δ), dealing with graph-problems approximable with ratios functions of the maximum degree δ of the input-graph. for this class also, using the proposed reduction, we establish complete problems.
euclidean strings. a string p = p0p1...pn-1 of non-negative integers is a euclidean string if the string (p0 + 1)p1...(pn-1 - 1) is rotationally equivalent (i.e., conjugate) to p. we show that euclidean strings exist if and only if n and p0 + p1 + ... + pn-1 are relatively prime and that, if they exist, they are unique. we show how to construct them using an algorithm with the same structure as the euclidean algorithm, hence the name. we show that euclidean strings are lyndon words and we describe relationships between euclidean strings and the stem-brocot tree, fibonacci strings, beatty sequences, and sturmian sequences. we also describe an application to a graph embedding problem.
on the complexity of resolution with bounded conjunctions. we analyze size and space complexity of res(k), a family of propositional proof systems introduced by krajíček in (fund. math. 170 (1-3) (2001) 123) which extend resolution by allowing disjunctions of conjunctions of up to k ≥ 1 literals. we show that the treelike res(k) proof systems form a strict hierarchy with respect to proof size and also with respect to space. moreover resolution, while simulating treelike res(k), is almost exponentially separated from treelike res(k). to study space complexity for general res(k) we introduce the concept of dynamical satisfiability which allows us to prove in a unified way all known space lower bounds for resolution and to extend them to res(k).