Log in

Relevant bibliographies by topics / Parallel Automata / Journal articles

To see the other types of publications on this topic, follow the link: Parallel Automata.

Journal articles on the topic 'Parallel Automata'

Author: Grafiati

Published: 4 June 2021

Last updated: 1 February 2022

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 50 journal articles for your research on the topic 'Parallel Automata.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

CSUHAJ-VARJÚ, ERZSÉBET, CARLOS MARTÍN-VIDE, VICTOR MITRANA, and GYÖRGY VASZIL. "PARALLEL COMMUNICATING PUSHDOWN AUTOMATA SYSTEMS." International Journal of Foundations of Computer Science 11, no. 04 (December 2000): 631–50. http://dx.doi.org/10.1142/s0129054100000338.

Full text

Abstract:

We consider automata systems consisting of several pushdown automata working in parallel and communicating the contents of their stacks by request, using a communication strategy borrowed from grammar system theory. We investigate the computational power of these mechanisms. We prove that non-centralized parallel communicating pushdown automata systems with a bounded number of components, where each automaton is allowed to issue a query, are able to recognize all recursively enumerable languages. We also present homomorphical characterizations of the class of recursively enumerable languages for the centralized variants, where only a distinguished automaton issues queries. Moreover, we show that these centralized variants are at least as powerful as one-way multihead pushdown automata. Finally, some open problems and further directions of research are discussed.

APA, Harvard, Vancouver, ISO, and other styles

2

Subramaniyan, Arun, and Reetuparna Das. "Parallel Automata Processor." ACM SIGARCH Computer Architecture News 45, no. 2 (September 14, 2017): 600–612. http://dx.doi.org/10.1145/3140659.3080207.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Tachon, Thibaut, Chong Li, Gaétan Hains, and Frédéric Loulergue. "Automated Generation of BSP Automata." Parallel Processing Letters 27, no. 01 (March 2017): 1740002. http://dx.doi.org/10.1142/s0129626417400023.

Full text

Abstract:

Bulk-Synchronous Parallel (BSP) is a bridging model between abstract execution and concrete parallel architectures that retains enough information to model performance scalability. In order to model BSP program executions, Hains adapted the theory of finite automata to the BSP paradigm by introducing BSP automata [12]. In the initial description of the theory, BSP automata had to be explicitly defined as structured sets of states and transitions. The lack of a clean and efficient algorithm for generating them from regular expressions would have prevented this theory from being used in practice. To alleviate this problem we introduce in this paper an algorithm that generates a BSP automaton recognizing a BSP language defined by a BSP regular expression. The main practical use of BSP automata developed in this paper is the parallelization of finite state automata with an explicit distribution and a performance model, that enable parallel matching of regular expressions. Secondarily, BSP regular expressions provide a convenient structure for automatic code generation of imperative BSP programs that is also developed in this paper.

APA, Harvard, Vancouver, ISO, and other styles

4

CANTONE, DOMENICO, and SIMONE FARO. "A SPACE EFFICIENT BIT-PARALLEL ALGORITHM FOR THE MULTIPLE STRING MATCHING PROBLEM." International Journal of Foundations of Computer Science 17, no. 06 (December 2006): 1235–51. http://dx.doi.org/10.1142/s0129054106004388.

Full text

Abstract:

Finite (nondeterministic) automata are very useful building blocks in the field of string matching. This is particularly true in the case of multiple pattern matching, where the use of factor-based automata can reduce substantially the number of computational steps when the patterns have large common factors. Direct simulation of nondeterministic automata can be performed very efficiently using the bit-parallelism technique, though this is not necessarily true for factor-based automata. In this paper we present an algorithm for the multiple string matching problem, based on the bit-parallel simulation of nondeterministic factor-based automata which satisfy a particular ordering condition. We also show how to enforce such condition by suitably modifying a minimal initial automaton, through equivalence preserving transformations. The resulting automaton turns out to be smaller than the corresponding maximal automata used by existing bit-parallel algorithms, as they do not take any advantage of common factors in patterns.

APA, Harvard, Vancouver, ISO, and other styles

5

Bruchertseifer, Jens, and Henning Fernau. "Synchronizing series-parallel deterministic finite automata with loops and related problems." RAIRO - Theoretical Informatics and Applications 55 (2021): 7. http://dx.doi.org/10.1051/ita/2021005.

Full text

Abstract:

We study the problem DFA-SW of determining if a given deterministic finite automaton A possesses a synchronizing word of length at most k for automata whose (multi-)graphs are TTSPL, i.e., series-parallel, plus allowing some self-loops. While DFA-SW remains NP-complete on TTSPL automata, we also find (further) restrictions with efficient (parameterized) algorithms. We also study the (parameterized) complexity of related problems, for instance, extension variants of the synchronizing word problem, or the problem of finding smallest alphabet-induced synchronizable sub-automata.

APA, Harvard, Vancouver, ISO, and other styles

6

LI, GUOQIANG, XIAOJUAN CAI, and SHOJI YUEN. "MODELING AND ANALYSIS OF REAL-TIME SYSTEMS WITH MUTEX COMPONENTS." International Journal of Foundations of Computer Science 23, no. 04 (June 2012): 831–51. http://dx.doi.org/10.1142/s0129054112400382.

Full text

Abstract:

Timed automata are commonly recognized as a formal behavioral model for real-time systems. For compositional system design, parallel composition of timed automata as proposed by Larsen et al. [22] is useful. Although parallel composition provides a general method for system construction, in the low level behavior, components often behave sequentially by passing control via communication. This paper proposes a behavioral model, named controller automata, to combine timed automata by focusing on the control passing between components. In a controller automaton, to each state a timed automaton is assigned. A timed automaton at a state may be preempted by the control passing to another state by a global labeled transition. A controller automaton properly extends the expressive power because of the stack, but this can make the reachability problem undecidable. Given a strict partial order over states, we show that this problem can be avoided and a controller automaton can be faithfully translated into a timed automaton.

APA, Harvard, Vancouver, ISO, and other styles

7

TORBEY, SAMI. "TOWARDS A FRAMEWORK FOR INTUITIVE PROGRAMMING OF CELLULAR AUTOMATA." Parallel Processing Letters 19, no. 01 (March 2009): 73–83. http://dx.doi.org/10.1142/s0129626409000079.

Full text

Abstract:

The ability to obtain complex global behaviour from simple local rules makes cellular automata an interesting platform for massively parallel computation. However, manually designing a cellular automaton to perform a given computation can be extremely difficult, and automated design techniques such as genetic programming have their limitations because of the absence of human intuition. In this paper, we propose elements of a framework whose goal is to make the manual synthesis of cellular automata rules exhibiting desired global characteristics more programmer-friendly, while maintaining the simplicity of local processing elements. Although many of the framework elements that we describe here are not new, we group them into a consistent framework and show that they can all be implemented on a traditional cellular automaton, which means that they are merely more human-friendly ways of describing simple cellular automata rules, and not foreign structures that require changing the traditional cellular automaton model.

APA, Harvard, Vancouver, ISO, and other styles

8

Morales, D. G., F. Almeida, C. Rodrı́guez, J. L. Roda, I. Coloma, and A. Delgado. "Parallel dynamic programming and automata theory." Parallel Computing 26, no. 1 (January 2000): 113–34. http://dx.doi.org/10.1016/s0167-8191(99)00098-8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Vollweiler, Marcel, and Friedrich Otto. "Systems of parallel communicating restarting automata." RAIRO - Theoretical Informatics and Applications 48, no. 1 (January 2014): 3–22. http://dx.doi.org/10.1051/ita/2013046.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Bordihn, Henning, and György Vaszil. "Reversible parallel communicating finite automata systems." Acta Informatica 58, no. 4 (July 19, 2021): 263–79. http://dx.doi.org/10.1007/s00236-021-00396-9.

Full text

Abstract:

AbstractWe study the concept of reversibility in connection with parallel communicating systems of finite automata (PCFA in short). We define the notion of reversibility in the case of PCFA (also covering the non-deterministic case) and discuss the relationship of the reversibility of the systems and the reversibility of its components. We show that a system can be reversible with non-reversible components, and the other way around, the reversibility of the components does not necessarily imply the reversibility of the system as a whole. We also investigate the computational power of deterministic centralized reversible PCFA. We show that these very simple types of PCFA (returning or non-returning) can recognize regular languages which cannot be accepted by reversible (deterministic) finite automata, and that they can even accept languages that are not context-free. We also separate the deterministic and non-deterministic variants in the case of systems with non-returning communication. We show that there are languages accepted by non-deterministic centralized PCFA, which cannot be recognized by any deterministic variant of the same type.

APA, Harvard, Vancouver, ISO, and other styles

11

MARTÍN-VIDE, CARLOS, ALEXANDRU MATEESCU, and VICTOR MITRANA. "PARALLEL FINITE AUTOMATA SYSTEMS COMMUNICATING BY STATES." International Journal of Foundations of Computer Science 13, no. 05 (October 2002): 733–49. http://dx.doi.org/10.1142/s0129054102001424.

Full text

Abstract:

An accepting device based on the communication between finite automata working in parallel is introduced. It consists of several finite automata working independently but communicating states to each other by request. Several variants of parallel communicating finite automata systems are investigated from their computational power point of view. We prove that all of them are at most as powerful as multi-head finite automata. Homomorphical characterizations of recursively enumerable languages are obtained starting from languages recognized by all variants of parallel communicating finite automata systems having at most three components. We present a brief comparison with the parallel communicating grammar systems. Some remarks suggesting that these devices might be mildly context-sensitive ones as well as a few open problems and directions for further research are also discussed.

APA, Harvard, Vancouver, ISO, and other styles

12

Otto, Friedrich. "Asynchronous Parallel Communicating Systems of Pushdown Automata." International Journal of Foundations of Computer Science 26, no. 05 (August 2015): 643–66. http://dx.doi.org/10.1142/s0129054115500367.

Full text

Abstract:

We introduce asynchronous variants of the parallel communicating systems of pushdown automata of Csuhaj-Varjú et al. These are obtained by using a response symbol in addition to the usual query symbols. Our main result states that centralized asynchronous parallel communicating systems of pushdown automata of degree n that work in returning mode have exactly the same expressive power as n-head pushdown automata. This holds in the nondeterministic as well as in the deterministic case. In addition, it is shown that the class of binary relations that is computed by centralized asynchronous parallel communicating systems of pushdown automata of degree two that are working in returning mode coincides with the class of pushdown relations.

APA, Harvard, Vancouver, ISO, and other styles

13

BORDIHN, HENNING, MARTIN KUTRIB, and ANDREAS MALCHER. "UNDECIDABILITY AND HIERARCHY RESULTS FOR PARALLEL COMMUNICATING FINITE AUTOMATA." International Journal of Foundations of Computer Science 22, no. 07 (November 2011): 1577–92. http://dx.doi.org/10.1142/s0129054111008891.

Full text

Abstract:

Parallel communicating finite automata (PCFAs) are systems of several finite state automata which process a common input string in a parallel way and are able to communicate by sending their states upon request. We consider deterministic and nondeterministic variants and distinguish four working modes. It is known that these systems in the most general mode are as powerful as one-way multi-head finite automata. It is additionally known that the number of heads corresponds to the number of automata in PCFAs in a constructive way. Thus, undecidability results as well as results on the hierarchies induced by the number of heads carry over from multi-head finite automata to PCFAs in the most general mode. Here, we complement these undecidability and hierarchy results also for the remaining working modes. In particular, we show that classical decidability questions are not semi-decidable for any type of PCFAs under consideration. Moreover, it is proven that the number of automata in the system induces infinite hierarchies for deterministic and nondeterministic PCFAs in three working modes.

APA, Harvard, Vancouver, ISO, and other styles

14

Moreira, Nelma, and Rogério Reis. "Series-Parallel Automata and Short Regular Expressions." Fundamenta Informaticae 91, no. 3-4 (2009): 611–29. http://dx.doi.org/10.3233/fi-2009-0061.

Full text

APA, Harvard, Vancouver, ISO, and other styles

15

Vollweiler, Marcel. "Asynchronous Systems of Parallel Communicating Finite Automata." Fundamenta Informaticae 136, no. 1-2 (2015): 177–97. http://dx.doi.org/10.3233/fi-2015-1149.

Full text

APA, Harvard, Vancouver, ISO, and other styles

16

Spezzano, Giandomenico, and Domenico Talia. "Programming cellular automata algorithms on parallel computers." Future Generation Computer Systems 16, no. 2-3 (December 1999): 203–16. http://dx.doi.org/10.1016/s0167-739x(99)00047-3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

17

Bordihn, Henning, Martin Kutrib, and Andreas Malcher. "Measuring Communication in Parallel Communicating Finite Automata." Electronic Proceedings in Theoretical Computer Science 151 (May 21, 2014): 124–38. http://dx.doi.org/10.4204/eptcs.151.8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

18

Jastrzab, Tomasz. "On Parallel Induction of Nondeterministic Finite Automata." Procedia Computer Science 80 (2016): 257–68. http://dx.doi.org/10.1016/j.procs.2016.05.318.

Full text

APA, Harvard, Vancouver, ISO, and other styles

19

El-Fakih, Khaled, Nina Yevtushenko, Sergey Buffalov, and Gregor v. Bochmann. "Progressive solutions to a parallel automata equation." Theoretical Computer Science 362, no. 1-3 (October 2006): 17–32. http://dx.doi.org/10.1016/j.tcs.2006.05.034.

Full text

APA, Harvard, Vancouver, ISO, and other styles

20

Thathachar, M. A. L., and M. T. Arvind. "Parallel algorithms for modules of learning automata." IEEE Transactions on Systems, Man and Cybernetics, Part B (Cybernetics) 28, no. 1 (1998): 24–33. http://dx.doi.org/10.1109/3477.658575.

Full text

APA, Harvard, Vancouver, ISO, and other styles

21

Goldberg, Robert R., and Jerry Waxman. "Parallel decision procedures for finite state automata." International Journal of Computer Mathematics 49, no. 1-2 (January 1993): 33–40. http://dx.doi.org/10.1080/00207169308804213.

Full text

APA, Harvard, Vancouver, ISO, and other styles

22

Plateau, B., and K. Atif. "Stochastic automata network of modeling parallel systems." IEEE Transactions on Software Engineering 17, no. 10 (1991): 1093–108. http://dx.doi.org/10.1109/32.99196.

Full text

APA, Harvard, Vancouver, ISO, and other styles

23

Avdeev, N. A., P. N. Bibilo, and V. I. Romanov. "Verification and Scheme Implementation of Parallel Automata." Russian Microelectronics 49, no. 1 (January 2020): 62–75. http://dx.doi.org/10.1134/s1063739719060027.

Full text

APA, Harvard, Vancouver, ISO, and other styles

24

Ibarra, Oscar H., Michael A. Palis, and Sam M. Kim. "Fast parallel language recognition by cellular automata." Theoretical Computer Science 41 (1985): 231–46. http://dx.doi.org/10.1016/0304-3975(85)90073-8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

25

Hirst, Tirza. "A Rice-style theorem for parallel automata." Information and Computation 207, no. 1 (January 2009): 1–13. http://dx.doi.org/10.1016/j.ic.2008.10.004.

Full text

APA, Harvard, Vancouver, ISO, and other styles

26

Tošic, Predrag T. "Cellular Automata Communication Models." International Journal of Natural Computing Research 1, no. 3 (July 2010): 66–84. http://dx.doi.org/10.4018/jncr.2010070105.

Full text

Abstract:

In this paper, cellular automata (CA) are viewed as an abstract model for distributed computing. The author argues that the classical CA model must be modified in several important respects to become a relevant model for large-scale MAS. The paper first proposes sequential cellular automata (SCA) and formalizes deterministic and nondeterministic versions of SCA. The author then analyzes differences in possible dynamics between classical parallel CA and various SCA models. The analysis in this paper focuses on one-dimensional parallel and sequential CA with node update rules restricted to simple threshold functions, as arguably the simplest totalistic, yet non-linear (and non-affine) update rules. The author identifies properties of asymptotic dynamics that can be proven to be entirely due to the assumption of perfect synchrony in classical, parallel CA. Finally, the paper discusses what an appropriate CA-based abstraction would be for large-scale distributed computing, insofar as the inter-agent communication models. In that context, the author proposes genuinely asynchronous CA and discusses main differences between genuinely asynchronous CA and various weakly asynchronous sequential CA models found in the literature.

APA, Harvard, Vancouver, ISO, and other styles

27

BAETEN, JOS C. M., BAS LUTTIK, TIM MULLER, and PAUL VAN TILBURG. "Expressiveness modulo bisimilarity of regular expressions with parallel composition." Mathematical Structures in Computer Science 26, no. 6 (January 2, 2015): 933–68. http://dx.doi.org/10.1017/s0960129514000309.

Full text

Abstract:

The languages accepted by finite automata are precisely the languages denoted by regular expressions. In contrast, finite automata may exhibit behaviours that cannot be described by regular expressions up to bisimilarity. In this paper, we consider extensions of the theory of regular expressions with various forms of parallel composition and study the effect on expressiveness. First we prove that adding pure interleaving to the theory of regular expressions strictly increases its expressiveness modulo bisimilarity. Then, we prove that replacing the operation for pure interleaving by ACP-style parallel composition gives a further increase in expressiveness, still insufficient, however, to facilitate the expression of all finite automata up to bisimilarity. Finally, we prove that the theory of regular expressions with ACP-style parallel composition and encapsulation is expressive enough to express all finite automata up to bisimilarity. Our results extend the expressiveness results obtained by Bergstra, Bethke and Ponse for process algebras with (the binary variant of) Kleene's star operation.

APA, Harvard, Vancouver, ISO, and other styles

28

Sun, Feng Wei, and Li Juan Yuan. "Study on the Modeling Method of Software Process Based on Timing and Parallel Automata." Advanced Materials Research 765-767 (September 2013): 1537–40. http://dx.doi.org/10.4028/www.scientific.net/amr.765-767.1537.

Full text

Abstract:

The finite automata theory extended and then the timing parallel automata theory is got and applied in the software process modeling. The establishment of group software process model is on the basis of timing parallel automata which realize the activity planning, resource allocation and progress control of process. The process model has been checked rationality and the rationality definition and check rules have been given. The process modeling method in this paper is intuitive, easy to understand and could describe the dynamic change of process, and also present the concurrent activity and provide the effective support to parallel work and cooperative work.

APA, Harvard, Vancouver, ISO, and other styles

29

BRESLAUER, DANY, and RAMESH HARIHARAN. "OPTIMAL PARALLEL CONSTRUCTION OF MINIMAL SUFFIX AND FACTOR AUTOMATA." Parallel Processing Letters 06, no. 01 (March 1996): 35–44. http://dx.doi.org/10.1142/s0129626496000054.

Full text

Abstract:

This paper gives optimal parallel algorithms for the construction of the smallest deterministic finite automata recognizing all the suffixes and the factors of a string. The algorithms use recently discovered optimal parallel suffix tree construction algorithms together with data structures for the efficient manipulation of trees, exploiting the well known relation between suffix and factor automata and suffix trees.

APA, Harvard, Vancouver, ISO, and other styles

30

Nguyễn, Trường Huy. "Automata Technique for The LCS Problem." Journal of Computer Science and Cybernetics 35, no. 1 (March 18, 2019): 21–37. http://dx.doi.org/10.15625/1813-9663/35/1/13293.

Full text

Abstract:

In this paper, we introduce two eﬃcient algorithms in practice for computing the length of a longest common subsequence of two strings, using automata technique, in sequential and parallel ways. For two input strings of lengths m and n with m ≤ n, the parallel algorithm uses k processors (k ≤ m) and costs time complexity O(n) in the worst case, where k is an upper estimate of the length of a longest common subsequence of the two strings. These results are based on the Knapsack Shaking approach proposed by P. T. Huy et al. in 2002. Experimental results show that for the alphabet of size 256, our sequential and parallel algorithms are about 65.85 and 3.41m times faster than the standard dynamic programming algorithm proposed by Wagner and Fisher in 1974, respectively.

APA, Harvard, Vancouver, ISO, and other styles

31

Cho, Sang, and Dung T. Huynh. "The parallel complexity of finite-state automata problems." Information and Computation 97, no. 1 (March 1992): 1–22. http://dx.doi.org/10.1016/0890-5401(92)90002-w.

Full text

APA, Harvard, Vancouver, ISO, and other styles

32

Seredynski, F., and A. Y. Zomaya. "Sequential and parallel cellular automata-based scheduling algorithms." IEEE Transactions on Parallel and Distributed Systems 13, no. 10 (October 2002): 1009–23. http://dx.doi.org/10.1109/tpds.2002.1041877.

Full text

APA, Harvard, Vancouver, ISO, and other styles

33

Kucharska, Edyta, Katarzyna Grobler-Dębska, Krzysztof Rączka, and Lidia Dutkiewicz. "Cellular Automata approach for parallel machine scheduling problem." SIMULATION 92, no. 2 (January 14, 2016): 165–78. http://dx.doi.org/10.1177/0037549715625120.

Full text

APA, Harvard, Vancouver, ISO, and other styles

34

Sipper, Moshe, Marco Tomassini, and Mathieu S. Capcarrere. "Designing cellular automata using a parallel evolutionary algorithm." Nuclear Instruments and Methods in Physics Research Section A: Accelerators, Spectrometers, Detectors and Associated Equipment 389, no. 1-2 (April 1997): 278–83. http://dx.doi.org/10.1016/s0168-9002(97)89460-0.

Full text

APA, Harvard, Vancouver, ISO, and other styles

35

Phipps, M., and A. Langlois. "Spatial dynamics, cellular automata, and parallel processing computers." Environment and Planning B: Planning and Design 24, no. 2 (1997): 193–204. http://dx.doi.org/10.1068/b240193.

Full text

APA, Harvard, Vancouver, ISO, and other styles

36

Crochemore, Maxime, Costas S. Iliopoulos, Gonzalo Navarro, Yoan J. Pinzon, and Alejandro Salinger. "Bit-parallel (δ,γ)-matching and suffix automata." Journal of Discrete Algorithms 3, no. 2-4 (June 2005): 198–214. http://dx.doi.org/10.1016/j.jda.2004.08.005.

Full text

APA, Harvard, Vancouver, ISO, and other styles

37

Crochemore, Maxime, and Wojciech Rytter. "Parallel construction of minimal suffix and factor automata." Information Processing Letters 35, no. 3 (July 1990): 121–28. http://dx.doi.org/10.1016/0020-0190(90)90060-b.

Full text

APA, Harvard, Vancouver, ISO, and other styles

38

Stotts, P. David, and William Pugh. "Parallel finite automata for modeling concurrent software systems." Journal of Systems and Software 27, no. 1 (October 1994): 27–43. http://dx.doi.org/10.1016/0164-1212(94)90112-0.

Full text

APA, Harvard, Vancouver, ISO, and other styles

39

Jastrzab, Tomasz, Zbigniew J. Czech, and Wojciech Wieczorek. "Parallel Algorithms for Minimal Nondeterministic Finite Automata Inference." Fundamenta Informaticae 178, no. 3 (January 15, 2021): 203–27. http://dx.doi.org/10.3233/fi-2021-2004.

Full text

Abstract:

The goal of this paper is to develop the parallel algorithms that, on input of a learning sample, identify a regular language by means of a nondeterministic finite automaton (NFA). A sample is a pair of finite sets containing positive and negative examples. Given a sample, a minimal NFA that represents the target regular language is sought. We define the task of finding an NFA, which accepts all positive examples and rejects all negative ones, as a constraint satisfaction problem, and then propose the parallel algorithms to solve the problem. The results of comprehensive computational experiments on the variety of inference tasks are reported. The question of minimizing an NFA consistent with a learning sample is computationally hard.

APA, Harvard, Vancouver, ISO, and other styles

40

HERNANDEZ, GONZALO, HANS J. HERRMANN, and ERIC GOLES. "EXTREMAL AUTOMATA FOR IMAGE SHARPENING." International Journal of Modern Physics C 05, no. 06 (December 1994): 923–31. http://dx.doi.org/10.1142/s0129183194001057.

Full text

Abstract:

We study numerically the parallel iteration of Extremal Rules. For four Extremal Rules, conceived for sharpening algorithms for image processing, we measured, on the square lattice with Von Neumann neighborhood and free boundary conditions, the typical transient length, the loss of information and the damage spreading response considering random and smoothening random damage. The same qualitative behavior was found for all the rules, with no noticeable finite size effect. They have a fast logarithmic convergence towards the fixed points of the parallel update. The linear damage spreading response has no discontinuity at zero damage, for both kinds of damage. Three of these rules produce similar effects. We propose these rules as sharpening algorithms for image processing.

APA, Harvard, Vancouver, ISO, and other styles

41

MORITA, KENICHI, SATOSHI UENO, and KATSUNOBU IMAI. "CHARACTERIZING THE ABILITY OF PARALLEL ARRAY GENERATORS ON REVERSIBLE PARTITIONED CELLULAR AUTOMATA." International Journal of Pattern Recognition and Artificial Intelligence 13, no. 04 (June 1999): 523–38. http://dx.doi.org/10.1142/s0218001499000318.

Full text

Abstract:

A PCAAG introduced by Morita and Ueno is a parallel array generator on a partitioned cellular automaton (PCA) that generates an array language (i.e. a set of symbol arrays). A "reversible" PCAAG (RPCAAG) is a backward deterministic PCAAG, and thus parsing of two-dimensional patterns can be performed without backtracking by an "inverse" system of the RPCAAG. Hence, a parallel pattern recognition mechanism on a deterministic cellular automaton can be directly obtained from a RPCAAG that generates the pattern set. In this paper, we investigate the generating ability of RPCAAGs and their subclass. It is shown that the ability of RPCAAGs is characterized by two-dimensional deterministic Turing machines, i.e. they are universal in their generating ability. We then investigate a monotonic RPCAAG (MRPCAAG), which is a special type of an RPCAAG that satisfies monotonic constraint. We show that the generating ability of MRPCAAGs is exactly characterized by two-dimensional deterministic linear-bounded automata.

APA, Harvard, Vancouver, ISO, and other styles

42

Balan, M. Sakthi. "Serializing the Parallelism in Parallel Communicating Pushdown Automata Systems." Electronic Proceedings in Theoretical Computer Science 3 (July 30, 2009): 59–68. http://dx.doi.org/10.4204/eptcs.3.5.

Full text

APA, Harvard, Vancouver, ISO, and other styles

43

Hecker, C., D. Roytenberg, J. R. Sack, and Z. Wang. "System development for parallel cellular automata and its applications." Future Generation Computer Systems 16, no. 2-3 (December 1999): 235–47. http://dx.doi.org/10.1016/s0167-739x(99)00049-7.

Full text

APA, Harvard, Vancouver, ISO, and other styles

44

Das, Debasis, and Rajiv Misra. "Programmable Cellular Automata Based Efficient Parallel AES Encryption Algorithm." International Journal of Network Security & Its Applications 3, no. 6 (November 30, 2011): 197–211. http://dx.doi.org/10.5121/ijnsa.2011.3615.

Full text

APA, Harvard, Vancouver, ISO, and other styles

45

Soreni, Michal, Sivan Yogev, Elizaveta Kossoy, Yuval Shoham, and Ehud Keinan. "Parallel Biomolecular Computation on Surfaces with Advanced Finite Automata." Journal of the American Chemical Society 127, no. 11 (March 2005): 3935–43. http://dx.doi.org/10.1021/ja047168v.

Full text

APA, Harvard, Vancouver, ISO, and other styles

46

Yih-Lang Li and Cheng-Wen Wu. "Cellular automata for efficient parallel logic and fault simulation." IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 14, no. 6 (June 1995): 740–49. http://dx.doi.org/10.1109/43.387734.

Full text

APA, Harvard, Vancouver, ISO, and other styles

47

Giordano, Andrea, Alessio De Rango, Rocco Rongo, Donato D'Ambrosio, and William Spataro. "Dynamic Load Balancing in Parallel Execution of Cellular Automata." IEEE Transactions on Parallel and Distributed Systems 32, no. 2 (February 1, 2021): 470–84. http://dx.doi.org/10.1109/tpds.2020.3025102.

Full text

APA, Harvard, Vancouver, ISO, and other styles

48

INOUE, KATSUSHI, ITSUO SAKURAMOTO, MAKOTO SAKAMOTO, and ITSUO TAKANAMI. "TWO TOPICS CONCERNING TWO-DIMENSIONAL AUTOMATA OPERATING IN PARALLEL." International Journal of Pattern Recognition and Artificial Intelligence 06, no. 02n03 (August 1992): 211–25. http://dx.doi.org/10.1142/s0218001492000126.

Full text

Abstract:

This paper deals with two topics concerning two-dimensional automata operating in parallel. We first investigate a relationship between the accepting powers of two-dimensional alternating finite automata (2-AFAs) and nondeterministic bottom-up pyramid cellular acceptors (NUPCAs), and show that Ω ( diameter × log diameter ) time is necessary for NUPCAs to simulate 2-AFAs. We then investigate space complexity of two-dimensional alternating Turing machines (2-ATMs) operating in small space, and show that if L (n) is a two-dimensionally space-constructible function such that lim n → ∞ L (n)/ loglog n > 1 and L (n) ≤ log n, and L′ (n) is a function satisfying L′ (n) =o (L(n)), then there exists a set accepted by some strongly L (n) space-bounded two-dimensional deterministic Turing machine, but not accepted by any weakly L′ (n) space-bounded 2-ATM, and thus there exists a rich space hierarchy for weakly S (n) space-bounded 2-ATMs with loglog n ≤ S (n) ≤ log n.

APA, Harvard, Vancouver, ISO, and other styles

49

Martı́n-Vide, Carlos, and Victor Mitrana. "Some undecidable problems for parallel communicating finite automata systems." Information Processing Letters 77, no. 5-6 (March 2001): 239–45. http://dx.doi.org/10.1016/s0020-0190(00)00159-9.

Full text

APA, Harvard, Vancouver, ISO, and other styles

50

Hoe, David H. K., Jonathan M. Comer, Juan C. Cerda, Chris D. Martinez, and Mukul V. Shirvaikar. "Cellular Automata-Based Parallel Random Number Generators Using FPGAs." International Journal of Reconfigurable Computing 2012 (2012): 1–13. http://dx.doi.org/10.1155/2012/219028.

Full text

Abstract:

Cellular computing represents a new paradigm for implementing high-speed massively parallel machines. Cellular automata (CA), which consist of an array of locally connected processing elements, are a basic form of a cellular-based architecture. The use of field programmable gate arrays (FPGAs) for implementing CA accelerators has shown promising results. This paper investigates the design of CA-based pseudo-random number generators (PRNGs) using an FPGA platform. To improve the quality of the random numbers that are generated, the basic CA structure is enhanced in two ways. First, the addition of a superrule to each CA cell is considered. The resulting self-programmable CA (SPCA) uses the superrule to determine when to make a dynamic rule change in each CA cell. The superrule takes its inputs from neighboring cells and can be considered itself a second CA working in parallel with the main CA. When implemented on an FPGA, the use of lookup tables in each logic cell removes any restrictions on how the super-rules should be defined. Second, a hybrid configuration is formed by combining a CA with a linear feedback shift register (LFSR). This is advantageous for FPGA designs due to the compactness of the LFSR implementations. A standard software package for statistically evaluating the quality of random number sequences known as Diehardis used to validate the results. Both the SPCA and the hybrid CA/LFSR were found to pass all the Diehardtests.

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!