Browsing by Subject "EQUIVALENCE"

Sort by: Order: Results:

Now showing items 1-3 of 3
  • Baumeister, Dorothea; Järvisalo, Matti; Neugebauer, Daniel; Niskanen, Andreas; Rothe, Jörg (2021)
    A Abstract argumentation frameworks (AFs), originally proposed by Dung, constitute a central formal model for the study of computational aspects of argumentation in AI. Credulous and skeptical acceptance of arguments in a given AF are well-studied problems both in terms of theoretical analysis-especially computational complexity-and the development of practical decision procedures for the problems. However, AFs make the assumption that all attacks between arguments are certain (i.e., present attacks are known to exist, and missing attacks are known to not exist), which can in various settings be a restrictive assumption. A generalization of AFs to incomplete AFs was recently proposed as a formalism that allows the representation of both uncertain attacks and uncertain arguments in AFs. In this article, we explore the impact of allowing for modeling such uncertainties in AFs on the computational complexity of natural generalizations of acceptance problems to incomplete AFs under various central AF semantics. Complementing the complexity-theoretic analysis, we also develop the first practical decision procedures for all of the NP-hard variants of acceptance in incomplete AFs. In terms of complexity analysis, we establish a full complexity landscape, showing that depending on the variant of acceptance and property/semantics, the complexity of acceptance in incomplete AFs ranges from polynomial-time decidable to completeness for Sigma(p)(3). In terms of algorithms, we show through an extensive empirical evaluation that an implementation of the proposed decision procedures, based on boolean satisfiability (SAT) solving, is effective in deciding variants of acceptance under uncertainties. We also establish conditions for what type of atomic changes are guaranteed to be redundant from the perspective of preserving extensions of completions of incomplete AFs, and show that the results allow for considerably improving the empirical efficiency of the proposed SAT-based counterexample-guided abstraction refinement algorithms for acceptance in incomplete AFs for problem variants with complexity beyond NP. (C) 2021 The Authors. Published by Elsevier B.V.
  • Lassas, Matti; Saksala, Teemu (2019)
    Let (N, g) be a Riemannian manifold with the distance function d(x, y) and an open subset M subset of N. For x is an element of M we denote by D-x the distance difference function D-x:F x F -> R, given by D-x(z(1), z(2)) = d(x, z(1)) - d(x, z(2)), z(1), z(2) is an element of F = N \ M. We consider the inverse problem of determining the topological and the differentiable structure of the manifold M and the metric g vertical bar M on it when we are given the distance difference data, that is, the set F, the metric g vertical bar F, and the collection D(M) = {D-x; x is an element of M}. Moreover, we consider the embedded image D(M) of the manifold M, in the vector space C(F x F), as a representation of manifold M. The inverse problem of determining (M, g) from D(M) arises e.g. in the study of the wave equation on R x N when we observe in F the waves produced by spontaneous point sources at unknown points (t, x) is an element of R x M. Then D-x (z(1), z(2)) is the difference of the times when one observes at points z(1) and z(2) the wave produced by a point source at x that goes off at an unknown time. The problem has applications in hybrid inverse problems and in geophysical imaging.
  • Exnerova, Vendula Honzlova; Maly, Jan; Martio, Olli (2018)
    Moduli of path families are widely used to study Sobolev functions. Similarly, the recently introduced approximation (AM-) modulus is helpful in the theory of functions of bounded variation (BV) in R-n (Martio, 2016). We continue this direction of research. Let Gamma(E) be the family of all paths which meet E subset of R-n. We introduce the outer measure E bar right arrow AM(Gamma(E)) and compare it with other (n - 1)-dimensional measures. In particular, we show that AM(Gamma(E)) = 2H(n-1)(Gamma(E)) whenever E lies on a countably (n - 1)-rectifiable set. Further, we study functions which have bounded variation on AM-a.e. path and we relate these functions to the classical BV functions which have only bounded essential variation on AM-a.e. path. We also characterize sets E of finite perimeter in terms of the AM-modulus of two path families naturally associated with E. (C) 2018 Elsevier Ltd. All rights reserved.