waashk/dblp huggingface dataset:
cell complexes, oriented matroids and digital geometry. abstract cell complexes (accs) were introduced by kovalevsky as a means of solving certain connectivity paradoxes in graph-theoretic digital topology, and to this extent provide an improved theoretical basis for image analysis. in this work we argue that accs are a very natural setting for digital geometry, to the extent that their use permits simple, almost trivial formulations of major convexity results, including caratheodory's, helly's and radon's theorems. we also discuss the relevance of oriented matroids to digital geometry.
slicing techniques for verification re-use. in this paper we discuss which properties of a formally verified component are preserved when the component is changed due to an adaption to a new use. more specifically, we will investigate when a temporal logic property of an object-z class is preserved under a modification or extension of the class with new features. to this end, we use the slicing technique from program analysis which provides us with a representation of the dependencies within the class in the form of a program dependence graph. this graph can be used to determine the effect of a change to the class's behaviour and thus to the validity of a temporal logic formula.
hypercomputation by definition. hypercomputation refers to computation surpassing the turing model, not just exceeding the von neumann architecture. algebraic constructions yield a finitely based pseudorecursive equational theory (internat. j. algebra comput. 6 (1996) 457-510). it is not recursive, although for each given number n, its equations in n variables form a recursive set. hypercomputation is therefore required for an algorithmic answer to the membership problem of such a theory. yet alfred tarski declared these theories to be decidable. the dilemma of a decidable but not recursive set presents an impasse to standard computability theory. one way to break the impasse is to predicate that the theory is computable--in other words, hypercomputation by definition.
learning to score final positions in the game of go. this article investigates the application of machine-learning techniques for the task of scoring final positions in the game of go. neural network classifiers are trained to classify life and death from labelled 9 × 9 game records. the performance is compared to standard classifiers from statistical pattern recognition. a recursive framework for classification is used to improve performance iteratively. using a maximum of four iterations our cascaded scoring architecture (csa*) scores 98.9% of the positions correctly. nearly all incorrectly scored positions are recognised (they can be corrected by a human operator). by providing reliable score information csa* opens the large source of go knowledge implicitly available in human game records for automatic extraction. it thus paves the way for a successful application of machine learning in go.
sublogarithmic ambiguity. context-free grammars and languages with infinite ambiguity can be distinguished by the growth rate of their ambiguity with respect to the length of the words. so far the least growth rate known for a divergent inherent ambiguity function was logarithmic. roughly speaking we show that it is possible to stay below any computable function. more precisely let f : n → n be an arbitrary computable divergent total non-decreasing function. then there is a context-free language l with a divergent inherent ambiguity function g below f, i.e., g(n) ≤ f(n) for each n ∈ n. this result is an immediate consequence of two other results which are of independent interest. the first result says that there is a linear context-free grammar g with so called unambiguous turn position whose ambiguity function is below f. the second one states that any ambiguity function of a cycle-free context-free grammar is an inherent ambiguity function of some context-free language.
characterizing the super-turing computing power and efficiency of classical fuzzy turing machines. the first attempts concerning formalization of the notion of fuzzy algorithms in terms of turing machines are dated in late 1960s when this notion was introduced by zadeh. recently, it has been observed that corresponding so-called classical fuzzy turing machines can solve undecidable problems. in this paper we will give exact recursion-theoretical characterization of the computational power of this kind of fuzzy turing machines. namely, we will show that fuzzy languages accepted by these machines with a computable t-norm correspond exactly to the union σ10 ∪ π10 of recursively enumerable languages and their complements. moreover, we will show that the class of polynomially time-bounded computations of such machines coincides with the union np ∪ co-np of complexity classes from the first level of the polynomial hierarchy.
normal forms and syntactic completeness proofs for functional independencies. we prove normal form theorems of a complete axiom system for the inference of functional dependencies and independencies in relational databases. we also show that all proofs in our system have a normal form where the application of independency rules is limited to three levels. our normal form results in a faster proof-search engine in deriving consequences of functional independencies. as a result, we get a new construction of an armstrong relation for a given set of functional dependencies. it is also shown that an armstrong relation for a set of functional dependencies and independencies do not exist in general, and this generalizes the same result valid under the closed-world assumption. copyright 2001 elsevier science b.v.
idempotent and co-idempotent stack filters and min-max operators. viewing the elements of rs as images f with pixels i ∈ s of grey-scale value f(i) motivates the study of certain nonlinear operators φ : rs → rs. for translation invariant φ (called stack filters in the signal processing literature) we derive the first necessary and sufficient condition for idempotency which can be tested in polynomial time. various related properties can be tested in polynomial time as well, and many results still apply when the linear lattice (r, ≤ ) is replaced by an arbitrary distributive lattice (r, ≤), or when the condition of translation invariance is dropped. although the main application is in nonlinear image processing several other fields will be touched upon.
a new algorithm for optimal 2-constraint satisfaction and its implications. we present a novel method for exactly solving (in fact, counting solutions to) general constraint satisfaction optimization with at most two variables per constraint (e.g. max-2-csp and min-2-csp), which gives the first exponential improvement over the trivial algorithm. more precisely, the runtime bound is a constant factor improvement in the base of the exponent: the algorithm can count the number of optima in max-2-sat and max-cut instances in o(m32ωn/3) time, where ω < 2.376 is the matrix product exponent over a ring. when the constraints have arbitrary weights, there is a (1 + ε)-approximation with roughly the same runtime, modulo polynomial factors. our construction shows that improvement in the runtime exponent of either k-clique solution (even when k = 3) or matrix multiplication over gf(2) would improve the runtime exponent for solving 2-csp optimization.our approach also yields connections between the complexity of some (polynomial time) high-dimensional search problems and some np-hard problems. for example, if there are sufficiently faster algorithms for computing the diameter of n points in l1, then there is an (2 - ε)n algorithm for max-lin. these results may be construed as either lower bounds on the high-dimensional problems, or hope that better algorithms exist for the corresponding hard problems.
an effective two-level proof-number search algorithm. the paper presents a new proof-number (pn) search algorithm, called pds-pn. it is a two-level search (like pn2), which performs at the first level a depth-first proof-number and disproof-number search (pds), and at the second level a best-first pn search. hence, pds-pn selectively exploits the power of both pn2 and pds. experiments in the domain of lines of action are performed. they show that within an acceptable time frame pds-pn is more effective for really hard endgame positions than αβ and any other pn-search algorithm.
a formal approach to object-oriented software engineering. we show how formal specifications can be integrated into one of the current pragmatic object-oriented software development methods. jacobson's "object-oriented software engineering" process is combined with object-oriented algebraic specifications by extending object and interaction diagrams with formal annotations. the specifications are based on meseguer's rewriting logic and are written in a meta-level extension of the language maude by process expressions. as a result any such diagram can be associated with a formal specification, proof obligations ensuring invariant properties can be automatically generated, and the refinement relations between documents at different abstraction levels can be formally stated and proved.
explicit fusions. we introduce explicit fusions of names. an explicit fusion is a process that exists concurrently with the rest of the system and enables two names to be used interchangeably. explicit fusions provide a small-step account of reaction in process calculi such as the pi calculus and the fusion calculus. in this respect they are similar to the explicit substitutions of abadi, cardelli and curien, which do the same for the lambda calculus. in this paper, we give a technical foundation for explicit fusions. we present the pi-f calculus, a simple process calculus with explicit fusions, and define a strong bisimulation congruence. we study the embeddings of the fusion calculus and the pi calculus. the former is fully abstract with respect to bisimulation.
a construction method for optimally universal hash families and its consequences for the existence of rbibds. we introduce a method for constructing optimally universal hash families and equivalently rbibds. as a consequence of our construction we obtain minimal optimally universal hash families, if the cardinalities of the universe and the range are powers of the same prime. a corollary of this result is that the necessary conditions for the existence of an rbibd with parameters v, k, λ, namely v ≡ 0 (mod k) and λ(v - 1) ≡ 0(mod k - 1), are sufficient, if v and k are powers of the same prime. as an application of our construction, we show that the k-maxcut algorithm of hofmeister and lefmann [a combinatorial design approach to maxcut, random struct. algorithms 9 (1996) 163-173] can be implemented such that it has a polynomial running time, in the case that the number of vertices and k are powers of the same prime.
seventeen lines and one-hundred-and-one points. we investigate a curious problem from additive number theory: given two positive integers s and q, does there exist a sequence of positive integers that add up to s and whose squares add up to q? we show that this problem can be solved in time polynomially bounded in the logarithms of s and q.as a consequence, also the following question can be answered in polynomial time: for given numbers n and m, do there exist n lines in the euclidean plane with exactly m points of intersection?
quantum communication and complexity. in the setting of communication complexity, two distributed parties want to compute a function depending on both their inputs, using as little communication as possible. the required communication can sometimes be significantly lowered if we allow the parties the use of quantum communication. we survey the main results of the young area of quantum communication complexity; its relation to teleportation and dense coding, the main examples of fast quantum communication protocols, lower bounds, and some applications.
counting the number of games. we give upper and lower bounds on g(n) equal to the number of games born by day n. in particular, we give an upper bound of g(n + 1) ≤ g(n) + 2g(n) + 2. for the lower bound, for all α < 1, for sufficiently large n, g(n + 1) ≥ 2g(n)z.
csp, partial automata, and coalgebras. the paper presents a first reconstruction of hoare's theory of csp in terms of partial automata and related coalgebras. we show that the concepts of processes in hoare (communicating sequential processes, prentice-hall, englewood cliffs, nj, 1985) are strongly related to the concepts of states for special, namely, final partial automata. moreover, we show how the deterministic and nondeterministic operations in hoare (1985) can be interpreted in a compatible way by constructions on the semantical level of automata. based on this, we are able to interpret finite process expressions as representing finite partial automata with designated initial states. in such a way we provide a new method for solving recursive process equations which is based on the concept of final automata. the coalgebraic reconstruction of csp allows us to use coinduction as a new proof principle. to make evident the usefulness of this principle we prove some example laws from hoare (1985).
optimal three-dimensional orthogonal graph drawing in the general position model. let g be a graph with maximum degree at most six. a three-dimensional orthogonal drawing of g positions the vertices at grid-points in the three-dimensional orthogonal grid, and routes edges along grid lines such that edge routes only intersect at common end-vertices. in this paper, we consider three-dimensional orthogonal drawings in the general position model; here no two vertices are in a common grid-plane. minimising the number of bends in an orthogonal drawing is an important aesthetic criterion, and is np-hard for general position drawings. we present an algorithm for producing general position drawings with an average of at most 2 2/7 bends per edge. this result is the best known upper bound on the number of bends in three-dimensional orthogonal drawings, and is optimal for general position drawings of k7. the same algorithm produces drawings with two bends per edge for graphs with maximum degree at most five; this is the only known non-trivial class of graphs admitting two-bend drawings.
an optical model of computation. we prove computability and complexity results for an original model of computation called the continuous space machine. our model is inspired by the theory of fourier optics. we prove our model can simulate analog recurrent neural networks, thus establishing a lower bound on its computational power. we also define a θ(log2n) unordered search algorithm with our model.
on the final sequence of a finitary set functor. a standard construction of the final coalgebra of an endofunctor involves defining a chain of iterates, starting at the final object of the underlying category and successively applying the functor. in this paper we show that, for a finitary set functor, this construction always yields a final coalgebra in ω2 = ω + ω steps.
some properties of ising automata. in this work, we shall present some arithmetical and topological properties of ising automata. more precisely, we shall study many different notions, such as faithful and strictly faithful automata, factor aud product automata, irreducible and weakly irreducible automata, prime automata, homogeneous automata, minimal automata, invertible automata, etc., and discuss their related properties. we shall also define and study three different topologies over the set of all minimal automata, and discuss the topological closure property of automatic sequences. as application, we shall use the obtained results to give a somewhat detailed analysis of ising automata.
minimum connected dominating sets and maximal independent sets in unit disk graphs. in ad hoc wireless networks, a connected dominating set can be used as a virtual backbone to improve the performance. many constructions for approximating the minimum connected dominating set are based on the construction of a maximal independent set. the relation between the size mis(g) of a maximum independent set and the size cds(g) of a minimum connected dominating set in the same graph g plays an important role in establishing the performance ratio of those approximation algorithms. previously, it is known that mis(g) ≤ 4ċcds(g) + 1 for all unit disk graphs g. in this paper, we improve it by showing mis(g) ≤ 3.8ċcds(g) + 1.2.
majority-based reversible logic gates. reversible logic plays an important role in the synthesis of circuits for quantum computing. in this paper, we introduce families of reversible gates based on the majority boolean function (mbf) and we prove their properties in reversible circuit synthesis. these gates can be used to synthesize reversible circuits of minimum "scratchpad register width" for arbitrary reversible functions. we show that, given a mbf f with 2k + 1 inputs, f can be implemented by a reversible logic gate with 2k + 1 inputs and 2k + 1 outputs, i.e., without any constant inputs. we also demonstrate new gates from this family with very efficient quantum realizations for majority-based applications. they can be used to synthesize any reversible function of the same width in conjunction with inverters and feynman (2-qubit controlled-not) gates. the gate universality problem is formulated in terms of elementary group theory and solved using the algebraic software gap.
the approximability of the weighted hamiltonian path completion problem on a tree. given a graph, the hamiltonian path completion problem is to find an augmenting edge set such that the augmented graph has a hamiltonian path. in this paper, we show that the hamiltonian path completion problem will unlikely have any constant ratio approximation algorithm unless np = p. this problem remains hard to approximate even when the given subgraph is a tree. moreover, if the edge weights are restricted to be either 1 or 2, the hamiltonian path completion problem on a tree is still np-hard. then it is observed that this problem is strongly np-hard, so it does not have any fully polynomial-time approximation scheme (fptas) unless np = p when the given tree is a k-tree, we give an approximation algorithm with performance ratio 1.5.
on the time-space tradeoff for sorting with linear queries. extending a result of borodin, et al., we show that any branching program using linear queries " $\sum_{i} {\lambda}_i {x_i}: c$ " to sort n numbers $x_1$,$x_2$,...,$x_n$ must satisfy the time-space tradeoff relation ts = $\omega (n_2)$. the same relation is also shown to be true for branching programs that use queries " min r = ? " where r is any subset of {$x_1$,$x_2$,...,$x_n$}.
completeness of type assignment systems with intersection, union, and type quantifiers. this paper develops type assignment systems with intersection and union types, and type quantifiers. we show that the known system for these types is not semantically complete. however, the following two hold for a certain class of typing statements, called stable statements, which include all statements without type quantifier: (1) the validity of stable statements for kripke models is equivalent to that for standard models, (2) if we add two axioms expressing the distributive laws of intersection over union and existential-type quantifier, then the resulting system is complete for kripke models. as a consequence, the known system with the axioms for distributive laws is complete for standard models if we restrict statements to stable ones. all the results are obtained in a systematic way with sequent-style formulations of type assignment and the cut-elimination property for them.
specification languages in algebraic compilers. algebraic compilers provide a powerful and convenient mechanism for specifying language translators. with each source language operation one associates a computation for constructing its target language image; these associated computations, called derived operations, are expressed in terms of operations from the target language. sometimes the target language is not powerful enough to specify the required translation and one may then need to extend the target language algebras with more computationally expressive operations or elements. a better solution is to package these extensions in a specification language which can be composed with the target language to ensure that all operations and elements needed or desired for performing the translation are provided. in the example in this paper, we show how imperative and functional specification languages can be composed with a target language to implement a temporal logic model checker as an algebraic compiler and show how specification languages can be seen as components to be combined with a source and target language to generate an algebraic compiler.
approximation schemes for knapsack problems with shelf divisions. given a knapsack of size k, non-negative values d and δ, and a set s of items, each item e ∈ s with size se and value ve, we define a shelf as a subset of items packed inside a bin with total items size at most δ. two subsequent shelves must be separated by a shelf divisor of size d. the size of a shelf is the total size of its items plus the size of the shelf divisor. the shelf-knapsack problem (sk) is to find a subset s' ⊆ s partitioned into shelves with total shelves size at most k and maximum value. the class constrained shelf knapsack (ccsk) is a generalization of the problem sk, where each item in s has a class and each shelf in the solution must have only items of the same class. we present approximation schemes for the sk and the ccsk problems. to our knowledge, these are the first approximation results where shelves of non-null size are used in knapsack problems.
power domination in block graphs. the problem of monitoring an electric power system by placing as few measurement devices in the system as possible is closely related to the well-known domination problem in graphs. in 2002, haynes et al. considered the graph theoretical representation of this problem as a variation of the domination problem. they defined a set s to be a power dominating set of a graph if every vertex and every edge in the system is monitored by the set s (following a set of rules for power system monitoring). the power domination number γp(g) of a graph g is the minimum cardinality of a power dominating set of g. this problem was proved np-complete even when restricted to bipartite graphs and chordal graphs. in this paper, we present a linear time algorithm for solving the power domination problem in block graphs. as an application of the algorithm, we establish a sharp upper bound for power domination number in block graphs and characterize the extremal graphs.
minimality and separation results on asynchronous mobile processes - representability theorems by concurrent combinators. in honda and yoshida (tacs'94, lecture notes in computer science, vol. 789, springer, berlin, 1994, pp. 786-805; popl'94, acm press, new york, 1994, pp. 348-360) we presented a theory of concurrent combinators for the asynchronous monadic calculus without match or summation operator. the system of concurrent combinators is based on a finite number of atoms and fixed interaction rules, but is as expressive as the original calculus, so that it can represent diverse interaction structures, including polyadic synchronous name passing and input guarded summations. the present paper shows that each of the five basic combinators introduced in honda and yoshida (popl'94, acm press, new york, 1994, pp. 348-360) is indispensable to represent the whole computation, i.e. if one of the combinators is missing, we can no longer express the original calculus up to semantic equalities. expressive power of several interesting subsystems of the asynchronous calculus is also measured by using appropriate subsets of the combinators and their variants. finally, as an application of the main result, we show there is no semantically sound encoding of the calculus into its proper subsystem under a certain condition.