共找到 20 条结果
Version incompatibility issues are prevalent when reusing or reproducing deep learning (DL) models and applications. Compared with official API documentation, which is often incomplete or out-of-date, Stack Overflow (SO) discussions possess a wealth of version knowledge that has not been explored by previous approaches. To bridge this gap, we present Decide, a web-based visualization of a knowledge graph that contains 2,376 version knowledge extracted from SO discussions. As an interactive tool, Decide allows users to easily check whether two libraries are compatible and explore compatibility knowledge of certain DL stack components with or without the version specified. A video demonstrating the usage of Decide is available at https://youtu.be/wqPxF2ZaZo0.
An outer automorphism of a free group is geometric if it can be represented by a homeomorphism of a compact surface. Bestvina and Handel gave an algorithmic characterization of geometric irreducible outer automorphisms using relative train tracks in 1995. The general case of detecting geometric outer automorphisms remained open, with a few partial results appearing subsequently. In this paper we give a complete resolution to the problem: an algorithm that can decide if a general outer automorphism is geometric. The algorithm is constructive and produces a realizing surface homeomorphism if one exists. We make use of advances in train-track theory, in conjunction with the Guirardel core of tree actions and Nielsen-Thurston theory for surfaces.
When engaging in strategic decision-making, we are frequently confronted with overwhelming information and data. The situation can be further complicated when certain pieces of evidence contradict each other or become paradoxical. The primary challenge is how to determine which information can be trusted when we adopt Artificial Intelligence (AI) systems for decision-making. This issue is known as deciding what to decide or Trustworthy AI. However, the AI system itself is often considered an opaque black box. We propose a new approach to address this issue by introducing a novel framework of Trustworthy AI (TAI) encompassing three crucial components of AI: representation space, loss function, and optimizer. Each component is loosely coupled with four TAI properties. Altogether, the framework consists of twelve TAI properties. We aim to use this framework to conduct the TAI experiments by quantitive and qualitative research methods to satisfy TAI properties for the decision-making context. The framework allows us to formulate an optimal prediction model trained by the given dataset for applying the strategic investment decision of credit default swaps (CDS) in the technology sector.
Population protocols are a model of distributed computation in which finite-state agents interact randomly in pairs. A protocol decides for any initial configuration whether it satisfies a fixed property, specified as a predicate on the set of configurations. A family of protocols deciding predicates $\varphi_n$ is succinct if it uses $\mathcal{O}(|\varphi_n|)$ states, where $\varphi_n$ is encoded as quantifier-free Presburger formula with coefficients in binary. (All predicates decidable by population protocols can be encoded in this manner.) While it is known that succinct protocols exist for all predicates, it is open whether protocols with $o(|\varphi_n|)$ states exist for \emph{any} family of predicates $\varphi_n$. We answer this affirmatively, by constructing protocols with $\mathcal{O}(\log|\varphi_n|)$ states for some family of threshold predicates $\varphi_n(x)\Leftrightarrow x\ge k_n$, with $k_1,k_2,...\in\mathbb{N}$. (In other words, protocols with $\mathcal{O}(n)$ states that decide $x\ge k$ for a $k\ge 2^{2^n}$.) This matches a known lower bound. Moreover, our construction for threshold predicates is the first that is not $1$-aware, and it is almost self-stabilising.
Tightness is a generalisation of the notion of convexity: a space is tight if and only if it is "as convex as possible", given its topological constraints. For a simplicial complex, deciding tightness has a straightforward exponential time algorithm, but efficient methods to decide tightness are only known in the trivial setting of triangulated surfaces. In this article, we present a new polynomial time procedure to decide tightness for triangulations of $3$-manifolds -- a problem which previously was thought to be hard. Furthermore, we describe an algorithm to decide general tightness in the case of $4$-dimensional combinatorial manifolds which is fixed parameter tractable in the treewidth of the $1$-skeletons of their vertex links, and we present an algorithm to decide $\mathbb{F}_2$-tightness for weak pseudomanifolds $M$ of arbitrary but fixed dimension which is fixed parameter tractable in the treewidth of the dual graph of $M$.
Nonequilibria show currents that are maintained as the result of a steady driving. We ask here what decides their direction. It is not only the second law, or the positivity of the entropy production that decides; also non-dissipative aspects often matter and sometimes completely decide.
Do unique node identifiers help in deciding whether a network $G$ has a prescribed property $P$? We study this question in the context of distributed local decision, where the objective is to decide whether $G \in P$ by having each node run a constant-time distributed decision algorithm. If $G \in P$, all the nodes should output yes; if $G otin P$, at least one node should output no. A recent work (Fraigniaud et al., OPODIS 2012) studied the role of identifiers in local decision and gave several conditions under which identifiers are not needed. In this article, we answer their original question. More than that, we do so under all combinations of the following two critical variations on the underlying model of distributed computing: ($B$): the size of the identifiers is bounded by a function of the size of the input network; as opposed to ($ eg B$): the identifiers are unbounded. ($C$): the nodes run a computable algorithm; as opposed to ($ eg C$): the nodes can compute any, possibly uncomputable function. While it is easy to see that under ($ eg B, eg C$) identifiers are not needed, we show that under all other combinations there are properties that can be decided locally if and
We prove that functionality of compositions of top-down tree transducers is decidable by reducing the problem to the functionality of one top-down tree transducer with look-ahead.
In this paper we present a unifying approach for deciding various bisimulations, simulation equivalences and preorders between two timed automata states. We propose a zone based method for deciding these relations in which we eliminate an explicit product construction of the region graphs or the zone graphs as in the classical methods. Our method is also generic and can be used to decide several timed relations. We also present a game characterization for these timed relations and show that the game hierarchy reflects the hierarchy of the timed relations. One can obtain an infinite game hierarchy and thus the game characterization further indicates the possibility of defining new timed relations which have not been studied yet. The game characterization also helps us to come up with a formula which encodes the separation between two states that are not timed bisimilar. Such distinguishing formulae can also be generated for many relations other than timed bisimilarity.
A set of stochastic matrices ${\cal P}$ is a consensus set if for every sequence of matrices $P(1), P(2), \ldots$ whose elements belong to ${\cal P}$ and every initial state $x(0)$, the sequence of states defined by $x(t) = P(t) P(t-1) \cdots P(1) x(0)$ converges to a vector whose entries are all identical. In this paper, we introduce an "avoiding set condition" for compact sets of matrices and prove in our main theorem that this explicit combinatorial condition is both necessary and sufficient for consensus. We show that several of the conditions for consensus proposed in the literature can be directly derived from the avoiding set condition. The avoiding set condition is easy to check with an elementary algorithm, and so our result also establishes that consensus is algorithmically decidable. Direct verification of the avoiding set condition may require more than a polynomial time number of operations. This is however likely to be the case for any consensus checking algorithm since we also prove in this paper that unless $P=NP$, consensus cannot be decided in polynomial time.
Implementing correct distributed systems is an error-prone task. Runtime Verification (RV) offers a lightweight formal method to improve reliability by monitoring system executions against correctness properties. However, applying RV in distributed settings - where no process has global knowledge - poses fundamental challenges, particularly under full asynchrony and fault tolerance. This paper addresses the Distributed Runtime Verification (DRV) problem under such conditions. In our model, each process in a distributed monitor receives a fragment of the input word describing system behavior and must decide whether this word belongs to the language representing the correctness property being verified. Hence, the goal is to decide languages in a distributed fault-tolerant manner. We propose several decidability definitions, study the relations among them, and prove possibility and impossibility results. One of our main results is a characterization of the correctness properties that can be decided asynchronously. Remarkably, it applies to any language decidability definition. Intuitively, the characterization is that only properties with no real-time order constraints can be decided
The decidability of a logical system refers to the existence of an algorithm that can determine whether any given formula in that system is a theorem. In this paper, Harrop's lemma is used to prove the decidability of quantum modal logic.
A drawing of a graph is {\em $x$-monotone} if every vertical line intersects each edge of the graph at most once. We present an $O(n^5)$ time algorithm for deciding whether a simple drawing of the complete graph $K_n$ is weakly isomorphic to an $x$-monotone drawing. We note that this algorithm can also decide whether a drawing of $K_n$ is strongly isomorphic to an $x$-monotone drawing.
In the setting of constructive mathematics, we suggest and study a framework for decidability of properties, which allows for finer distinctions than just "decidable, semidecidable, or undecidable". We work in homotopy type theory and use Brouwer ordinals to specify the level of decidability of a property. In this framework, we express the property that a proposition is $α$-decidable, for a Brouwer ordinal $α$, and show that it generalizes decidability and semidecidability. Further generalizing known results, we show that $α$-decidable propositions are closed under binary conjunction, and discuss for which $α$ they are closed under binary disjunction. We prove that if each $P(i)$ is semidecidable, then the countable meet $\forall i\in \mathbb N. P(i)$ is $ω^2$-decidable, and similar results for countable joins and iterated quantifiers. We also discuss the relationship with countable choice. All our results are formalized in Cubical Agda.
Many logical properties are known to be undecidable for normal modal logics, with few exceptions such as consistency and coincidence with $\mathsf{K}$. This paper shows that the property of being a union-splitting in $\mathsf{NExt}\mathsf{K}$, the lattice of normal modal logics, is decidable, thus answering the open problem [WZ07, Problem 2]. This is done by providing a semantic characterization of union-splittings in terms of finite modal algebras. Moreover, by clarifying the connection to union-splittings, we show that in $\mathsf{NExt}\mathsf{K}$, having a decidable axiomatization problem and being a (un)decidable formula are also decidable. The latter answers [CZ97, Problem 17.3] for $\mathsf{NExt}\mathsf{K}$.
Regular games form a well-established class of games for analysis and synthesis of reactive systems. They include coloured Muller games, McNaughton games, Muller games, Rabin games, and Streett games. These games are played on directed graphs $\mathcal G$ where Player 0 and Player 1 play by generating an infinite path $ρ$ through the graph. The winner is determined by specifications put on the set $X$ of vertices in $ρ$ that occur infinitely often. These games are determined, enabling the partitioning of $\mathcal G$ into two sets $W_0$ and $W_1$ of winning positions for Player 0 and Player 1, respectively. Numerous algorithms exist that decide specific instances of regular games, e.g., Muller games, by computing $W_0$ and $W_1$. In this paper we aim to find general principles for designing uniform algorithms that decide all regular games. For this we utilise various recursive and dynamic programming algorithms that leverage standard notions such as subgames and traps. Importantly, we show that our techniques improve or match the performances of existing algorithms for many instances of regular games.
There are many types of automata and grammar models that have been studied in the literature, and for these models, it is common to determine whether certain problems are decidable. One problem that has been difficult to answer throughout the history of automata and formal language theory is to decide whether a given system $M$ accepts a bounded language (whether there exist words $w_1, \ldots,w_k$ such that $L(M) \subseteq w_1 \cdots w_k$?). Decidability of this problem has gone unanswered for the majority of automata/grammar models in the literature. Boundedness was only known to be decidable for regular and context-free languages until recently when it was shown to also be decidable for finite-automata and pushdown automata augmented with reversal-bounded counters, and for vector addition systems with states. In this paper, we develop new techniques to show that the boundedness problem is decidable for larger classes of one-way nondeterministic automata and grammar models, by reducing the problem to the decidability of boundedness for simpler classes of automata. One technique involves characterizing the models in terms of multi-tape automata. We give new characterizations of fi
We show that for quasivarieties of p-algebras the properties of (i) having decidable first-order theory and (ii) having decidable first-order theory of the finite members, coincide. The only two quasivarieties with these properties are the trivial variety and the variety of Boolean algebras. This contrasts sharply, even for varieties, with the situation in Heyting algebras where decidable varieties do not coincide with finitely decidable ones.
By looking at decidable quotients, a sufficient condition is provided to guarantee that (1) the full subcategory of decidable objects of a topos is an exponential ideal and that (2) the classical notion of connectedness for an object $X$ coincides with $ΠX=1$, where $Π$ is the left-adjoint functor of the inclusion of the decidable objects. The addition of this condition to McLarty's axiomatic set up for Synthetic Differential Geometry makes any topos that satisfies it precohesive over the topos of its decidable objects. A converse is also provided.