共查询到20条相似文献,搜索用时 31 毫秒
1.
Yasuo Uchida Takao Ito Makoto Sakamoto Takashi Ide Kazuyuki Uchida Ryuju Katamune Hiroshi Furutani Michio Kono Satoshi Ikeda Tsunehiro Yoshinaga 《Artificial Life and Robotics》2012,16(4):529-532
In 1967, M. Blum and C. Hewitt first proposed two-dimensional automata as a computational model of two-dimensional pattern
processing. Since then, many researchers in this field have been investigating the many properties of two- or three-dimensional
automata. In 1977, C.R. Dyer and A. Rosenfeld introduced an acceptor on a two-dimensional pattern (or tape) called the pyramid cellular acceptor, and demonstrated that many useful recognition tasks are executed by pyramid cellular acceptors in a time which is proportional
to the logarithm of the diameter of the input. They also introduced a bottom-up pyramid cellular acceptor, which is a restricted version of the pyramid cellular acceptor, and proposed some interesting open problems about bottom-up
pyramid cellular acceptors. On the other hand, we think that the study of four-dimensional automata has been meaningful as
the computational model of four-dimensional information processing such as computer animation, moving picture processing,
and so forth. In this article, we investigate bottom-up pyramid cellular acceptors with four-dimensional layers, and show
some of their accepting powers. 相似文献
2.
The combination of the notions of a cellular automaton and a probabilistic automaton, called a probabilistic cellular automaton, was proposed in 1973 by the first author of this paper as a more adequate model of any system with unreliable components that operate in a parallel manner. In this paper a language-acceptor type of such a probabilistic cellular automaton, called aprobabilistic bounded cellular acceptor (PBCA), is defined and studied. It is shown that the class of all languages accepted by one-dimensional PBCAs includes both the class of all languages accepted by bounded cellular acceptors (BCAs) and the class of all languages accepted by probabilistic acceptors (PAs). Also, it is shown that every language accepted by ad-dimensional PBCA at a given cut point is accepted by ad-dimensional PBCA at an arbitrary nonzero cut point. The class of all languages accepted by one-dimensional PBCAs at cut point 0 is shown to be precisely the class of all context-sensitive languages. Several decision problems for PBCAs are shown to be recursively unsolvable. Finally, various open problems concerning PBCAs and PBCLs are discussed. 相似文献
3.
It is proved that the emptiness problem for deterministic bottom-up triangle acceptors (BTA's) over a single input symbol is recursively unsolvable. From this result, it is also shown that certain decision problems involving BTA's and BPA's (deterministic bottom-up pyramid acceptors) are unsolvable. 相似文献
4.
Edward A. Hirsch Dmitry Itsykson Ivan Monakhov Alexander Smal 《Theory of Computing Systems》2012,51(2):179-195
The existence of an optimal propositional proof system is a major open question in proof complexity; many people conjecture that such systems do not exist. Krají?ek and Pudlák (J.?Symbol. Logic 54(3):1063, 1989) show that this question is equivalent to the existence of an algorithm that is optimal on all propositional tautologies. Monroe (Theor. Comput. Sci. 412(4?C5):478, 2011) recently presented a conjecture implying that such an algorithm does not exist. We show that if one allows errors, then such optimal algorithms do exist. The concept is motivated by the notion of heuristic algorithms. Namely, we allow an algorithm, called a heuristic acceptor, to claim a small number of false ??theorems?? and err with bounded probability on other inputs. The amount of false ??theorems?? is measured according to a polynomial-time samplable distribution on non-tautologies. Our result remains valid for all recursively enumerable languages and can also be viewed as the existence of an optimal weakly automatizable heuristic proof system. The notion of a heuristic acceptor extends the notion of a classical acceptor; in particular, an optimal heuristic acceptor for any distribution simulates every classical acceptor for the same language. We also note that the existence of a co-NP-language L with a polynomial-time samplable distribution on $\overline{L}$ that has no polynomial-time heuristic acceptors is equivalent to the existence of an infinitely-often one-way function. 相似文献
5.
Tadayuki Makino Hidenobu Okabe Shinya Taniguchi Makoto Sakamoto Katsushi Inoue 《Artificial Life and Robotics》2005,9(2):99-101
Recently, related to the open problem whether deterministic and nondeterministic space (especially lower-level) complexity classes are separated, inkdot Turing machines were introduced. On the other hand, due to the advances in many application areas about three-dimensional information processing, the research on three-dimensional automata as the computation of three-dimensional pattern processing has been meaningful. From this viewpoint, we propose a three-dimensional multiinkdot automata, and investigate some properties of three-dimensional multiinkdot automata.This work was presented, in part, at the 9th International Symposium on Artificial Life and Robotics, Oita, Japan, January 28–30, 2004 相似文献
6.
A stack-counter acceptor is a stack acceptor in which the storage alphabet is just one letter. The present paper discusses multi-stack-counter acceptors operating in quasirealtime, i.e., acceptors in which each storage tape is a stack counter and in which there are only a bounded number of consecutive-moves. For each positive integerk let be the family of languages accepted byk-stack-counter acceptors (k-counter acceptors). Each is a principal AFL closed under reversal but not under-free substitution or under intersection. Also, and a specific language in each, is exhibited. For each and there are noi andj such that. It is shown that a quasi-real-timek-stackcounter acceptor is equivalent to one operating in non-deterministic real time. Lastly, it is shown that acceptance by final state of ak-stack-counter acceptor is equivalent to acceptance by empty tape and final state.Also formerly with System Development Corporation, Santa Monica, California. Research sponsored in part by the Air Force Cambridge Research Laboratories, Office of Aerospace Research, USAF, under Contract F19628-70-C-0023; by the Air Force Office of Scientific Research, Office of Aerospace Research, USAF, under AFOSR No. F44620-70-C-0013; and by NSF Grant No. GJ454. 相似文献
7.
Reinhard Klette 《Information Sciences》1980,22(1):37-43
The languages accepted by bottom-up triangle cellular acceptors (UTCAs) in log diameter time are the same as those accepted by UTCAs in which a cell's new state depends only on its sons' states and not on its own preceding state. This set of languages remains the same if we allow log diameter + constant time, but it increases if we allow 2 log diameter time. It is also shown that this set is the same as the set of languages generated by a special class of “power of 2” OL-systems. 相似文献
8.
Makoto Sakamoto Takao Ito Hiroshi Furutani Michio Kono Satoshi Ikeda 《Artificial Life and Robotics》2008,13(1):368-372
It is conjectured that the three-dimensional pattern processing has its own difficulties not arising in two-dimensional case.
One of these difficulties occurs in recognizing topological properties of three-dimensional patterns because the three-dimensional
neighborhood is more complicated than two-dimensional case. Generally a property or relationship is topological only if it
is preserved when an arbitrary “rubber-sheet” distortion is applied to the pictures. For example, adjacency and connectedness
are topological; area, elongatedness, convexity, and straightness are not. In recent years, there have been many interesting
papers on digital topological properties. For example, an interlocking component was defined as a new topological property
in three-dimensional digital pictures, and it was proved that no one marker automaton can recognize interlocking components
in a three-dimensional digital picture. In this paper, we deal with recognizability of topological components by three-dimensional
Turing machines, and investigate some properties.
This work was presented in part at the 12th International Symposium on Artificial Life and Robotics, Oita, Japan, January
25–27, 2007 相似文献
9.
When an image is viewed at varying resolutions, it is known to create discrete perceptual jumps or transitions amid the continuous
intensity changes. In this paper, we study a perceptual scale-space theory which differs from the traditional image scale-space theory in two aspects. (i) In representation, the perceptual scale-space adopts a full generative model. From a Gaussian
pyramid it computes a sketch pyramid where each layer is a primal sketch representation (Guo et al. in Comput. Vis. Image Underst. 106(1):5–19, 2007)—an attribute graph whose elements are image primitives for the image structures. Each primal sketch graph generates the
image in the Gaussian pyramid, and the changes between the primal sketch graphs in adjacent layers are represented by a set
of basic and composite graph operators to account for the perceptual transitions. (ii) In computation, the sketch pyramid and graph operators are inferred, as hidden
variables, from the images through Bayesian inference by stochastic algorithm, in contrast to the deterministic transforms
or feature extraction, such as computing zero-crossings, extremal points, and inflection points in the image scale-space.
Studying the perceptual transitions under the Bayesian framework makes it convenient to use the statistical modeling and learning
tools for (a) modeling the Gestalt properties of the sketch graph, such as continuity and parallelism etc; (b) learning the
most frequent graph operators, i.e. perceptual transitions, in image scaling; and (c) learning the prior probabilities of
the graph operators conditioning on their local neighboring sketch graph structures. In experiments, we learn the parameters
and decision thresholds through human experiments, and we show that the sketch pyramid is a more parsimonious representation
than a multi-resolution Gaussian/Wavelet pyramid. We also demonstrate an application on adaptive image display—showing a large
image in a small screen (say PDA) through a selective tour of its image pyramid. In this application, the sketch pyramid provides
a means for calculating information gain in zooming-in different areas of an image by counting a number of operators expanding
the primal sketches, such that the maximum information is displayed in a given number of frames.
A short version was published in ICCV05 (Wang et al. 2005). 相似文献
10.
《Information Fusion》2008,9(2):176-185
Medical image fusion plays an important role in clinical applications such as image-guided surgery, image-guided radiotherapy, non-invasive diagnosis, and treatment planning. Pulse coupled neural network (PCNN) is derived from the synchronous neuronal burst phenomena in the cat visual cortex. However, it is very difficult to directly apply original PCNN into the field of image fusion, because its model has some shortcomings. Although a significant amount of research work has been done in developing various medical image algorithms, one disadvantage with the approaches is that they cannot deal with different kinds of medical images. In this instance, we propose a novel multi-channel model – m-PCNN for the first time and apply it to medical image fusion. In the paper, firstly the mathematical model of m-PCNN is described, and then dual-channel model as a special case of m-PCNN is introduced in detail. In order to show that the m-PCNN can deal with multimodal medical images, we used four pairs of medical images with different modalities as our experimental subjects. At the same time, in comparison with other methods (Contrast pyramid, FSD pyramid, Gradient pyramid, Laplacian pyramid, etc.), the performance and relative importance of various methods is investigated using the Mutual Information criteria. Experimental results show our method outperforms other methods, in both visual effect and objective evaluation criteria. 相似文献
11.
Qing Zhang Youetsu Sato Jun‐ya Takahashi Kazunobu Muraoka Norishige Chiba 《Computer Animation and Virtual Worlds》1999,10(1):27-37
Suibokuga is a style of monochrome painting characterized by the use of Chinese black ink (sumi), a complex interaction between brush, ink and paper, and such visual features as Noutan (shade), Kasure (scratchiness), and Nijimi (blur). In this paper we present a simple behavioural model of water and ink particles based on a 2D cellular automaton computational model, and its application to a Suibokuga‐like rendering of 3D trees. Copyright © 1999 John Wiley & Sons, Ltd. 相似文献
12.
The Pyramid network is a desirable network topology used as both software data-structure and hardware architecture. In this
paper, we propose a general definition for a class of pyramid networks that are based on grid connections between the nodes
in each level. Contrary to the conventional pyramid network in which the nodes in each level form a mesh, the connections
between these nodes may also be according to other grid-based topologies such as the torus, hypermesh or WK-recursive. Such
pyramid networks form a wide class of interconnection networks that possess rich topological properties. We study a number
of important properties of these topologies for general-purpose parallel processing applications. In particular, we prove
that such pyramids are Hamiltonian-connected, i.e. for any arbitrary pair of nodes in the network there exists at least one
Hamiltonian path between the two given nodes, and pancyclic, i.e. any cycle of length 3, 4 … and N, can be embedded in a given N-node pyramid network. It is also proven that two link-disjoint Hamiltonian cycles exist in the torus-pyramid and hypermesh-pyramid
networks. 相似文献
13.
Bin Jiang Jian Pei Xuemin Lin Yidong Yuan 《Journal of Intelligent Information Systems》2012,38(1):1-39
Uncertain data are inherent in some important applications. Although a considerable amount of research has been dedicated
to modeling uncertain data and answering some types of queries on uncertain data, how to conduct advanced analysis on uncertain
data remains an open problem at large. In this paper, we tackle the problem of skyline analysis on uncertain data. We propose a novel probabilistic skyline model where an uncertain object may take a probability to be in the skyline, and a p-skyline contains all objects whose skyline probabilities are at least p (0 < p ≤ 1). Computing probabilistic skylines on large uncertain data sets is challenging. We develop a bounding-pruning-refining
framework and three algorithms systematically. The bottom-up algorithm computes the skyline probabilities of some selected
instances of uncertain objects, and uses those instances to prune other instances and uncertain objects effectively. The top-down
algorithm recursively partitions the instances of uncertain objects into subsets, and prunes subsets and objects aggressively.
Combining the advantages of the bottom-up algorithm and the top-down algorithm, we develop a hybrid algorithm to further improve
the performance. Our experimental results on both the real NBA player data set and the benchmark synthetic data sets show
that probabilistic skylines are interesting and useful, and our algorithms are efficient on large data sets. 相似文献
14.
By analogy with the concept of interpretation of a grammar, the notion of interpretation of a pushdown acceptor is introduced for studying the pushdown-like devices structurally close to a given master pushdown acceptor. The main result established is that the family of languages accepted by those pushdown-like acceptors defined by interpretations of a fixed pushdown acceptor coincide with the family of languages generated by those grammars defined by interpretations of some grammar, and conversely. 相似文献
15.
Makoto Sakamoto Takao Ito Hiroshi Furutani Michio Kono 《Artificial Life and Robotics》2008,13(1):27-30
Informally, the parallel Turing machine (PTM) proposed by Wiedermann is a set of identical usual sequential Turing machines
(STMs) cooperating on two common tapes: storage tape and input tape. Moreover, STMs which represent the individual processors
of a parallel computer can multiply themselves in the course of computation. On the other hand, during the past 25 years or
so, automata on a three-dimensional tape have been proposed as computational models of three-dimensional pattern processing,
and several properties of such automata have been obtained. We proposed a three-dimensional parallel Turing machine (3-PTM),1 and dealt with a hardware-bounded 3-PTM whose inputs are restricted to cubic ones. We believe that this machine is useful
in measuring the parallel computational complexity of three-dimensional images. Here, we continue the study of 3-PTM, whose
inputs are restricted to cubic ones, and investigate some of its accepting powers.
This work was presented in part at the First European Workshop on Artificial Life and Robotics, Vienna, Austria, July 12–13,
2007 相似文献
16.
Azriel Rosenfeld 《Journal of Parallel and Distributed Computing》1985,2(4):404-411
The prism machine is a stack of n cellular arrays, each of size 2n × 2n. Cell (i, j) on level k is connected to cells (i, j), (i + 2k, j), and (i, j + 2k) on level k + 1, 1 ≤ k < n, where the sums are modulo 2n. Such a machine can perform various operations (e.g., “Gaussian” convolutions or least-squares polynomial fits) on image neighborhoods of power-of-2 sizes in every position in O(n) time, unlike a pyramid machine which can do this only in sampled positions. It can also compute the discrete Fourier transform in O(n) time. It consists of n · 4n cells, while a pyramid consists of fewer than 4n+1/3 cells; but in practice n would be at most 10, so that a prism would be at most about seven times as large as a pyramid. 相似文献
17.
Kenichi Morita 《Theoretical computer science》2011,412(30):3856-3865
In this paper, we investigate how 1-D reversible cellular automata (RCAs) can simulate reversible Turing machines (RTMs) and cyclic tag systems (CTSs). A CTS is a universal string rewriting system proposed by M. Cook. First, we show that for any m-state n-symbol RTM there is a 1-D 2-neighbor RCA with a number of states less than (m+2n+1)(m+n+1) that simulates it. It improves past results both in the number of states and in the neighborhood size. Second, we study the problem of finding a 1-D RCA with a small number of states that can simulate any CTS. So far, a 30-state RCA that can simulate any CTS and works on ultimately periodic infinite configurations has been given by K. Morita. Here, we show there is a 24-state 2-neighbor RCA with this property. 相似文献
18.
Let A be a set and let G be a group, and equip AG with its prodiscrete uniform structure. Let τ:AG→AG be a map. We prove that τ is a cellular automaton if and only if τ is uniformly continuous and G-equivariant. We also give an example showing that a continuous and G-equivariant map τ:AG→AG may fail to be a cellular automaton when the alphabet set A is infinite. 相似文献
19.
Multi-Agent (MA) product systems were defined in [I. Romanovski, P.E. Caines, On the supervisory control of multi-agent products systems, IEEE Trans. Automated Control 51(5) (2006)] where the notion of an MA controllable vector language specification was introduced and necessary and sufficient conditions for the existence of a supervisor for such a specification were derived. In this paper we present a set of results about the controllability of an MA product system and its components. In particular, we obtain an algorithm for finding the infimal MA-controllable superlanguage infMA(K) of a given vector (language) specification K w.r.t. an MA product system G and establish that in fact . It is proven that there is an algorithmic procedure for the recursive construction of MA supervisors when additional automata are added to a system via the MA product. Controllability properties of component structures (such as standard controllability and MA controllability of projections) are considered. Several examples are given to illustrate the results of the paper. 相似文献
20.
The notion of Boyer-Moore automaton was introduced by Knuth, Morris, and Pratt in their historical paper on fast pattern matching. It leads to an algorithm that requires more preprocessing but is more efficient than the original Boyer-Moore's algorithm. We formalize the notion of Boyer-Moore automaton and we give an efficient building algorithm. Also, bounds on the number of states are presented, and the concept of potential of a transition is introduced to improve the worst-and average-case behavior of these machines. We show that looking at the rightmost unknown character, as suggested by Knuthet al., is not necessarily optimal.R. A. Baeza-Yates gratefully acknowledges the support of Grant C-11001 from Fundación Andes, and C. Choffrut gratefully acknowledges the support of the PRC Mathématiques et Informatique. 相似文献