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.
the proceedings contain 35 papers. the special focus in this conference is on trends in Algorithmics and Information Technologies in practice. the topics include: A software engineering discipline in need of research;...
ISBN:
(纸本)3540413480
the proceedings contain 35 papers. the special focus in this conference is on trends in Algorithmics and Information Technologies in practice. the topics include: A software engineering discipline in need of research;exhaustive search, combinatorial optimization and enumeration;the incompressibility method;algorithms for rational agents;simplified witness tree arguments;physical design of CMOS chips in six easy steps;analysis patterns;information society technologies in healthcare;towards high speed grammar induction on large text corpora;information access based on associative calculation;exploiting ecological niche and morphology;hierarchies of sensing and control in visually guided agents;recognizing objects by their appearance using eigenimages;applications in image processing;an automatic composition algorithm for functional logic programs;on the approximation ratio of the group-merge algorithm for the shortest common superstring problem;fast evolutionary chains;a temporal layered knowledge architecture for an evolving structured environment;on-line maximum-order induced hereditary subgraph problems;quantum pushdown automata;use of dependency microcontexts in information retrieval;some notes on the information flow in read-once branching programs;on vision-based orientation method of a robot head in a dark cylindrical pipe;autonomous components;parallel object server for fine grained objects;massively parallel pattern recognition with link failures;finitary observations in regular algebras and using consensus methods for solving conflicts of data in distributed systems.
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.
We study properties characterized by applying successively a "destructive" rule expressed in first-order logic. the rule says that Points, a(1),...,a(k) of a structure can be removed if they satisfy a certai...
详细信息
ISBN:
(纸本)9783642112652
We study properties characterized by applying successively a "destructive" rule expressed in first-order logic. the rule says that Points, a(1),...,a(k) of a structure can be removed if they satisfy a certain first-order formula. phi(a(1),...,a(k)). the property defined this way by the formula is the set of finite structures such that we are able to obtain the empty structure when applying the rule repeatedly. Many classical properties can be formulated by means of a. "destructive" rule. We do a systematic study of the computational complexity of these properties according to the fragment of first-order logic in which the rule is expressed. We give the list of minimal fragments able to define NP-complete properties and maximal fragments that define only PTIME properties (unless PTIME = NP), depending on the number k of free variables and the quantifier symbols used in the formula. We also study more specifically the case where the formula has one free variable and is universal.
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.
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.
暂无评论