We introduce the generalized notion of automata synchronization, so called partial synchronization, which holds for automata with partial transition function. We give a lower bound for the length of minimal synchroniz...
详细信息
ISBN:
(数字)9783540775669
ISBN:
(纸本)9783540775652
We introduce the generalized notion of automata synchronization, so called partial synchronization, which holds for automata with partial transition function. We give a lower bound for the length of minimal synchronizing words for partial synchronizing automata. the difference, in comparison to the 'classical' synchronization, lies in the initial conditions: let A = (Q, A, delta) be an automaton representing the dynamics of a particular system. In case of partial synchronization we assume that initial conditions (initial state of the system) can be represented by some particular states, that is by some P C Q, not necessarily by all possible states from Q. At first glance the above assumption limits our room for manoeuvre for constructing possibly long minimal synchronizing words (because of the lower number of states at the beginning). Unexpectedly this assumption allows us to construct longer minimal synchronizing words than in a standard case. In our proof we use Sperner's theorem and some basic combinatorics.
We examine a parameterized complexity class for randomized computation where only the error bound and not the full runtime is allowed to depend more than polynomially on the parameter, based on a proposal by Kwisthout...
详细信息
ISBN:
(数字)9783030108014
ISBN:
(纸本)9783030108014;9783030108007
We examine a parameterized complexity class for randomized computation where only the error bound and not the full runtime is allowed to depend more than polynomially on the parameter, based on a proposal by Kwisthout in [15,16]. We prove that this class, for which we propose the shorthand name PPPT, has a robust definition and is in fact equal to the intersection of the classes paraBPP and PP. this result is accompanied by a Cook-style proof of completeness for the corresponding promise class (under a suitable notion of reduction) for parameterized approximation versions of the inference problem in Bayesian networks, which is known to be PP-complete. Withthese definitions and results in place, we proceed by showing how it follows from this that derandomization is equivalent to efficient deterministic approximation methods for the inference problem. Furthermore, we observe as a straightforward application of a result due to Drucker in [8] that these problems cannot have polynomial size randomized kernels unless the polynomial hierarchy collapses to the third level. We conclude by indicating potential avenues for further exploration and application of this framework.
We examine the parameterized complexity of t-DOMINATING SET, the problem of finding a set of at most k nodes that dominate at least t nodes of a graph G = (V, E). the classic NP-complete problem DOMINATING SET, which ...
详细信息
ISBN:
(纸本)9783540695066
We examine the parameterized complexity of t-DOMINATING SET, the problem of finding a set of at most k nodes that dominate at least t nodes of a graph G = (V, E). the classic NP-complete problem DOMINATING SET, which can be seen to be t-DOMINATING SET withthe restriction that t = n, has long been known to be W[2]-complete when parameterized in k. Whereas this implies W[2]-hardness for t-DOMINATING SET and the parameter k, we are able to prove fixed-parameter tractability for t-DOMINATING SET and the parameter t. More precisely, we obtain a quintic problem kernel and a randomized O((4 + epsilon)(t) poly(n)) algorithm. the algorithm is based on the divide-and-color method introduced to the community earlier this year, rather intuitive and can be derandomized using a standard framework.
Trust and reputation systems are decision support tools used to drive parties' interactions on the basis of parties' reputation. In such systems, parties rate with each other after each interaction. Reputation...
详细信息
ISBN:
(纸本)9783642358432
Trust and reputation systems are decision support tools used to drive parties' interactions on the basis of parties' reputation. In such systems, parties rate with each other after each interaction. Reputation scores for each ratee are computed via reputation functions on the basis of collected ratings. We propose a general framework based on Bayesian decision theory for the assessment of such systems, with respect to the number of available ratings. Given a reputation function g and n independent ratings, one is interested in the value of the loss a user may incur by relying on the ratee's reputation as computed by the system. To this purpose, we study the behaviour of both Bayes and frequentist risk of reputation functions with respect to the number of available observations. We provide results that characterise the asymptotic behaviour of these two risks, describing their limits values and the exact exponential rate of convergence. One result of this analysis is that decision functions based on Maximum-Likelihood are asymptotically optimal. We also illustrate these results through a set of numerical simulations.
From the 1990s on, one of the most important challenges facing computerscience researchers has been the design and construction of software tools to exploit Internet computing. At the same time, the development of ag...
详细信息
In this paper the notion of quantum finite one-counter automata (QF1CA) is introduced. Introduction of the notion is similar to that of the 2-way quantum finite state automata in [1]. the well-formedness conditions fo...
详细信息
ISBN:
(纸本)354066694X
In this paper the notion of quantum finite one-counter automata (QF1CA) is introduced. Introduction of the notion is similar to that of the 2-way quantum finite state automata in [1]. the well-formedness conditions for the automata are specified ensuring unitarity of evolution. A special kind of QF1CA, called simple, that satisfies the well-formedness conditions is introduced. that allows specify rules for constructing such automata more naturally and simpler than in general case. Possible models of language recognition by QF1CA are considered. the recognition of some languages by QF1CA is shown and compared with recognition by probabilistic counterparts.
Traditional verbatim browsers give back information linearly according to a ranking performed by a search engine that may not be optimal for the surfer. the latter may need to assess the pertinence of the information ...
详细信息
ISBN:
(纸本)9783030389192;9783030389185
Traditional verbatim browsers give back information linearly according to a ranking performed by a search engine that may not be optimal for the surfer. the latter may need to assess the pertinence of the information retrieved, particularly when s center dot he wants to explore other facets of a multi-facetted information space. Simultaneous facet visualisation can help to gain insights into the information retrieved and call for further refined searches. Facets are potentially heterogeneous co-occurrence networks, built choosing at least one reference type, and modeled by HyperBag-Graphs-families of multisets on a given universe. References allow to navigate inside the dataset and perform visual queries. the approach is illustrated on Arxiv scientific pre-prints searches.
Justification theory is a unifying semantic framework. While it has its roots in non-monotonic logics, it can be applied to various areas in computerscience, especially in explainable reasoning;its most central conce...
详细信息
Justification theory is a unifying semantic framework. While it has its roots in non-monotonic logics, it can be applied to various areas in computerscience, especially in explainable reasoning;its most central concept is a justification: an explanation why a property holds (or does not hold) in a model. In this paper, we continue the study of justification theory by means of three major contributions. the first is studying the relation between justification theory and game theory. We show that justification frameworks can be seen as a special type of games. the established connection provides the theoretical foundations for our next two contributions. the second contribution is studying under which condition two different dialects of justification theory (graphs as explanations vs trees as explanations) coincide. the third contribution is establishing a precise criterion of when a semantics induced by justification theory yields consistent results. In the past proving that such semantics were consistent took cumbersome and elaborate proofs. We show that these criteria are indeed satisfied for all common semantics of logic programming.
Mirror neurons are specialized neurons recently discovered in the brains of primates. In experiments mirror neurons showed activity both when a subject performed an action and when it observed the same action performe...
详细信息
ISBN:
(纸本)3540207791
Mirror neurons are specialized neurons recently discovered in the brains of primates. In experiments mirror neurons showed activity both when a subject performed an action and when it observed the same action performed by self or another (possibly conspecific) subject. We formulate and study possible computational consequences of the hypothesis in which the experimentally observed properties of mirror neurons are generalized to other perceptive modalities and the underlying mechanism for coupling sensory and motor information is extended by an associative mechanism serving for completion of cross-modal information composed of perception and motor information. Depending on of what kind of information is completed, the hypothesis opens the door for understanding the mechanisms for sensorimotor coordination, imitation learning, and thinking and is inspiring for the design of such mechanisms in the case of artificial agents. Our results justify the hopes generally related to the discovery of mirror neurons.
Most of the concerns of Distributed Computing may appear in settings which are quite different from its traditonal applications ares such as distributed systems, data and communication networks, etc. An important sett...
ISBN:
(纸本)9783540429128
Most of the concerns of Distributed Computing may appear in settings which are quite different from its traditonal applications ares such as distributed systems, data and communication networks, etc. An important setting of this type is the one of autonomous mobile robots.
暂无评论