waashk/dblp huggingface dataset:
parametrized semantics of logic programs--a unifying framework. the different semantics that can be assigned to a logic program correspond to different assumptions made concerning the atoms that are rule heads and whose logical values cannot be inferred from the rules. for example, the well founded semantics corresponds to the assumption that every such atom is false, while the kripke-kleene semantics corresponds to the assumption that every such atom is unknown. in this paper, we propose to unify and extend this assumption-based approach by introducing parameterized semantics for logic programs. the parameter holds the value that one assumes for all rule heads whose logical values cannot be inferred from the rules. we work within multi-valued logic with bilattice structure, and we consider the class of logic programs defined by fitting.following fitting's approach, we define an operator that allows us to compute the parameterized semantic, and to compare and combine semantics obtained for different values of the parameter. we show that our approach captures and extends the usual semantics of conventional logic programs thereby unifying their computation.
automatic workflow verification and generation. correctness is an important aspect of workflow management systems. however, most of the workflow literature focuses only on the modeling aspects and assumes that a workflow is correct if during the execution it respects the control and data dependency specified by the workflow designer. to address the correctness question properly we propose a new workflow model based on hoare semantics that allows to: (1) automatically check if the desired outcome of a workflow can be produced by its actual implementation, (2) automatically synthesize a workflow implementation from the workflow specification and a given task library.in particular we: (1) formalize the semantics of workflows and tasks with pre-and postconditions, (2) for each control construct we provide a set of sound inference rules formalizing its semantics. while most of our workflow constructs are standard, two of them are new: the universal and the existential constructs. we then describe algorithms for automatically checking the correctness of workflows and for automatic workflow generation.
finding the shortest boundary guard of a simple polygon. there are many different kinds of guards in a simple polygon that have been proposed and discussed. in this paper, we consider a new type of guard, boundary guard, which is a guard capable of moving along a boundary of a polygon and every interior point of the polygon can be seen by the mobile guard. we propose an algorithm to 1nd the shortest boundary guard of a simple polygon p in o(n log n) time, where n is the number of vertices of p.
efficient minus and signed domination in graphs. an efficient minus (respectively, signed) dominating function of a graph g = (v,e) is a function f: v → {-1,0,1} (respectively, {-1, 1}) such that σu∈m[v] f(u) = 1 for all v ∈ v, where n[v] = {v} ∪ {u|(u,v) ∈ e}. the efficient minus (respectively, signed) domination problem is to find an efficient minus (respectively, signed) dominating function of g. in this paper, we show that the efficient minus (respectively, signed) domination problem is np-complete on chordal graphs, chordal bipartite graphs, planar bipartite graphs and planar graphs of maximum degree 4 (respectively, on chordal graphs). based on the forcing property on blocks of vertices and automata theory, we provide a uniform approach to show that in a special class of interval graphs, every graph (respectively, every graph with no vertex of odd degree) has an efficient minus (respectively, signed) dominating function. we also give linear-time algorithms to find these functions. besides, we show that the efficient minus domination problem is equivalent to the efficient domination problem on trees.
absolute exponential stability of a class of recurrent neural networks with multiple and variable delays. in this paper, we derive some new conditions for absolute exponential stability (aest) of a class of recurrent neural networks with multiple and variable delays. by using the holder's inequality and the young's inequality to estimate the derivatives of the lyapunov functionals, we are able to establish more general results than some existing ones. the first type of conditions established involves the convex combinations of column-sum and row-sum dominance of the neural network weight matrices, while the second type involves the p-norm of the weight matrices with p ∈ [1, +∞].
the full steiner tree problem. motivated by the reconstruction of phylogenetic tree in biology, we study the full steiner tree problem in this paper. given a complete graph g = (v,e) with a length function on e and a proper subset r ⊆ v, the problem is to find a full steiner tree of minimum length in g, which is a kind of steiner tree with all the vertices of r as its leaves. in this paper, we show that this problem is np-complete and max snp-hard, even when the lengths of the edges are restricted to either 1 or 2. for the instances with lengths either 1 or 2, we give a 8/5-approximation algorithm to find an approximate solution for the problem.
some combinatorial results on bernoulli sets and codes. a bernoulli set is a set x of words over a finite alphabet a such that for any positive bernoulli distribution in a* one has that (x)=1. in the case of a two-letter alphabet a={a,b} a characterization of finite bernoulli sets is given in terms of the function &xi,j counting the number of words of x having i occurrences of the letter a and j occurrences of the letter b. moreover, we also derive a necessary and sufficient condition on the distribution &xi, j which characterizes bernoulli sets which are commutatively equivalent to prefix codes
pseudopalindrome closure operators in free monoids. we consider involutory antimorphisms ϕ of a free monoid a* and their fixed points, called ϕ-palindromes or pseudopalindromes. a ϕ-palindrome reduces to a usual palindrome when ϕ is the reversal operator. for any word w ∈ a* the right (resp. left) ϕ-palindrome closure of w is the shortest ϕ-palindrome having w as a prefix (resp. suffix). we prove some results relating ϕ-palindrome closure operators with periodicity and conjugacy, and derive some interesting closure properties for the languages of finite sturmian and episturmian words. in particular, a finite word w is sturmian if and only if both its palindromic closures are so. moreover, in such a case, both the palindromic closures of w share the same minimal period of w. a new characterization of finite sturmian words follows, in terms of periodicity and special factors of their palindromic closures. some weaker results can be extended to the episturmian case. by using the right ϕ-palindrome closure, we extend the construction of standard episturmian words via directive words. in this way one obtains a family of infinite words, called ϕ-standard words, which are morphic images of episturmian words, as well as a wider family of infinite words including the thue-morse word on two symbols.
some characterizations of finite sturmian words. in this paper, we give some new characterizations of words which are finite factors of sturmian words. an enumeration formula for primitive finite sturmian words is given. moreover, we provide two linear-time algorithms to recognize whether a finite word is sturmian.
relaxed models for rewriting logic. we modify the definition of the models for rewrite theories by replacing the equality of functors, defined by e-equal terms, with the equality via a natural isomorphism, called natural symmetry. the relaxation process can be adapted by relaxing all or only a part of the equations, and by relaxing the state structure (and implicitly the computation structure) or just the computation structure. we also consider the subclasses of c-coherent models, where c is a set of equations specifying a collection of commutative symmetry diagrams. the result is a wide palette of model classes which offers more flexibility in modeling concurrent systems.
algorithms, nymphs, and shepherds. computability and complexity are the two major lines along which the science of algorithms has evolved; but the same concepts guide many human activities. we try to catch some glimpses of the connections between these two worlds, to meet the expectations of the audience. we will encounter nymphs and universal turing machines, ancient traditions and randomized procedures, all tending to the same end: having fun with algorithms.
multitree automata that count. multitree are unranked, unordered trees and occur in many computer science applications like rewriting and logic, knowledge representation, xml queries, typing for concurrent systems, cryptographic protocols, etc. we define constrained multitree automata which accept sets of multitrees where the constraints are expressed in a first-order theory of multisets with counting formulas which is very expressive. we give constructions for union, intersection, determinization. then, we give an algorithm to decide emptiness when the constraints belong to a subclass where counting is limited to distinct elements. we show that many classes of tree automata that have been defined for a wide variety of applications can be seen as instance of our general framework. finally, we describe the quantifier elimination procedure used to decide the theory of constraints.
a partial order semantics approach to the clock explosion problem of timed automata. we present a new approach to the symbolic model checking of timed automata based on a partial order semantics. it relies on event zones that use vectors of event occurrences instead of clock zones that use vectors of clock values grouped in polyhedral clock constraints. we provide a description of the different congruences that arise when we consider an independence relation in a timed framework. we introduce a new abstraction, called catchup equivalence which is defined on event zones and which can be seen as an implementation of one of the (more abstract) previous congruences. this formal language approach helps clarifying what the issues are and which properties abstractions should have. the catchup equivalence yields an algorithm to check emptiness which has the same complexity bound in the worst case as the algorithm to test emptiness in the classical semantics of timed automata. our approach works for the class of timed automata proposed by alur-dill, except for state invariants (an extension including state invariants is discussed informally). first experiments show that the approach is promising and may yield very significant improvements.
the regular viewpoint on pa-processes. pa is the process algebra allowing non-determinism, sequential and parallel compositions, and recursion. we suggest viewing pa-processes astrees, and usingtree-automata techniques for verification problems on pa. our main result is that the set of iterated predecessors of a regular set of pa-processes is a regular tree language, and similarly for iterated successors. furthermore, the corresponding tree automata can be built effectively in polynomial time. this has many immediate applications to verification problems for pa-processes, among which a simple and general model-checking algorithm.
reconstructing permutation matrices from diagonal sums. in this paper, we present a result concerning the reconstruction of permutation matrices from their diagonal sums. the problem of reconstructing a sum of k permutation matrices from its diagonal sums is np-complete. we prove that a simple variant of this problem in which the permutation matrices lie on a cylinder instead of on a plane can be solved in polynomial time. we give an exact, algebraic characterization of the diagonal sums that correspond to a sum of permutation matrices. then, we derive an o(kn2)-time algorithm for reconstructing the sum of k permutation matrices of order n from their diagonal sums. we obtain these results by means of a generalization of a classical theorem of hall on the finite abelian groups.
bisimulation on speed: a unified approach. two process-algebraic approaches have been developed for comparing two bisimulation-equivalent processes with respect to speed: the one of moller/tofts equips actions with lower time bounds, while the other by lüttgen/vogler considers upper time bounds instead.this article sheds new light on both approaches by testifying to their close relationship. we introduce a general, intuitive concept of "faster-than", which is formalised by a notion of amortised faster-than preorder. when closing this preorder under all contexts, exactly the two faster-than preorders investigated by moller/tofts and lüttgen/vogler arise. for processes incorporating both lower and upper time bounds we also show that the largest precongruence contained in the amortised faster-than preorder is not a proper preorder but a timed bisimulation. in the light of this result we systematically investigate under which circumstances the amortised faster-than preorder degrades to an equivalence.
decomposition orders another generalisation of the fundamental theorem of arithmetic. we discuss unique decomposition in partial commutative monoids. inspired by a result from process theory, we propose the notion of decomposition order for partial commutative monoids, and prove that a partial commutative monoid has unique decomposition iff it can be endowed with a decomposition order. we apply our result to establish that the commutative monoid of weakly normed processes modulo bisimulation definable in acpε with linear communication, with parallel composition as binary operation, has unique decomposition. we also apply our result to establish that the partial commutative monoid associated with a well-founded commutative residual algebra has unique decomposition.
computing similarity between rna structures. the primary structure of a ribonucleic acid (rna) molecule is a sequence of nucleotides (bases) over the four-letter alphabet {a,c,g,u}. the secondary or tertiary structure of an rna is a set of base-pairs (nucleotide pairs) which forms bonds between au and cg. for secondary structures, these bonds have been traditionally assumed to be one to one and non-crossing. this paper considers a notion of similarity between two rna molecule structures taking into account the primary, the secondary and the tertiary structures. we show that, for tertiary structures, it is max snp-hard for both minimization and maximization versions. we show a stronger result for the maximization version where it cannot be approximated within ratio 2logn in polynomial time, unless npdtime[2polylogn]. we then present an algorithm that can be used for practical application. our algorithm will produce an optimal solution for the case where at least one of the rna involved is of a secondary structure. we also show an approximation algorithm.
on the relevance of time in neural computation and learning. we discuss models for computation in biological neural systems that are based on the current state of knowledge in neurophysiology. differences and similarities to traditional neural network models are highlighted. it turns out that many important questions regarding computation and learning in biological neural systems cannot be adequately addressed in traditional neural network models. in particular, the role of time is quite different in biologically more realistic models, and many fundamental questions regarding computation and learning have to be rethought for this context. simultaneously, a somewhat related new generation of vlsi-chips is emerging ("pulsedvlsi") where new ideas about computing and learning with temporal coding can be tested in an engineering context. articles with details to models and results that are sketched in this article can be found at http://www.tu-graz.ac.at/igi/maass/. we refer to maass and bishop(eds.,pulsed neural network, mit press, cambridge, ma, 1999) for a collection of survey articles that contain further details and references.
natural computation and non-turing models of computation. we propose certain non-turing models of computation, but our intent is not to advocate models that surpass the power of turing machines (tms), but to defend the need for models with orthogonal notions of power. we review the nature of models and argue that they are relative to a domain of application and are ill-suited to use outside that domain. hence we review the presuppositions and context of the tm model and show that it is unsuited to natural computation (computation occurring in or inspired by nature). therefore we must consider an expanded definition of computation that includes alternative (especially analog) models as well as the tm. finally we present an alternative model, of continuous computation, more suited to natural computation. we conclude with remarks on the expressivity of formal mathematics.
properties of probabilistic pushdown automata. properties of probabilistic as well as ``probabilistic plus nondeterministic'''' pushdown automata and auxiliary pushdown automata are studied. these models are analogous to their counterparts with nondeterministic and alternating states. complete characterizations in terms of well-known complexity classes are given for the classes of languages recognized by polynomial time-bounded, logarithmic space-bounded auxiliary pushdown automata with probabilistic states and with ``probabilistic plus nondeterministic'''' states. also, complexity lower bounds are given for the classes of languages recognized by these automata with unlimited running time. it follows that, by fixing an appropriate mode of computation, the difference between classes of languages such as p and pspace, nl and sac^1, pl and diff_<(#sac^1) is characterized as the difference between the number of stack symbols; that is, whether the stack alphabet contains one versus two distinct symbols.
branching time controllers for discrete event systems. we study the problem of synthesizing controllers for discrete event systems in a branching time framework. we use a class of labelled transition systems to model both plants and specifications. we use first simulations and later bisimulations to capture the role of a controller; the controlled behaviour of the plant should be related via a simulation (bisimulation) to the specification. for both simulations and bisimulations we show that the problem of checking if a pair of finite transition systems - one modelling the plant and the other the specification - admits a controller is decidable in polynomial time. we also show that the size of the controller, if one exists, can be bounded by a polynomial in the sizes of the plant and the specification and can be effectively constructed in polynomial time. finally, we prove that in the case of simulations, the problem of checking for the existence of a controller is undecidable in a natural concurrent setting.
when does a planar bipartite framework admit a continuous deformation? let k(x,y) denote the bipartite framework in the plane that realizes the complete bipartite graph km, n with partite sets x,y; |x| = m, |y| = n. we show that for m&ge;3, n&ge;5, k(x,y) admits a continuous deformation if and only if x lies on a line l and y lies on a line perpendicular to l.
on the computational strength of pure ambient calculi. cardelli and gordon's calculus of mobile ambients has attracted widespread interest as a model of mobile computation. the standard calculus is quite rich, with a variety of operators, together with capabilities for entering, leaving and dissolving ambients. the question arises of what is a minimal turing-complete set of constructs. previous work has established that turing completeness can be achieved without using communication or restriction. we show that it can be achieved merely using movement capabilities (and not dissolution). we also show that certain smaller sets of constructs are either terminating or have decidable termination.
pac learning of probability distributions over a discrete domain. we investigate learning of classes of distributions over a discrete domain in a pac context. we introduce two paradigms of pac learning, namely absolute pac learning, which is independent of the representation of the class of hypotheses, and pac learning wrt the indexes, which heavily depends on such representations. we characterize non-computable learnability in both contexts. then we investigate efficient learning strategies which are simulated by a polynomial-time turing machine. one strategy is the frequentist one. according to this strategy, the learner conjectures a hypothesis which is as close as possible to the distribution given by the frequency relative to the examples. we characterize the classes of distributions which are absolutely pac learnable by means of this strategy, and we relate frequentist learning wrt the indexes to the np = rp problem. finally, we present another strategy for learning wrt the indexes, namely learning by tests.
underspecification for a simple process algebra of recursive processes. this paper deals with underspecification for process algebras which is relevant in early design stages. we consider a form of underspecification that arises from a situation where at a certain design stage the decision between several options of system behaviour is to be postponed until more information is available. we follow an approach of veglioni and de nicola (lecture notes in computer science 1466 (1998) 179) who propose to interpret the choice operator of a simple class of finite process terms as underspecification whenever it combines two processes that have some initial action in common, as e.g. in (a.p + v.q) + (a.r + s.s). in particular, we consider recursive processes and discuss several extensions. copyright 2001 elsevier science b.v.
asymptotic behavior in a heap model with two pieces. in a heap model, solid blocks, or pieces, pile up according to the tetris game mechanism. an optimal schedule is an infinite sequence of pieces minimizing the asymptotic growth rate of the heap. in a heap model with two pieces, we prove that there always exists an optimal schedule which is balanced, either periodic or sturmian. we also consider the model where the successive pieces are chosen at random, independently and with some given probabilities. we study the expected growth rate of the heap. for a model with two pieces, the rate is either computed explicitly or given as an infinite series. we show an application for a system of two processes sharing a resource, and we prove that a greedy schedule is not always optimal.
results on multiples of primitive polynomials and their products over gf(2). linear feedback shift registers (lfsr) are important building blocks in stream cipher cryptosysterns. to be cryptographically secure, the connection polynomials of the lfsrs need to be primitive over gf(2). moreover, the polynomials should have high weight and they should not have sparse multiples at low or moderate degree. here we provide results on t-nomial multiples of primitive polynomials and their products. we present results for counting t-nomial multiples and also analyse the statistical distribution of their degrees. the results in this paper helps in deciding what kind of primitive polynomial should be chosen and which should be discarded in terms of cryptographic applications. further the results involve important theoretical identities in terms of t-nomial multiples which were not known earlier.
cryptographically significant boolean functions with five valued walsh spectra. we describe methods to construct balanced (resp. 1-resilient) functions of odd number of variables n achieving the bent concatenation nonlinearity and having algebraic degree n1 (resp. n-2). the technique is to algebraically modify the concatenation of two properly chosen (n-1)-variable maiorana-mcfarland bent functions. the constructed functions can be used with certain recursive operators to provide higher order resilient functions with maximum possible degree and high nonlinearity. such functions are well suited for stream cipher applications. interestingly, all the constructed functions have a five valued walsh spectr