waashk/dblp huggingface dataset:
many hard examples in exact phase transitions. this paper analyzes the resolution complexity of two random constraint satisfaction problem (csp) models (i.e. model rb/rd) for which we can establish the existence of phase transitions and identify the threshold points exactly. by encoding csps into cnf formulas, it is proved that almost all instances of model rb/rd have no tree-like resolution proofs of less than exponential size. thus, we not only introduce new families of csps and cnf formulas hard to solve, which can be useful in the experimental evaluation of csp and sat algorithms, but also propose models with both many hard instances and exact phase transitions. finally, conclusions are presented, as well as a detailed comparison of model rb/rd with the hamiltonian cycle problem and random 3-sat, which, respectively, exhibit three different kinds of phase transition behavior in np-complete problems.
exact matching of rna secondary structure patterns. many rna structures are assembled from a collection of rna motifs, which appear repeatedly and in various combinations. identification of rna structural motifs will enhance our understanding of rna structures and functions. searching for secondary structural patterns in sequence databases is the basic technique and fundamental problem for extracting and identifying such motifs. a number of algorithms and programs have been developed for this purpose.in this paper, we adopt a representation of secondary structure called secondary expressions, and present two algorithms for finding all exact matches of a given secondary expression.
interpolation functor and computability. computability of banach spaces is discussed. a compatible relation is shown to hold between the complex interpolation spaces of calderón (studia math. 24 (1964) 113) and the computability structures introduced by pour-el and richards (computability in analysis and physics, springer, berlin, 1989). namely, it is verified that calderón's original construction of the complex interpolation functor is valid in the context of computability if a mild effective separability condition is fulfilled by a compatible couple of banach spaces.
weighted connected k-domination and weighted k-dominating clique in distance-hereditary graphs. a graph is distance-hereditary if the distance between any two vertices in a connected induced subgraph is the same as in the original graph. this paper presents efficient algorithms for solving the weighted connected k-domination and the weighted k-dominating clique problems in distance-hereditary graphs.
graph colourings and partitions. in this paper we have investigated mainly the three colouring parameters of a graph g, viz., the chromatic number, the achromatic number and the pseudoachromatic number. the importance of their study in connection with the computational complexity, partitions, algebra, projective plane geometry and analysis were briefly surveyed. some new results were found along these directions. we have rede0ned the concept of perfect graphs in terms of these parameters and obtained a few results. some open problems are raised.
similarity between preferential models. the notion of bisimulation is an important concept in process algebra and modern modal logic. this paper explores the notion of b-similarity, which is a kind of bisimulation between preferential models. we characterize the equivalence of preferential models in terms of b-similarity. however, this result is applicable only for preferential models of finite depth. to overcome this defect, we introduce a weak notion of similarity called m-similarity, and obtain a result corresponding to hennessy-milner theorem and keisler-shelah's isomorphism theorem in modal logic and first-order logic, respectively. as its application, we investigate the expressive power of boolean combinations of conditional assertions (bca, for short), and prove that bcas are the fragments of first-order language preserved under m-similarity. moreover, we obtain a characterization for elementary classes defined by bcas. a notion of first-order translation originating from modal logic plays an important role in this paper. in order to illustrate that first-order translation is a powerful tool in the study of nonmonotonic logic, some model-theoretic results about preferential models are proved based on this translation.
resource-sharing system scheduling and circular chromatic number. a graph g is used as a model for a resource sharing system, where each vertex represents a process and an edge joining two vertices means that the corresponding processes share a resource. a scheduling of g is a mapping f : {1, 2, 3, ... } → 2v(g), where f(i) consists of processes that are operating at round i. the rate of f is defined as rate(f) = lim supn → ∞ σi=1n|f(i)|/n|v(g)|, which is the average fraction of operating processes at each round. a scheduling is fair if adjacent vertices alternate their turns in operating. the operating rate γ*(g) of g is the maximum rate of a fair scheduling. fair schedulings of a graph was first studied by barbosa and gafni. they introduced the method of "scheduling by edge reversal" which derives a fair scheduling through an acyclic orientation. through scheduling by edge reversal, barbosa and gafni related γ* (g) to the structure of acyclic orientations of g. we point out that this relation implies that γ* (g) is equal to the reciprocal of the circular chromatic number of g. both circular coloring and scheduling by edge reversal have been studied extensively in the past decade. the former by graph theorists, and the latter by computer scientists. however, it seems that neither side knew the existence of the other. this paper intends to build a connection between the two sides. we show that certain open problems concerning scheduling by edge reversal are indeed solved under the language of circular coloring. in the study of fair scheduling, barbosa and gafni defined a variation of multiple coloring of graphs: the interleaved p-color, q-tuple colorings. we formulate the interleaved coloring as a graph homomorphism problem. in the study of circular chromatic number, bondy and hell defined (p, q)-colorings and also formulated it as a graph homomorphism problem. we prove that the target graph for the interleaved p-color, q-tuple coloring and the target graph of (p, q)-coloring are homomorphically equivalent. this gives another proof of the fact that γ* (g) = 1/χc (g). moreover, the proof gives an explicit formula which deduces an optimal circular coloring of g from an optimal interleaved coloring of g, and vice versa. this paper also introduces two other schedulings of a graph, the weakly fair scheduling and the strongly fair scheduling. it is proved that the rate of an optimal strongly fair scheduling of a graph g is also equal to the reciprocal of the circular chromatic number of g, and the rate of an optimal weakly fair scheduling of g is equal to the reciprocal of the fractional chromatic number of g. barbosa and gafni presented an algorithm that determines the rate γo(w) of the scheduling induced by an acyclic orientation ω of g. by using karp's minimum mean cycle algorithm, we give a faster algorithm to calculate γo(w).
resource bounded immunity and simplicity. revisiting the 30-years-old notions of resource-bounded immunity and simplicity, we investigate the structural characteristics of various immunity notions: strong immunity, almost immunity, and hyperimmunity as well as their corresponding simplicity notions. we also study limited immunity and simplicity, called k-immunity and feasible k-immunity, and their simplicity notions. finally, we propose the k-immune hypothesis as a working hypothesis that guarantees the existence of simple sets in np.
hypothesis finding based on upward refinement of residue hypotheses. for given logical formulae b and e such that b n e, hypothesis finding means the generation of a formula h such that b ∧ h ⊧ e. hypothesis finding constitutes a basic technique for fields of inference, like inductive inference and knowledge discovery. in order to put various hypothesis finding methods proposed previously on one general ground, we use upward refinement and residue hypotheses. we show that their combination is a complete method for solving any hypothesis finding problem in clausal logic. we extend the relative subsumption relation, and show that some hypothesis finding methods previously presented can be regarded as finding hypotheses which subsume examples relative to a given background theory. noting that the weakening rule may make hypothesis finding difficult to solve, we propose restricting this rule either to the inverse of resolution or to that of subsumption. we also note that this work is related to relevant logic.
on the intercluster distance of a tree metric. for two vertex clusters of a tree metric, we show that the sum of the average intracluster distances is always less than or equal to twice of the average intercluster distance. we show the feature in a more general form of weighted distance. this feature provides a 2-approximation algorithm for the minimum average intercluster distance spanning tree problem, which is a generalization of the minimum routing cost spanning tree or minimum average distance spanning tree problem. the results in this paper can be further generalized to more than two clusters.
on-line scheduling mesh jobs with dependencies. we study an on-line problem of scheduling parallel jobs on two-dimensional meshes. parallel jobs arrive dynamically according to the dependencies between them, which are unknown before the jobs appear. each job may need more than one processor simultaneously and is required to be scheduled on a submesh of the processors which are located on a two-dimensional mesh, i.e., a job must be scheduled on a rectangle of given dimensions. the objective is to minimize the maximum completion time (makespan). we deal with a uet job system, in which all job processing times are equal. we show a lower bound of 3.859 and present a 5.25-competitive algorithm. it significantly improves a previous lower bound of 3.25 and a previous upper bound of 46/7. we consider also the rotated two-dimensional mesh, in which the parallel jobs can be rotated and the rotation of all the jobs is feasible. a lower bound of 3.535 is proven and an on-line algorithm with competitive ratio of at most 4.25 is derived.
global exponential convergence of recurrent neural networks with variable delays. convergence analysis of recurrent neural networks is an important research direction in the field of neural networks. novel methods to study the global exponential convergence of recurrent neural networks with variable delays are proposed. a condition for global exponential stability, which is independent of the delays, is derived by the method of delayed inequalities analysis. another condition for global exponential stability, which depends on the delays, is obtained via the method of constructing a suitable and interesting lyapunov functional.
classifying regular languages by a split game. in this paper, we introduce the split game, a variant of the ehrenfeucht-fraisse game from logic, which is useful for analyzing the expressive power of classes of generalized regular expressions. an extension of the split game to generalized @w-regular expressions is also established. to gain insight into how the split game can be applied to attack the long-standing generalized star height 2 problem, we propose and solve the omega power problem, a similar but tractable problem in the context of @w-languages. namely we show that omega powers, together with boolean combinations and concatenations, are not sufficient to express the class of @w-regular languages.
authenticated key agreement in dynamic peer groups. many group-oriented applications in distributed systems, such as teleconferencing and cooperative works, involve dynamic peer groups. in order to secure communications in dynamic peer groups, authenticated key agreement protocols are required. in this paper, we propose a new authenticated key agreement protocol, composed of a basic protocol and a dynamic protocol, for dynamic peer groups. with the basic protocol, a secret group key can be achieved in a peer group via group handshake, secret broadcast, key derivation and key confirmation phases. by the dynamic protocol, a new secret group key can be reached when member or mass join, group mergence, group division, member or mass quit occurs in a dynamic peer group. security analysis shows that our protocol offers explicit group key authentication and prevents from both passive and active attacks. in our basic protocol, each group member equally contributes to the secret group key in parallel and guarantees key freshness.
k-partitioning problems with partition matroid constraint. in this paper, we consider the k-partitioning problems with partition matroid constraint and present an algorithm called the layered lpt algorithm. with the objective of minimizing the maximum load, we show that the layered lpt algorithm has a tight worst case ratio of 2-1/m. with the objective of maximizing the minimum load, we show that the layered lpt algorithm has a tight worst case ratio of 1/m for the general case and, with certain conditions, the worst ratio can be improved to m/(2m-1) for the general k case and to (m-1)/(2m-3) for the k=3 case.
a cost-effective estimation of uncaught exceptions in standard ml programs. we present a static analysis that detects potential runtime exceptions that are raised and never handled inside standard ml (sml) programs. this analysis will predict abrupt termination of sml programs, which is smls only one "safety hole". even though sml program's control flow and exception flow are in general mutually dependent, analyzing the two flows are safely decoupled. program's control flow is firstly estimated by simple case analysis of call expressions. using this call-graph information, program's exception flow is derived as set constraints, whose least model is our analysis result. both of these two analyses are proven safe and the reasons behind each design decision are discussed. our implementation of this analysis has been applied to realistic sml programs and shows a promising cost-accuracy performance. for the ml-lex program, for example, the analysis takes 1.36 s and it reports 3 may-uncaught exceptions, which are exactly the exceptions that can really escape. our final goal is to make the analysis overhead less than 10% of the compilation time (compiling the ml-lex takes 6-7 s) and to analyze modules in isolation. copyright 2002 elsevier science b.v.
msol partitioning problems on graphs of bounded treewidth and clique-width. we show that a class of vertex partitioning problems that can be expressed in monadic second order logic (msol) are polynomials on graphs of bounded clique-width. this class includes coloring, h-free coloring, domatic number and partition into perfect graphs. moreover we show that a class of vertex and edge partitioning problems are polynomials on graphs of bounded treewidth.
exchange market equilibria with leontief's utility: freedom of pricing leads to rationality. this paper studies the equilibrium property and algorithmic complexity of the exchange market equilibrium problem with concave piecewise linear functions, which include linear and leontief's utility functions as special cases. we show that the fisher model again reduces to the weighted analytic center problem, and the same linear programming complexity bound applies to computing its equilibrium. however, the story for the arrow-debreu model with leontief's utility becomes quite different. we show that, for the first time, solving this class of leontief exchange economies is equivalent to solving a linear complementarity problem whose algorithmic complexity is finite but not polynomially bounded.
a sound and complete procedure for a general logic program in non-floundering derivations with respect to the 3-valued stable model semantics. this paper presents a sound and complete procedure with respect to the 3-valued stable model semantics. the procedure is regarded as an extension of eshghi and kowalski abductive proof procedure, involving finite or countably infinite sld resolution, as well as finite or countably infinite negative recursion caused by negation as failure. the procedure makes use of the set of negative literals (the set of abducibles) for the negation as failure to be implemented. the set of abducibles is not only applicable to the extraction of explanations for abduction as in kakas et al. (j. logic comput. 2 (1992) 719-770) but also specified for what stable model is now computed in the procedure, because a 3-valued stable model is not always the least (that is, the well-founded model). the procedure also contains nondeterminism in the choices of what ground negative literals are used for negation as failure. by the assumptions of some adequate choices, the procedure is well-defined inductively. copyright 2001 elsevier science b.v.
bisimulation indexes and their applications. bisimulation expresses the equivalence of processes whose external actions are identical. sometimes we may meet two processes which are not exactly bisimilar but more or less bisimilar in the sense that whenever a process makes an action the other can make an action different from but very similar to the action performed by the first one. to describe this kind of looser bisimulations we propose the concept of bisimulation index in a labelled transition system and give its various properties, especially those properties related to the operations of transition systems. furthermore, we establish a modal logical characterization of bisimulation indexes. this characterization is a generalization of hennessy-milner logic. we study strong and weak bisimulation indexes in the basic asynchronous process calculus, and some of their fundamental properties are derived. bisimulation indexes are not substitutive under composition. to overcome this defect we introduce an approximate communication rule to replace the original rule in process calculus. this enables us to recover some useful properties of composition with respect to bisimulation indexes. finally, we present three examples in timed ccs and real time acp to demonstrate the usage of bisimulation indexes in the analysis of real time systems. these examples show that bisimulation indexes are suitable formal tools for describing approximate implementations of real time systems.
additive models of probabilistic processes. we propose a new model of probabilistic processes. in this model, a probability is assigned to the action of a prefix and a probability distribution is assigned to the components of a parallel composition. in addition, the probability of a transition of a probabilistic summation is evaluated as the sum of the probabilities of the same transition of summands multiplied by the probabilities associated to them in the summation. the concepts of strong bisimulation degree and (weak) bisimulation degree are introduced. these notions provide us with continuous spectra of strong bisimilarities, (weak) bisimilarities and observation congruences which equate probabilistic processes with different degrees of belief. various equational laws of probabilistic processes with respect to these equivalence relations are presented and substitutivities of these equivalence relations under various combinators are established.
quantum versus deterministic counter automata. this paper focuses on quantum analogues of various models of counter automata, and almost completely proves the relation between the classes of languages recognizable by bounded error quantum ones and classical deterministic ones in every model of counter automata. it is proved that (i) there are languages that can be recognized by two-way quantum one-counter automata with bounded error, but cannot be recognized by two-way deterministic one-counter automata, (ii) under some reasonable restriction, every language that can be recognized by two-way deterministic one-counter automata can also be recognized by two-way reversible one-counter automata (and hence by bounded error two-way quantum one-counter automata), and (iii) for any fixed k, quantum ones and deterministic ones are incomparable in one-way k-counter automata.
a theory of computation based on quantum logic (i). the (meta)logic underlying classical theory of computation is boolean (two-valued) logic. quantum logic was proposed by birkhoff and von neumann as a logic of quantum mechanics more than 60 years ago. it is currently understood as a logic whose truth values are taken from an orthomodular lattice. the major difference between boolean logic and quantum logic is that the latter does not enjoy distributivity in general. the rapid development of quantum computation in recent years stimulates us to establish a theory of computation based on quantum logic. the present paper is the first step toward such a new theory and it focuses on the simplest models of computation, namely finite automata. we introduce the notion of orthomodular lattice-valued (quantum) automaton. various properties of automata are carefully reexamined in the framework of quantum logic by employing an approach of semantic analysis. we define the class of regular languages accepted by orthomodular lattice-valued automata. the acceptance abilities of orthomodular lattice-valued nondeterministic automata and their various modifications (such as deterministic automata and automata with ε-moves) are compared. the closure properties of orthomodular lattice-valued regular languages are derived. the kleene theorem about equivalence of regular expressions and finite automata is generalized into quantum logic. we also present a pumping lemma for orthomodular lattice-valued regular languages. it is found that the universal validity of many properties (for example, the kleene theorem, the equivalence of deterministic and nondeterministic automata) of automata depend heavily upon the distributivity of the underlying logic. this indicates that these properties does not universally hold in the realm of quantum logic. on the other hand, we show that a local validity of them can be recovered by imposing a certain commutativity to the (atomic) statements about the automata under consideration. this reveals an essential difference between the classical theory of computation and the computation theory based on quantum logic.
one-way probabilistic reversible and quantum one-counter automata. kravtsev introduced 1-way quantum 1-counter automata (1q1cas), and showed that several non-context-free languages can be recognized by bounded error 1q1cas. in this paper, we first show that all of these non-context-free languages can be also recognized by bounded error 1pr1cas (and so 1q1cas). moreover, the accepting probability of each of these 1pr1cas is strictly greater than, or at least equal to, that of corresponding kravtsev's original 1q1ca. second, we show that there exists a bounded error 1pr1ca (and so 1q1ca) which recognizes {a1na2n...akn}, for each k ≥ 2. we also show that, in a quantum case, we can improve the accepting probability in a strict sense by using quantum interference. third, we state the relation between 1-way deterministic 1-counter automata (1d1cas) and 1q1cas. on one hand, all of above mentioned languages cannot be recognized by 1d1cas because they are non-context-free. on the other hand, we show that a regular language {{a, b}*a} cannot be recognized by bounded error 1q1cas.
recursive equations in higher-order process calculi. regarding behaviour equivalence in higher-order process calculi, sangiorgi (inform. and comput. 131 (1996) 141) and thomsen (inform. and comput. 116 (1995) 38) introduced context and higher-order bisimulations, respectively. in this paper, uniqueness of solutions of equations with respect to strong context and higher-order bisimilarities and compatibility of strong context and higher-order bisimilarities with recursive definitions are shown. copyright 2001 elsevier science b.v.