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.
this paper studies two problems on compressed strings described in terms of straight line programs (SLPs). One is to compute the length of the longest common substring of two given SLP-compressed strings, and the othe...
详细信息
ISBN:
(数字)9783540775669
ISBN:
(纸本)9783540775652
this paper studies two problems on compressed strings described in terms of straight line programs (SLPs). One is to compute the length of the longest common substring of two given SLP-compressed strings, and the other is to compute all palindromes of a given SLP-compressed string. In order to solve these problems efficiently (in polynomial time w.r.t. the compressed size) decompression is never feasible, since the decompressed size can be exponentially large. We develop combinatorial algorithms that solve these problems in O(n(4) log n) time with O(n(3)) space, and in O(n(4)) time with O(n(2)) space, respectively, where n is the size of the input SLP-compressed strings.
this book constitutes the refereed proceedings of the 24th Seminar on currenttrends in theory and practice of Informatics, SOFSEM'97, held in Milovy, Czech Republic, in November 1997. SOFSEM is special in being a...
详细信息
ISBN:
(数字)9783540696452
ISBN:
(纸本)9783540637745
this book constitutes the refereed proceedings of the 24th Seminar on currenttrends in theory and practice of Informatics, SOFSEM'97, held in Milovy, Czech Republic, in November 1997. SOFSEM is special in being a mix of a winter school, an international conference, and an advanced workshop meeting the demand for ongoing education in the area of computerscience. the volume presents 22 invited contributions by leading experts together with 24 revised contributed papers selected from 63 submissions. the invited presentations are organized in topical sections on foundations, distributed and parallel computing, software engineering and methodology, and databases and information systems.
An arithmetic progression is a sequence of integers in which the difference between any two consecutive elements is the same. We investigate the parameterized complexity of two problems related to arithmetic progressi...
详细信息
ISBN:
(纸本)9783031521126;9783031521133
An arithmetic progression is a sequence of integers in which the difference between any two consecutive elements is the same. We investigate the parameterized complexity of two problems related to arithmetic progressions, called COVER BY ARIthMETIC PROGRESSIONS (CAP) and EXACT COVER BY ARIthMETIC PROGRESSIONS (XCAP). In both problems, we are given a set X consisting of n integers along with an integer k, and our goal is to find k arithmetic progressions whose union is X. In XCAP we additionally require the arithmetic progressions to be disjoint. Both problems were shown to be NP-complete by Heath [IPL'90]. We present a 2(O(k2)) poly(n) time algorithm for CAP and a 2(O(k3)) poly(n) time algorithm for XCAP. We also give a fixed parameter tractable algorithm for CAP parameterized below some guaranteed solution size. We complement these findings by proving that CAP is Strongly NP-complete in the field Z(p), if p is a prime number part of the input.
We study the rendezvous problem in the asynchronous setting in the graph of infinite line following the model introduced in [13]. We formulate general lemmas about deterministic rendezvous algorithms in this setting w...
详细信息
ISBN:
(纸本)9783540958901
We study the rendezvous problem in the asynchronous setting in the graph of infinite line following the model introduced in [13]. We formulate general lemmas about deterministic rendezvous algorithms in this setting which characterize the algorithms in which the agents have the shortest routes. We also improve rendezvous algorithms in the infinite line which formulated in [13]. Two agents have distinct labels L-min, L-max and vertical bar L-min vertical bar <= vertical bar L-max vertical bar. When the initial distance D between the agents is known, our algorithm has cost D vertical bar L-min vertical bar(2) which is ail improvement in the constant. If the initial distance is unknown we give an algorithm of cost O(D log(2) D + D log D vertical bar L-max vertical bar + D vertical bar L-min vertical bar(2) + vertical bar L-max vertical bar vertical bar L-min vertical bar log vertical bar L-min vertical bar) which is an asymptotic improvement.
the well-known Disjoint Paths problem takes as input a graph G and a set of k pairs of terminals in G, and the task is to decide whether there exists a collection of k pairwise vertex-disjoint paths in G such that the...
详细信息
ISBN:
(纸本)9783319042978;9783319042985
the well-known Disjoint Paths problem takes as input a graph G and a set of k pairs of terminals in G, and the task is to decide whether there exists a collection of k pairwise vertex-disjoint paths in G such that the vertices in each terminal pair are connected to each other by one of the paths. this problem is known to NP-complete, even when restricted to planar graphs or interval graphs. Moreover, although the problem is fixed-parameter tractable when parameterized by k due to a celebrated result by Robertson and Seymour, it is known not to admit a polynomial kernel unless NP subset of coNP/poly. We prove that Disjoint Paths remains NP-complete on split graphs, and show that the problem admits a kernel with O(k(2)) vertices when restricted to this graph class. We furthermore prove that, on split graphs, the edge-disjoint variant of the problem is also NP-complete and admits a kernel with O(k(3)) vertices. To the best of our knowledge, our kernelization results are the first non-trivial kernelization results for these problems on graph classes.
暂无评论