waashk/dblp huggingface dataset:
transformations of clp modules. we propose a transformation system for clp programs and modules. the framework is inspired by the one of tamaki and sato for pure logic programs. however, the use of clp allows us to introduce some new operations such as splitting and constraint replacement. we provide two sets of applicability conditions. the first one guarantees that the original and the transformed programs have the same computational behaviour, in terms of answer constraints. the second set contains more restrictive conditions that ensure compositionality: we prove that under these conditions the original and the transformed modules have the same answer constraints also when they are composed with other modules. this result is proved by first introducing a new formulation, in terms of trees, of a resultants semantics for clp. as corollaries we obtain the correctness of both the modular and the non-modular system w.r.t. the least model semantics.
characterizing bipartite toeplitz graphs. a toeplitz graph is a symmetric graph whose adjacency matrix is toeplitz. if such a graph has neither loops nor multiple edges it can be defined by a 0-1 sequence. in euler et al. (in: ku tung-hsin (ed.), combinatorics and graph theory '95, vol. 1, academia sinica, world scientific, singapore, 1995, pp. 119-130) infinite, bipartite toeplitz graphs have been fully characterized. in this paper we complete these results by some structural and algorithmic properties and then turn ourselves to study the .nite case. we present a complete solution for bipartite toeplitz graphs that are defined by a 0-1 sequence with two 1-entries, and we present several partial results for those defined by a 0-1 sequence with three 1-entries.
on the complexity of finding common approximate substrings. problems associated with finding strings that are within a specified hamming distance of a given set of strings occur in several disciplines. in this paper, we use techniques from parameterized complexity to assess non-polynomial time algorithmic options and complexity for the common approximate substring (cas) problem. our analyses indicate under which parameter restrictions useful algorithms are possible, and include both class membership and parameterized reductions to prove class hardness. in order to achieve fixed-parameter tractability, either a fixed string length or both a fixed size alphabet and fixed substring length are sufficient. fixing either the string length or the alphabet size and hamming distance is shown to be necessary, unless w[1] = fpt. an assortment of parameterized class membership and hardness results cover all other parameterized variants, showing in particular the effect of fixing the number of strings.
a multi-scale constraint programming model of alternative splicing regulation. alternative splicing is a key process in post-transcriptional regulation, by which different mature rna can be obtained from the same premessenger rna. the resulting combinatorial complexity contributes to biological diversity, especially in the case of the human immunodeficiency virus hiv-1. using a constraint programming approach, we develop a model of the alternative splicing regulation in hiv-1. our model integrates different scales (single site vs. multiple sites), and thus allows us to exploit several types of experimental data available to us.
on the parametric complexity of schedules to minimize tardy tasks. given a set t of tasks, each of unit length and having an individual deadline d(t) ∈ z+, a set of precedence constraints on t, and a positive integer k ≤ |t|, we can ask "is there a one-processor schedule for t that obeys the precedence constraints and contains no more than k late tasks?" this is a well-known np-complete problem.we might also inquire "is there a one-processor schedule for t that obeys the precedence constraints and contains at least k tasks that are on time i.e. no more than |t| - k late tasks?"within the framework of classical complexity theory, these two questions are merely different instances of the same problem. within the recently developed framework of parameterized complexity theory, however, they give rise to two separate problems that may be studied independently of one another.we investigate these problems from the parameterized point of view. we show that, in the general case, both these problems are hard for the parameterized complexity class w[1].in contrast, in the case where the set of precedence constraints can be modelled by a partial order of bounded width, we show that both these problems are fixed parameter tractable.
on finding short resolution refutations and small unsatisfiable subsets. we consider the parameterized problems of whether a given set of clauses can be refuted within k resolution steps, and whether a given set of clauses contains an unsatisfiable subset of size at most k. we show that both problems are complete for the class w[1], the first level of the w-hierarchy of fixed-parameter intractable problems. our results remain true if restricted to 3-sat instances and/or to various restricted versions of resolution including tree-like resolution, input resolution, and read-once resolution. applying a metatheorem of frick and grohe, we show that, restricted to classes of sets of clauses of locally bounded treewidth, the considered problems are fixed-parameter tractable. for example, the problems are fixed-parameter tractable for planar cnf formulas.
a pumping lemma for random permitting context languages. random context grammars belong to the class of context-free grammars with regulated rewriting. their productions depend on context that may be randomly distributed in a sentential form. context is classified as either permitting or forbidding, where permitting context enables the application of a production and forbidding context inhibits it. for random context languages of finite index a generalization of the well-known pumping lemma for context-free languages has been proven. we drop the finite index restriction and concentrate on non-erasing grammars that use permitting context only. we prove a pumping lemma for their languages that generalizes and refines the existing one, and show that these grammars are strictly weaker than the non-erasing random context grammars
kolmogorov complexities , on computable partially ordered sets. we introduce a machine free mathematical framework to get a natural formalization of some general notions of infinite computation in the context of kolmogorov complexity. namely, the classes maxp rx → d and maxrecx → d of functions x → d which are pointwise maximum of partial or total computable sequences of functions where d = (d, <) is some computable partially ordered set. the enumeration theorem and the invariance theorem always hold for maxp rx → d, leading to a variant kmaxd of kolmogorov complexity. we characterize the orders d such that the enumeration theorem (resp. the invariance theorem) also holds for maxrecx → d. it turns out that maxrecx → d may satisfy the invariance theorem but not the enumeration theorem. also, when maxrecx → d satisfies the invariance theorem then the kolmogorov complexities associated to maxrecx → d and maxp rx → d are equal (up to constant).letting kmind = kmaxdrev where drev is the reverse order, we prove that either kmind = ctkmaxd = ctkd (=ct is equality up to a constant) or kmind, kmaxdare ≤ ct incomparable and <ct kd and > ct k0',d. we characterize the orders leading to each case. we also show that kmind, kmaxd cannot be both much smaller than kd at any point.these results are proved in a more general setting with two orders on d, one extending the other.
a -enumeration of convex polyominoes by the festoon approach. in 1938, pólya stated an identity involving the perimeter and area generating function for parallelogram polyominoes. to obtain that identity, pólya presumably considered festoons. a festoon (so named by flajolet) is a closed path w which can be written as w = uv, where each step of u is either (1, 0) or (0, 1), and each step of v is either (-1, 0) or (0, -1).in this paper, we introduce four new festoon-like objects. as a result, we obtain explicit expressions (and not just identities) for the generating functions of parallelogram polyominoes, directed convex polyominoes, and convex polyominoes.
interactive observability in ludics: the geometry of tests. ludics [j.-y. girard, locus solum, math. structures in comput. sci. 11 (2001) 301-506] is a recent proposal of analysis of interaction, developed by abstracting away from proof-theory. it provides an elegant, abstract setting in which interaction between agents (proofs/programs/processes) can be studied at a foundational level, together with a notion of equivalence from the point of view of the observer.an agent should be seen as some kind of black box. an interactive observation on an agent is obtained by testing it against other agents.in this paper we explore what can be observed interactively in this setting. in particular, we characterize the objects that can be observed in a single test: the primitive observables of the theory.our approach builds on an analysis of the geometrical properties of the agents, and highlights a deep interleaving between two partial orders underlying the combinatorial structures: the spatial one and the temporal one.
data exchange: semantics and query answering. data exchange is the problem of taking data structured under a source schema and creating an instance of a target schema that reflects the source data as accurately as possible. in this paper, we address foundational and algorithmic issues related to the semantics of data exchange and to the query answering problem in the context of data exchange. these issues arise because, given a source instance, there may be many target instances that satisfy the constraints of the data exchange problem.we give an algebraic specification that selects, among all solutions to the data exchange problem, a special class of solutions that we call universal. we show that a universal solution has no more and no less data than required for data exchange and that it represents the entire space of possible solutions. we then identify fairly general, yet practical, conditions that guarantee the existence of a universal solution and yield algorithms to compute a canonical universal solution efficiently. we adopt the notion of the "certain answers" in indefinite databases for the semantics for query answering in data exchange. we investigate the computational complexity of computing the certain answers in this context and also address other algorithmic issues that arise in data exchange. in particular, we study the problem of computing the certain answers of target queries by simply evaluating them on a canonical universal solution, and we explore the boundary of what queries can and cannot be answered this way, in a data exchange setting.
decomposable multi-parameter matroid optimization problems. a framework for solving certain multi-dimensional parametric matroid optimization problems in randomized linear time by prune-and-search is presented. the common feature of these problems, which include the multi-parameter minimum spanning tree problem on planar and dense graphs, is that their fixed-parameter versions are solvable by tournament-like algorithms whose structure is represented by a balanced decomposition tree.
the do-all problem with byzantine processor failures. do-all is the abstract problem of using n processors to cooperatively perform m independent tasks in the presence of failures. this problem and its derivatives have been a centerpiece in the study of trade-offs between efficiency and fault-tolerance in cooperative computing environments. many algorithms have been developed for do-all in various models of computation, including message-passing, partitionable networks, and shared-memory models under a variety of failure models.this work initiates the study of the do-all problem for synchronous message-passing processors prone to byzantine failures. in particular, upper and lower bounds are given on the complexity of do-all for several cases: (a) the case where the maximum number of faulty processors f is known a priori, (b) the case where f is not known, (c) the case where a task execution can be verified (without re-executing the task), and (d) the case where task executions cannot be verified. the efficiency of algorithms is evaluated in terms of work and message complexities. the work complexity accounts for all computational steps taken by the processors and the message complexity accounts for all messages sent by the processors during the computation. the work and messages of a faulty processor are counted only until the processor fails to follow the algorithm. it is shown that in some cases obtaining work θ(mn) is the best one can do. it is also shown that in certain cases communication cannot help improve work efficiency.
operational equivalence for interaction nets. the notion of contextual (or operational) equivalence is fundamental in the theory of programming languages. by setting up a notion of bisimilarity, and showing that it coincides with contextual equivalence, one obtains a simple coinductive proof technique for showing that two programs are equivalent in all contexts. in this paper we apply these (now standard) techniques to interactions nets, a graphical programming language characterized by local reduction. this work generalizes previous studies of operational equivalence in typed interaction nets since it can be applied to untyped systems, thus all systems of interaction nets are captured.
cubical local partial orders on cubically subdivided spaces - existence and construction. the geometric models of higher dimensional automata (hda) and dijkstra's pv-model are cubically subdivided topological spaces with a local partial order. if a cubicalization of a topological space is free of immersed cubic möbius bands, then there are consistent choices of direction in all cubes, such that any n-cube in the cubic subdivision is dihomeomorphic to [0, 1]n with the induced partial order from rn. after subdivision once, any cubicalized space has a cubical local partial order. in particular, all triangularized spaces have a cubical local partial order. this implies in particular that the underlying geometry of an hda may be quite complicated.
algebraic topology and concurrency. we show in this article that some concepts from homotopy theory, in algebraic topology, are relevant for studying concurrent programs. we exhibit a natural semantics of semaphore programs, based on partially ordered topological spaces, which are studied up to "elastic deformation" or homotopy, giving information about important properties of the program, such as deadlocks, unreachables, serializability, essential schedules, etc. in fact, it is not quite ordinary homotopy that has to be used, but rather a "directed homotopy" that does not reverse the flow of time. we show some of the essential differences between ordinary and directed homotopy through examples. we also relate the topological view to a combinatorial view of concurrent programs closer to transition systems, through the notion of a cubical set. finally we apply some of these concepts to the proof of the safeness of a two-phase protocol, well-known and used in concurrent database theory. we end up with a list of problems from both a mathematical and a computer-scientific point of view.
even linear simple matrix languages: formal language properties and grammatical inference. we show that so-called deterministic even linear simple matrix grammars can be inferred in polynomial time using the query-based learner-teacher model (minimally adequate teacher-learning model) proposed by angluin (inform. and comput. 75 (1987) 87) for learning deterministic regular languages. in this way, we extend the class of efficiently learnable languages beyond both the even linear languages and the even equal matrix languages (pattern recognition 21 (1988) 55; proc. 2nd internat. colloq. on grammatical inference (icgi-94): grammatical inference and applications, lecture notes in computer science/lecture notes in artificial intelligence, vol. 862, springer, berlin, 1994, p. 38; inform. process. lett. 28 (1988) 193; technical report iias-rr-93-6e, fujitsu laboratories, 1992; parallel image analysis, icpia'92, lecture notes in computer science, vol. 652, springer, berlin, 1992, p. 274; inform. and comput. 123 (1995) 138; algorithmic learning for knowledge-based systems, lecture notes in computer science/lecture notes in artificial intelligence, springer, berlin, 1995, p. 317). moreover, we investigate formal language properties of even linear simple matrix languages and related language classes. more precisely, we discuss characterizations, (proper) inclusion relations, closure properties and decidability questions. this way, we also show that, in a certain sense, the idea of iterating the control language approach for learning purposes, as undertook by takada (1995), could be seen as a special case of using deterministic even linear simple matrix grammars as basic and uniform learning target.
identification of function distinguishable languages. we show how appropriately chosen functions f which we call distinguishing can be used to make deterministic finite automata backward deterministic. this idea can be exploited to design regular language classes called f-distinguishable which are identifiable in the limit from positive samples. special cases of this approach are the k-reversible and terminal distinguishable languages, as discussed in angluin (j. assoc. comput. mach. 29 (3) (1982) 741), fernau (technical report wsi-99-23, universität tübingen (germany), wilhelm-schickard-institut für informatik, 1999, short version published in the proceedings of amai 2000, see http://rutcot. rutgers. edu/~amai/aimath00/acceptedcont.htm, proc. 15th internat. conf. on pattern recognition (icpr 2000), vol. 2, ieee press, new york, 2000, pp. 125-128), radhakrishnan (ph.d. thesis, department of computer science and engineering, indian institute of technology, bombay, india, 1987), radhakrishnan and nagaraja (ieee trans. systems, man cybernet. 17 (6) (1987) 982). moreover, we show that all regular languages may be approximated in the setting introduced by kobayashi and yokomori (in: k. p. jantke, t. shinohara, th. zeugmann (eds.), proc. sixth internat. conf. algorithmic learning theory (alt'95), lecture notes in computer science/lecture notes in artificial intelligence, vol. 997, springer, berlin, 1995, pp. 298-312), (theoret. comput. sci. 174 (1997) 251-257) by any class of f-distinguishable languages. observe that the class of all function-distinguishable languages is equal to the class of regular languages.
nonterminal complexity of programmed grammars. we show that, in the case of context-free programmed grammars with appearance checking working under free derivations, three nonterminals are enough to generate every recursively enumerable language. this improves the previously published bound of eight for the nonterminal complexity of these grammars. this also yields an improved nonterminal complexity bound of four for context-free matrix grammars with appearance checking. moreover, we establish an upperbound of four on the nonterminal complexity of context-free programmed grammars without appearance checking working under leftmost derivations of type 2. we derive nonterminal complexity bounds for context-free programmed and matrix grammars with appearance checking or with unconditional transfer working under leftmost derivations of types 2 and 3, as well. more specifically, a first nonterminal complexity bound for context-free programmed grammars with unconditional transfer (working under leftmost derivations of type 3) which depends on the size of the terminal alphabet is proved.
additives of linear logic and normalization - part i: a (restricted) church-rosser property. we define a generalized cut-elimination procedure for proof-nets of fall linear logic (without constants), for which we prove a (restricted) church-rosser property.
frequency of symbol occurrences in bicomponent stochastic models. we give asymptotic estimates of the frequency of occurrences of a symbol in a random word generated by any bicomponent stochastic model. more precisely, we consider the random variable yn, representing the number of occurrences of a given symbol in a word of length n generated at random; the stochastic model is defined by a rational formal series r having a linear representation with two primitive components. this model includes the case when r is the product or the sum of two primitive rational formal series. we obtain asymptotic evaluations for the mean value and the variance of yn and its limit distribution.
on the degree of scattered context-sensitivity. in this paper, we prove that every recursively enumerable language can be generated by a scattered context grammar with no more than two context-sensitive productions.
the go polynomials of a graph. this paper introduces graph polynomials based on a concept from the game of go. suppose that, for each vertex of a graph, we either leave it uncoloured or choose a colour uniformly at random from a set of available colours, with the choices for the vertices being independent and identically distributed. we ask for the probability that the resulting partial assignment of colours has the following property: for every colour class, each component of the subgraph it induces has a vertex that is adjacent to an uncoloured vertex. in go terms, we are requiring that every group is uncaptured. this definition leads to go polynomials for a graph. although these polynomials are based on properties that are less "local" in nature than those used to define more traditional graph polynomials such as the chromatic polynomial, we show that they satisfy recursive relations based on local modifications similar in spirit to the deletion-contraction relation for the chromatic polynomial. we then show that they are #p-hard to compute in general, using a result on linear forms in logarithms from transcendental number theory. we also briefly record some correlation inequalities.
sequential grammars and automata with valences. we discuss the model of valence grammars, a simple extension of context-free grammars. we show closure properties of context-free valence languages over arbitrary monoids. chomsky and greibach normal form theorems and an iteration lemma for context-free valence grammars over the groups zk are proved. the generative power of different control monoids is investigated. in particular, we show that context-free valence grammars over finite monoids or commutative monoids have the same power as valence grammars over finite groups or commutative groups, respectively.
bounded-connect noncanonical discriminating-reverse parsers. the precision of right-hand context covering for conflict resolution is improved over previous ndr parsers, resulting in acceptation of wider subsets of lr-regular and lr-nonregular grammars, including all lalr(k) grammars for a given k. parser generation combines a new form of dr items and subgraph connections of bounded length, without the need to implement subgraph copies. the ndr parser, whose algorithm remains essentially unchanged, is presented as an extended two-stack pushdown automaton. the technique is illustrated with a detailed example.