waashk/dblp huggingface dataset:
multiple splicing systems and the universal computability. we propose a new extension of splicing systems, called multiple splicing systems, based on a kind of logic grammars. first, we introduce a class of elementary formal systems, called simple h-form efs, and show that its generative power is equivalent to the class of basic splicing systems (the original head's splicing system) and is more adequate as representation device for formal languages. next, we gradually extend the simple class of efss and get a very natural extension of splicing systems, multiple splicing systems. we show that multiple splicing systems have universal computability.
the complexity of learning concept classes with polynomial general dimension. the general dimension is a combinatorial measure that characterizes the number of queries needed to learn a concept class. we use this notion to show that any p-evaluatable concept class with polynomial query complexity can be learned in polynomial time with the help of an oracle in the polynomial hierarchy, where the complexity of the required oracle depends on the query-types used by the learning algorithm. in particular, we show that for subset and superset queries an oracle in σ3p suffices. since the concept class of dnf formulas has polynomial query complexity with respect to subset and superset queries with dnf formulas as hypotheses, it follows that dnf formulas are properly learnable in polynomial time with subset and superset queries and the help of an oracle in σ3p. we also show that the required oracle in our main theorem cannot be replaced by an oracle in a lower level of the polynomial-time hierarchy, unless the hierarchy collapses.
list version of (, )-labelings. let g = (v, e) be a simple graph, and for all v ∈ v, let l(v) be a list of colors assigned to v. we shall assume throughout that the colors are natural numbers. for nonnegative integers d, s, define χd,sl (g) to be the smallest integer k such that for every list assignment with |l(v)| = k for all v ∈ v one can choose a color c(v) ∈ l(v) for every vertex in such a way that |c(v) - c(w)| ≥ d for all vw ∈ e and |c(v) - c(w)| ≥ s for all pairs v, w of vertices having distance 2 in g. for a given list assignment such a coloring c is called an l(d, s)-list labeling.we prove a general bound for χd,sl (g) depending on the maximum degree of g. furthermore, we study this parameter for trees, and also for the particular classes of paths and stars. polynomial algorithms are designed for deciding whether a given list assignment admits an l(d, s)-list labeling on paths (for a given s unrestricted) and on trees (for s = 1).
proof assistance for real-time systems using an interactive theorem prover. this paper discusses the adaptation of the pvs theorem prover for performing analysis of real-time systems written in the astral formal specification language. several issues arose during the encoding of astral that are relevant to the encoding of many real-time specification languages such as encoding formulas as types, handling partial functions, dealing with noninterleaved concurrency, and defining irregular operators. these issues and possible solutions are presented as well as how they were handled in the astral encoding. a translator was written that translates any astral specification into its corresponding pvs encoding. after performing the proofs of several systems using their translations, pvs strategies were developed to automate the proofs of certain types of properties. in particular, strategies are presented for fully automating the proofs of certain classes of untimed properties. in addition, strategies were developed for partially automating the derivation of timed executions using transition steps. the encoding was used as the basis for a fully automated transition sequence generator tool, which has a wide variety of applications.
an operational and denotational approach to non-context-freeness. the main result of this paper is a description of linguistically motivated non-context-free phenomena equivalently in terms of regular tree languages (to express the recursive properties) and both a logical and an operational perspective (to establish the intended linguistic relations). the result is exemplified with a particular non-context-free phenomenon, namely cross-serial dependencies in natural languages such as swiss german or dutch. the logical description is specified in terms of binary monadic second-order (mso) formulas and the operational description is achieved by means of a linear and non-deleting macro tree transducer. besides giving a grammatical presentation for the regular tree language we shall also specify an implementation in the form of a finite-state (tree) automaton to emphasize the effectivity of our approach.
approximation algorithms for minimizing the total weighted tardiness on a single machine. given a single machine and a set of jobs with due dates, the classical np-hard problem of scheduling to minimize total tardiness is a well-understood one. lawler gave a fully polynomial-time approximation scheme (fptas) for it some 20 years ago. if the jobs have positive weights the problem of minimizing total weighted tardiness seems to be considerably more intricate, it. in this paper, we give some of the first approximation algorithms for it. we examine first the weighted problem with a fixed number of due dates and we design a pseudopolynomial algorithm for it. we show how to transform the pseudopolynomial algorithm to an fptas for the case where the weights are polynomially bounded.for the case with an arbitrary number of due dates and polynomially bounded processing times, we provide a quasipolynomial algorithm which produces a schedule whose value has an additive error proportional to the weighted sum of the due dates. we also investigate the performance of algorithms for minimizing the related total weighted late work objective.
finding approximate repetitions under hamming distance. the problem of computing periodicities with k possible mismatches is studied. two main definitions are considered, and for both of them an o(nk logk + s) algorithm is proposed (n the word length and s the size of the output). this improves, in particular, the bound obtained by g. landan and j. schmidt in 1993 (proceedings of the fourth annual symposium on combinatorial pattern matching, lecture notes in computer science, vol. 684, springer, berlin, padova, italy, pp. 120-133). finally, other possible definitions are briefly analyzed.
real functions computable by finite automata using affine representations. this paper tries to classify the functions of type in → i (for some interval i ⊆ r) that can be exactly realized by a finite transducer. such a class of functions strongly depends on the choice of real number representation. this paper considers only the so-called affine representations where numbers are represented by infinite compositions of affine contracting functions on i. affine representations include the radix (e.g. decimal, signed binary) representations. the first result is that all piecewise affine functions of n variables with rational coefficients are computable by a finite transducer which uses the signed binary representation. the second and main result is that any function computable by a finite transducer using an affine representation is affine on any open connected subset of in on which it is continuously differentiable. this limitation theorem shows that the set of finitely computable functions is very restricted.
real functions incrementally computable by finite automata. this is an investigation into exact real number computation using the incremental approach of potts (ph.d. thesis, department of computing, imperial college, 1998), edalat and potts (electronic notes in computer science, vol. 6, elsevier science publishers, amsterdam, 2000), nielsen and kornerup (j. universal comput. sci. 1(7) (1995) 527), and vuillemin (ieee trans. on comput. 39(8) (1990) 1087) where numbers are represented as infinite streams of digits, each of which is a möbius transformation. the objective is to determine for each particular system of digits which functions r → r can be computed by a finite transducer and ultimately to search for the most finitely expressible möbius representations of real numbers. the main result is that locally such functions are either not continuously differentiable or equal to some möbius transformation. this is proved using elementary properties of finite transition graphs and möbius transformations. applying the results to the standard signed-digit representations, we can classify functions that are finitely computable in such a representation and are continuously differentiable everywhere except for finitely many points. they are exactly those functions whose graph is a fractured line connecting finitely many points with rational coordinates.
the khalimsky topologies are precisely those simply connected topologies on z whose connected sets include all 2n-connected sets but no (3n-1)-disconnected sets. we give a proof of the result stated in the title. here the concepts of 2n- and (3n- 1)- (dis)connected sets are the natural generalizations to zn of the standard concepts of 4- and 8-(dis)connected sets in 2d digital topology.suppose we have an n-dimensional scanner that digitizes n-dimensional objects to subsets of zn. we are interested in topological spaces (zn, τ) that might allow standard concepts and methods of general topology to be directly and usefully applied to good digitizations produced by the scanner. but our result suggests that if a topological space (zn, τ) is not a khalimsky space, then it will not satisfy our requirement.our proof involves some purely discrete arguments and a fact about simply connected polyhedra that is a well-known consequence of the simplicial approximation theorem, but also uses the following fact (which was one of the main results in an earlier paper (in: r.m. shortt (ed.), general topology and applications: proc. 1988 northeast conf., marcel dekker, new york, 1990, pp. 153-164) by the author and khalimsky): for any t0 topological space in which each point lies in a finite open set and a finite closed set there exists a polyhedron, whose vertices are in 1-1 correspondence with the points of the space, such that the homotopy classes of continuous maps into the topological space from any metric space are in 1-1 correspondence with the homotopy classes of continuous maps from that metric space into the polyhedron.
rasiowa-sikorski deduction systems in computer science applications. a rasiowa-sikorski system is a sequence-type formalization of logics. the system uses invertible decomposition rules which decompose a formula into sequences of simpler formulae whose validity is equivalent to validity of the original formula. there may also be expansion rules which close indecomposable sequences under certain properties of relations appearing in the formulae, like symmetry or transitivity. proofs are finite decomposition trees with leaves having "fundamental", valid labels. the author describes a general method of applying the rs formalism to develop complete deduction systems for various brands of c.s and a.i. logic, including a logic for reasoning about relative similarity, a three-valued software specification logic with mccarthy's connectives and kleene quantifiers, a logic for nondeterministic specifications, many-sorted fol with possibly empty carriers of some sorts, and a three-valued logic for reasoning about concurrency.
error-detecting properties of languages. the language property of error-detection ensures that the communications medium cannot transform a word of the language to another word of the language. in this paper we provide some insights on the notion of error-detection from a language theoretic point of view. we define certain error-detecting properties of languages and codes including the notion of error-detection with finite delay which is a natural extension of unique decodability with finite delay. we obtain results about the error-detecting capabilities of regular and other languages, and of known classes of codes. moreover, we consider the problem of estimating the optimal redundancy of infinite languages with the property of detecting errors of the deletion type.
uniquely decodable n-gram embeddings. we define the family of n-gram embeddings from strings over a finite alphabet into the semimodule nk. we classify all ξ ∈ nk that are valid images of strings under such embeddings, as well as all ξ whose inverse image consists of exactly 1 string (we call such ξ uniquely decodable). we prove that for a fixed alphabet, the set of all strings whose image is uniquely decodable is a regular language.
on-line scheduling with tight deadlines. this paper is concerned with the on-line problem of scheduling jobs with tight deadlines in a uni-processor system. it has been known for long that in such a setting, no on-line algorithm is 1-competitive (i.e., optimal) in the sense of matching the optimal off-line algorithm on the total value of jobs that meet the deadlines; indeed, no algorithm can be better than k-competitive, where k is the importance ratio of the jobs. recent work, however, reveals that the competitive ratio can be improved to a constant if the on-line scheduler is equipped with a processor o(1) times faster (j. acm 47(4) (2000) 617), and further to one when using a processor o(logk) times faster (proc. 12th ann. acm-siam symp. on discrete algorithms, 2001, p. 755). this paper presents a new on-line algorithm for scheduling jobs with tight deadlines and shows that it is 1-competitive when using a processor that is only o(1) times faster.
tilings of rectangles with t-tetrominoes. we prove that any two tilings of a rectangular region by t-tetrominoes are connected by moves involving only 2 and 4 tiles. we also show that the number of such tilings is an evaluation of the tutte polynomial. the results are extended to a more general class of regions.
choosing starting values for certain newton-raphson iterations. we aim at finding the best possible seed values when computing a1/p using the newton-raphson iteration in a given interval. a natural choice of the seed value would be the one that best approximates the expected result. it turns out that in most cases, the best seed value can be quite far from this natural choice. when we evaluate a monotone function f(a) in the interval [amin, amax], by building the sequence xn defined by the newton-raphson iteration, the natural choice consists in choosing x0 equal to the arithmetic mean of the endpoint values. this minimizes the maximum possible distance between x0 and f(a). and yet, if we perform n iterations, what matters is to minimize the maximum possible distance between xn and f(a). in several examples, the value of the best starting point varies rather significantly with the number of iterations.
tractable disjunctions of linear constraints: basic results and applications to temporal reasoning. we study the problems of deciding consistency and performing variable elimination for disjunctions of linear inequalities and disequations with at most one inequality per disjunction. this new class of constraints extends the class of generalized linear constraints originally studied by lassez and mcaloon. we show that deciding consistency of a set of constraints in this class can be done in polynomial time. we also present a variable elimination algorithm which is similar to fourier's algorithm for linear inequalities. finally, we use these results to provide new temporal reasoning algorithms for the ord-horn subclass of allen's interval formalism. we also show that there is no low level of local consistency that can guarantee global consistency for the ord-horn subclass. this property distinguishes the ord-horn subclass from the pointizable subclass (for which strong 5-consistency is sufficient to guarantee global consistency), and the continuous endpoint subclass (for which strong 3-consistency is sufficient to guarantee global consistency). copyright 2001. elsevier science b.v.
the cnn problem and other k-server variants. we study several interesting variants of the k-server problem. in the cnn problem, one server services requests in the euclidean plane. the difference from the k-server problem is that the server does not have to move to a request, but it has only to move to a point that lies in the same horizontal or vertical line with the request. this, for example, models the problem faced by a crew of a certain news network trying to shoot scenes on the streets of manhattan from a distance; for any event at an intersection, the crew has only to be on a matching street or avenue. the cnn problem contains as special cases two important problems: the bridge problem, also known as the cow-path problem, and the weighted 2-server problem in which the 2 servers may have different speeds. we show that any deterministic online algorithm has competitive ratio at least 6 + √17. we also show that some successful algorithms for the k-server problem fail to be competitive. in particular, no memoryless randomized algorithm can be competitive.we also consider another variant of the k-server problem, in which servers can move simultaneously, and we wish to minimize the time spent waiting for service. this is equivalent to the regular k-server problem under the l∞ norm for movement costs. we give a ½ k(k + 1) upper bound for the competitive ratio on trees.
time complexity of radio broadcasting: adaptiveness vs. obliviousness and randomization vs. determinism. we consider the time of broadcasting in ad hoc radio networks modeled as undirected graphs. in such networks, every node knows only its own label and a linear bound on the number of nodes but is unaware of the topology of the network, or even of its own neighborhood. our aim is to study to what extent the availability of two important characteristics of a broadcasting algorithm influences optimal broadcasting time. these characteristics are adaptiveness and randomization. our contribution is establishing upper and lower bounds on optimal broadcasting time for three classes of algorithms: adaptive deterministic, oblivious randomized and oblivious deterministic. in two cases we present tight bounds, and in one case a small gap remains. we show that for deterministic adaptive algorithms time ω(n) is required even for n-node networks of constant diameter. this lower bound is strongest possible, since linear time algorithms are known, and hence establishes optimal time θ(n) for this class. for oblivious randomized algorithms we show an upper bound o(n min{d, log n}) and a lower bound ω(n) on optimal expected broadcasting time in n-node networks of diameter d. finally, for oblivious deterministic algorithms we show matching upper and lower bounds θ(n min{d, √n}) on optimal broadcasting time. our results imply that enforcing obliviousness has at least as strong negative impact on broadcasting time as enforcing determinism, and that algorithms having both these features are strictly less efficient than those having only one of them.
partial algebras, meaning categories and algebraization. many approaches to natura language semantics are essentially model-theoretic, typically cast in type theoretic terms. many linguists have adopted type theory or many-sorted algebras [see h. hendriks, compositionality and model-theoretic interpretation, j. logic, language inform. 10 (2001) 29-48 and references therein]. however, recently hodges [formal features of compositionality, j. logic, language inform. 10 (2001) 7-28] has offered an approach to compositionality using just partial algebras. an approach in terms of partial algebras seems at the outset more justified, since the typing is often just artificially superimposed on language (and makes many words massively polymorphic). on the other hand, many-sorted algebras are easier to handle than partial algebras, and are therefore generally preferred. this paper investigates the dialectics between partial algebras and many-sorted algebras and tries to set the background for an approach in the spirit of hodges [formal features of compositionality, j. logic, language inform. 10 (2001) 7-28], which also incorporates insights from algebraic logic, in particular from blok and pigozzi [algebraizable logics, mem. amer. math. soc. 77 (396) (1990)]. the analytic methods that we shall develop here shall also be applied to combinatory algebras and algebraizations of predicate logic.
mixed hypergraphs with bounded degree: edge-coloring of mixed multigraphs. a mixed hypergraph h is a triple (v, c, d) where v is its vertex set and c and d are families of subsets of v (c-edges and d-edges). the degree of a vertex is the number of edges in which it is contained. a vertex coloring of h is proper if each c-edge contains two vertices with the same color and each d-edge contains two vertices with different colors. the feasible set of h is the set of all k's such that there exists a proper coloring using exactly k colors. the lower (upper) chromatic number of h is the minimum (maximum) number in the feasible set.we restrict our attention to mixed hypergraphs with maximum degree two; those with maximum degree three are not simpler than general ones. mixed hypergraphs with maximum degree two were suggested as an interesting subclass of mixed hypergraphs in voloshin (austral. j. combin. 11 (1995) 25-45). we prove that feasible sets of mixed hypergraphs with maximum degree two are intervals. we present a linear time algorithm for determining the lower chromatic number, a linear 5/3-approximation algorithm and a polynomial 3/2-approximation algorithm for the upper chromatic number. we prove that there is no ptas for the upper chromatic number unless p = np.
it is tough to be a plumber. in the linux computer game kplumber, the objective is to rotate tiles in a raster of squares so as to complete a system of pipes. we give a complexity classification for the original game and various special cases of it that arise from restricting the set of six possible tiles.most of the cases are np-complete. one polynomially solvable case is settled by formulating it as a perfect matching problem; other polynomial cases are settled by simple sweepline techniques. moreover, we show that all the unsettled cases are polynomial time equivalent.
approximate maxima finding of continuous functions under restricted budget. a function is distributed among nodes of a graph in a &ldquo;continuous&rdquo; (or &ldquo;slowly changing&rdquo;) way, i.e., such that the difference between values stored at adjacent nodes is small. the goal is to find a node of maximum value by probing some nodes under a restricted budget. every node has an associated cost which has to be paid for probing it and a probe reveals the value of the node. if the total budget is too small to allow probing every node, it is impossible to find the maximum value in the worst case. hence we seek an approximate maxima finding (amf) algorithm that offers the best worst-case guarantee g, i.e., for any continuous distribution of values it finds a node whose value differs from the maximum value by at most g. amf in graphs is related to a generalization of the multicenter problem and we get new results for this problem as well. for example, we give a polynomial algorithm to find a minimum cost solution for the multicenter problem on a tree, with arbitrary node costs. &mdash;authors' abstract
encoding hamiltonian circuits into multiplicative linear logic. we give a new proof of the np-completeness of multiplicative linear logic without constants by a direct encoding of the hamiltonian circuit decision problem.