waashk/dblp huggingface dataset:
new applications of clique separator decomposition for the maximum weight stable set problem. graph decompositions such as decomposition by clique separators and modular decomposition are of crucial importance for designing efficient graph algorithms. clique separators in graphs were used by tarjan as a divide-and-conquer approach for solving various problems such as the maximum weight stable set (mws) problem, colouring and minimum fill-in. the basic tool is a decomposition tree of the graph whose leaves have no clique separator (so-called atoms), and the problem can be solved efficiently on the graph if it is efficiently solvable on its atoms. we give new examples where the clique separator decomposition works well for the mws problem; our results improve and extend various recently published results. in particular, we describe the atom structure for some new classes of graphs whose atoms are p"5-free (the p"5 is the induced path with five vertices) and obtain new polynomial time results for the mws problem. the complexity of this problem on the class of p"5-free graphs is still unknown.
languages generated by iterated idempotency. duplication languages are generated from an initial word by iterated application of string-rewriting rules of the form u->uu. in several recent articles such languages have been investigated with a main focus on finding their placement in the chomsky hierarchy. we generalize the generating rules to u^m->u^n with arbitrary m and n. when the length of the factor u is a fixed number, most cases result in regular languages. if there is just some bound on the length, then often non-regular but always context-free languages are generated. the regularity conditions for both variants are fully characterized, and confluence for the underlying rewrite relations is determined. for the unrestricted case only some results are presented which carry over from restricted variants.
all minimal prime extensions of hereditary classes of graphs. the substitution composition of two disjoint graphs g"1 and g"2 is obtained by first removing a vertex x from g"2 and then making every vertex in g"1 adjacent to all neighbours of x in g"2. let f be a family of graphs defined by a set z of forbidden configurations. giakoumakis [v. giakoumakis, on the closure of graphs under substitution, discrete mathematics 177 (1997) 83-97] proved that f^*, the closure under substitution of f, can be characterized by a set z^* of forbidden configurations - the minimal prime extensions of z. he also showed that z^* is not necessarily a finite set. since substitution preserves many of the properties of the composed graphs, an important problem is the following: find necessary and sufficient conditions for the finiteness of z^*. giakoumakis [v. giakoumakis, on the closure of graphs under substitution, discrete mathematics 177 (1997) 83-97] presented a sufficient condition for the finiteness of z^* and a simple method for enumerating all its elements. since then, many other researchers have studied various classes of graphs for which the substitution closure can be characterized by a finite set of forbidden configurations. the main contribution of this paper is to completely solve the above problem by characterizing all classes of graphs having a finite number of minimal prime extensions. we then go on to point out a simple way for generating an infinite number of minimal prime extensions for all the other classes of f^*.
well-definedness and semantic type-checking for the nested relational calculus. the well-definedness problem for a programming language consists of checking, given an expression and an input type, whether the semantics of the expression is defined for all inputs adhering to the input type. a related problem is the semantic type-checking problem which consists of checking, given an expression, an input type, and an output type whether the expression always returns outputs adhering to the output type on inputs adhering to the input type. both problems are undecidable for general-purpose programming languages. in this paper we study these problems for the nested relational calculus, a specific-purpose database query language. we also investigate how these problems behave in the presence of programming language features such as singleton coercion and type tests.
conjunctive query evaluation by search-tree revisited. the most natural and perhaps most frequently used method for testing membership of an individual tuple in a conjunctive query is based on searching trees of partial solutions, or search-trees. we investigate the question of evaluating conjunctive queries with a time-bound guarantee that is measured as a function of the size of the optimal search-tree. we provide an algorithm that, given a database d, a conjunctive query q, and a tuple a, tests whether q(a) holds in d in time bounded by a polynomial in (sn)^l^o^g^k(sn)^l^o^g^l^o^g^n and n^r, where n is the size of the domain of the database, k is the number of bound variables of the conjunctive query, s is the size of the optimal search-tree, and r is the maximum arity of the relations. in many cases of interest, this bound is significantly smaller than the n^o^(^k^) bound provided by the naive search-tree method. moreover, our algorithm has the advantage of guaranteeing the bound for any given conjunctive query. in particular, it guarantees the bound for queries that admit an equivalent form that is much easier to evaluate, even when finding such a form is an np-hard task. concrete examples include the conjunctive queries that can be non-trivially folded into a conjunctive query of bounded size or bounded treewidth. all our results translate to the context of constraint-satisfaction problems via the well-publicized correspondence between both frameworks.
connectionist modal logic: representing modalities in neural networks. modal logics are amongst the most successful applied logical systems. neural networks were proved to be effective learning systems. in this paper, we propose to combine the strengths of modal logics and neural networks by introducing connectionist modal logics (cml). cml belongs to the domain of neural-symbolic integration, which concerns the application of problem-specific symbolic knowledge within the neurocomputing paradigm. in cml, one may represent, reason or learn modal logics using a neural network. this is achieved by a modalities algorithm that translates modal logic programs into neural network ensembles. we show that the translation is sound, i.e. the network ensemble computes a fixed-point meaning of the original modal program, acting as a distributed computational model for modal logic. we also show that the fixed-point computation terminates whenever the modal program is well-behaved. finally, we validate cml as a computational model for integrated knowledge representation and learning by applying it to a well-known testbed for distributed knowledge representation. this paves the way for a range of applications on integrated knowledge representation and learning, from practical reasoning to evolving multi-agent systems.
computability of analog networks. we define a general concept of a network of analog modules connected by channels, processing data from a metric space a, and operating with respect to a global continuous clock t. the inputs and outputs of the network are continuous streams u:t->a, and the input-output behaviour of the network with system parameters from a is modelled by a function @f:a^rxc[t,a]^p->c[t,a]^q(p,q>0,r>=0), where c[t,a] is the set of all continuous streams equipped with the compact-open topology. we give an equational specification of the network, and a semantics which involves solving a fixed point equation over c[t,a] using a contraction principle based on the fact that c[t,a] can be approximated locally by metric spaces. we show that if the module functions are continuous then so is the network function @f. we analyse in detail two case studies involving mechanical systems. finally, we introduce a custom-made concrete computation theory over c[t,a] and show that if the module functions are concretely computable then so is @f.
accepting networks of splicing processors: complexity results. in this paper we consider a new, bio-inspired computing model: the accepting network of splicing processors. we define two computational complexity classes based on this model and show how they are related to the classical ones defined for turing machines, namely np and pspace. furthermore, we approach the topic of problem solving using these newly defined devices. in this context, a linear time solution for one of the most interesting np-complete problems, the sat problem, is presented. the results presented here suggest once more that nondeterminism might be approached in a deterministic way by means of multiplicities.
horn axiomatizations for sequential data. we propose a notion of deterministic association rules for ordered data. we prove that our proposed rules can be formally justified by a purely logical characterization, namely, a natural notion of empirical horn approximation for ordered data which involves background horn conditions; these ensure the consistency of the propositional theory obtained with the ordered context. the whole framework resorts to concept lattice models from formal concept analysis, but adapted to ordered contexts. we also discuss a general method to mine these rules that can be easily incorporated into any algorithm for mining closed sequences, of which there are already some in the literature.
can newtonian systems, bounded in space, time, mass and energy compute all functions? in the theoretical analysis of the physical basis of computation there is a great deal of confusion and controversy (e.g., on the existence of hyper-computers). first, we present a methodology for making a theoretical analysis of computation by physical systems. we focus on the construction and analysis of simple examples that are models of simple sub-theories of physical theories. then we illustrate the methodology by presenting a simple example for newtonian kinematics, and a critique that leads to a substantial extension of the methodology. the example proves that for any set a of natural numbers there exists a 3-dimensional newtonian kinematic system m"a, with an infinite family of particles p"n whose total mass is bounded, and whose observable behaviour can decide whether or not n@?a for all n@?n in constant time. in particular, the example implies that simple newtonian kinematic systems that are bounded in space, time, mass and energy can compute all possible sets and functions on discrete data. the system is a form of marble run and is a model of a small fragment of newtonian kinematics. next, we use the example to extend the methodology. the marble run shows that a formal theory for computation by physical systems needs strong conditions on the notion of experimental procedure and, specifically, on methods for the construction of equipment. we propose to extend the methodology by defining languages to express experimental procedures and the construction of equipment. we conjecture that the functions computed by experimental computation in newtonian kinematics are ''equivalent'' to those computed by algorithms, i.e. the partial computable functions.
on the structure and complexity of worst-case equilibria. in the resource allocation game introduced by koutsoupias and papadimitriou, n jobs of different weights are assigned to m identical machines by selfish agents. for this game, it has been conjectured by several authors that the fully mixed nash equilibrium (fmne) is the worst possible w.r.t. the expected maximum load over all machines. assuming the validity of this conjecture, computing a worst-case nash equilibrium for a given instance was trivial, and approximating the price of anarchy for this instance would be possible by approximating the expected social cost of the fmne by applying a known fpras. we present a counter-example to this conjecture showing that fully mixed nash equilibria cannot be used to approximate the price of anarchy. we show that the factor between the social cost of the worst nash equilibrium and the social cost of the fmne can be as large as the price of anarchy itself, up to a constant factor. in addition, we present an algorithm that constructs so-called concentrated equilibria that approximate the worst-case nash equilibria within constant factors.
rewriting queries using views with access patterns under integrity constraints. we study the problem of rewriting queries using views in the presence of access patterns, integrity constraints, disjunction and negation. we provide asymptotically optimal algorithms for (1) finding minimally containing and (2) maximally contained rewritings respecting the access patterns (which we call executable) and for (3) deciding whether an exact executable rewriting exists. we show that rewriting queries using views in this case reduces (a) to rewriting queries with access patterns and constraints without views and also (b) to rewriting queries using views under constraints without access patterns. we show how to solve (a) directly and how to reduce (b) to rewriting queries under constraints only (semantic optimization). these reductions provide two separate routes to a unified solution for problems 1, 2 and 3 based on an extension of the relational chase theory to queries and constraints with disjunction and negation. we also handle equality and arithmetic comparisons. we also show that in an information integration setting, maximally contained rewritings are given by the certain answers (under the usual semantics) for a set of constraints derived from the binding patterns. that is, except for defining the appropriate constraints, binding patterns do not need special treatment. finally, we show that if there is an exact executable rewriting, there is an executable rewriting which is a union of conjunctive queries with negation.
a note on discreteness and virtuality in analog computing. the need for physically motivated discreteness and finiteness conditions emerges in models of both analog and digital computing that are genuinely concerned with physically realizable computational processes. this is brought out by a critical examination of notional analog superturing devices which involve physically untenable idealizations about the perfect functioning of analog apparatuses and infinite precision of physical measurements. the capability for virtual behaviour, that is, the capability of interpreting, storing, transforming, creating the code, and thereby mimicking the behaviour of (turing) machines, is used here to introduce a new dimension in the discussion of the analog-digital watershed. in the light of recent results on the analog simulation of digital computing, we examine the role of virtuality as a discriminating factor between these two species of computing, and immerse this problem in the context of natural computing. is virtuality instantiated in parts of the natural world other than computer technology? this broad issue is examined in connection with the computational modelling of brain and mental information processing.
quorum sensing p systems. this paper continues the investigation of population p systems model [f. bernardini, m. gheorghe, population p systems, journal of universal computer science 10 (5) (2004) 509-539] by considering bacterium quorum sensing (qs) phenomena as the basis of the new approach. a new computational model called qs p system is introduced. it is proved that qs p systems are able to simulate counter machines, and hence they are equivalent in power to turing machines. an example of a qs p system modelling the behaviour of vibrio fischeri bacteria colonies is also presented and the emergence of the qs mechanism is illustrated.
influence of data dimensionality on the quality of forecasts given by a multilayer perceptron. one of the phenomena that can be observed when using neural networks for time series prediction is that the quality of the forecasts obtained is correlated with the dimensionality of the data. higher data dimensionality leads, in most cases, to higher prediction errors. this phenomenon is connected by some authors to the decrease in variance of the distances between the data points, which occurs when the lengths of the predicted vectors increase. in this paper, a proof is given that the variance of the distances between data points also decreases with the so-called correlation dimension of the data. therefore, a drop in forecast quality might be expected not only when the lengths of the data vectors are increased, but also when using vectors of the same length to represent data of increasing dimensionality. we also present some experimental results that illustrate the dependence between data dimensionality and the variance of the distances between the data points, and the forecast error obtained when using a multilayer perceptron to predict future values of some time series.
optimal workload-based weighted wavelet synopses. in recent years wavelets were shown to be effective data synopses. we are concerned with the problem of finding efficiently wavelet synopses for massive data sets, in situations where information about query workload is available. we present linear time, i/o optimal algorithms for building optimal workload-based wavelet synopses for point queries. the synopses are based on a novel construction of weighted inner products and use weighted wavelets that are adapted to those products. the synopses are optimal in the sense that the subset of retained coefficients is the best possible for the bases in use with respect to either the mean-squared absolute or relative errors. for the latter, this is the first optimal wavelet synopsis even for the regular, non-workload-based case. experimental results demonstrate the advantage obtained by the new optimal wavelet synopses.
view-based query processing: on the relationship between rewriting, answering and losslessness. as a result of the extensive research in view-based query processing, three notions have been identified as fundamental, namely rewriting, answering, and losslessness. answering amounts to computing the tuples satisfying the query in all databases consistent with the views. rewriting consists in first reformulating the query in terms of the views and then evaluating the rewriting over the view extensions. losslessness holds if we can answer the query by solely relying on the content of the views. while the mutual relationship between these three notions is easy to identify in the case of conjunctive queries, the terrain of notions gets considerably more complicated going beyond such a query class. in this paper, we revisit the notions of answering, rewriting, and losslessness and clarify their relationship in the setting of semistructured databases, and in particular for the basic query class in this setting, i.e., two-way regular path queries. our first result is a clean explanation of the relationship between answering and rewriting, in which we characterize rewriting as a ''linear approximation'' of query answering. we show that applying this linear approximation to the constraint-satisfaction framework yields an elegant automata-theoretic approach to query rewriting. as for losslessness, we show that there are indeed two distinct interpretations for this notion, namely with respect to answering, and with respect to rewriting. we also show that the constraint-theoretic approach and the automata-theoretic approach can be combined to give algorithmic characterization of the various facets of losslessness. finally, we deal with the problem of coping with loss, by considering mechanisms aimed at explaining lossiness to the user.
universality results for p systems based on brane calculi operations. operations with membranes are essential both in brane calculi as well as in membrane computing. in this paper, we attempt to express six basic operations of brane calculi, viz., pino, exo, phago, bud, mate, drip in terms of the membrane computing formalism. we also investigate the computing power of p systems controlled by phago/exo, pino/exo, bud/mate as well as the mate/drip operations. we give an improvement to a characterization of re using mate/drip operations given in [l. cardelli, gh. paun, an universality result based on mate/drip operations, international journal of foundations of computer science (in press)]. we also give a characterization of re using a new operation, called selective mate. we conjecture that it is not possible to obtain turing completeness using only one of the six operations. we also conjecture that the pairs of operations we have considered for completeness, in this paper, are complete: it is impossible to obtain turing completeness with any other pair of operations.
axiomatizing the identities of binoid languages. we present a nontrivial axiomatization for the equational theory of binoid languages, the subsets of a free binoid. in doing so, we prove that a conjecture given in our previous paper was true: the identical laws of ordinary (string) languages, written separately using 'horizontal' and 'vertical' operation symbols form a required complete system of axioms.
quasiperiodic sturmian words and morphisms. we characterize all quasiperiodic sturmian words: a sturmian word is not quasiperiodic if and only if it is a lyndon word. moreover, we study links between sturmian morphisms and quasiperiodicity.
using well-structured transition systems to decide divergence for catalytic p systems. p systems are a biologically inspired model introduced by gheorghe paun with the aim of representing the structure and the functioning of the cell. since their introduction, several variants of p systems have been proposed and explored. we concentrate on the class of catalytic p systems without priorities associated with the rules. we show that the theory of well-structured transition systems can be used to decide the divergence problem (i.e. checking for the existence of an infinite computation) for such a class of p systems. as a corollary, we obtain an alternative proof of the nonuniversality of deterministic catalytic p systems, an open problem recently solved by ibarra and yen.
convergence analysis of the ojan mca learning algorithm by the deterministic discrete time method. minor component analysis (mca) is a statistical method of extracting the eigenvector associated with the smallest eigenvalue of the covariance matrix of input signals. convergence is essential for mca algorithms towards practical applications. traditionally, the convergence of mca algorithms is indirectly analyzed via their corresponding deterministic continuous time (dct) systems. however, the dct method requires the learning rate to approach zero, which is not reasonable in many applications due to the round-off limitation and tracking requirements. this paper studies the convergence of the deterministic discrete time (ddt) system associated with the ojan mca learning algorithm. unlike the dct method, the ddt method does not require the learning rate to approach zero. in this paper, some important convergence results are obtained for the ojan mca learning algorithm via the ddt method. simulations are carried out to illustrate the theoretical results achieved.
on rearrangeable multirate three-stage clos networks. since 1989 when melen and turner introduced an elegant model for interconnection networks that carry multirate traffic, the theory and applications of the three-stage clos network has been extended from circuit switching to the multirate environment. chung and ross conjectured that c(n,2n-1,r) is rearrangeable if each call has weight chosen from a given set of k weights. lin et al. confirmed the conjecture for a restricted discrete bandwidth case only. in this paper we show that the conjecture of chung and ross holds not only in the discrete bandwidth case but also in the continuous bandwidth case for r@?2n5-235.