PL
 |
EN
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 12

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last
Wyniki wyszukiwania
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available remote An Algorithmic Approach to Tilings of Hyperbolic Spaces: Universality Results
Margenstern M.
Fundamenta Informaticae
|
2015
|
Vol. 138, nr 1/2
113--125
EN
In this paper, our results on algorithmic analysis of tiling in hyperbolic spaces are discussed. We overview results and developments obtained by the approach, focusing on the construction of universal cellular automata in hyperbolic spaces with a minimal number of cell states.
2
Content available remote Universality of Splicing Test Tube Systems with Two Tubes
Verlan S., Margenstern M.
Fundamenta Informaticae
|
2011
|
Vol. 110, nr 1-4
329-342
EN
Splicing test tube systems are one of the first distributed computing models based on splicing. The model introduces (test) tubes where the splicing operation is applied, which are arranged in a communication network with filters that permits to redistribute the words between the tubes at each step. We show that the computational completeness can be achieved with two tubes when the communication graph does not have self-loops. We also construct a universal splicing test tube system with 2 tubes having 23 rules.
3
Content available remote The Injectivity of the Global Function of a Cellular Automaton in the Hyperbolic Plane is Undecidable
Margenstern M.
Fundamenta Informaticae
|
2009
|
Vol. 94, nr 1
63-99
EN
In this paper, we look at the following question. We consider cellular automata in the hyperbolic plane, see [6, 22, 9, 12] and we consider the global function defined on all possible configurations. Is the injectivity of this function undecidable? The problem was answered positively in the case of the Euclidean plane by Jarkko Kari, in 1994, see [4]. In the present paper, we show that the answer is also positive for the hyperbolic plane: the problem is undecidable.
4
Content available remote Array P Systems and t-Communication
Subramanian K.G., Ali R.M., Nagar A.K., Margenstern M.
Fundamenta Informaticae
|
2009
|
Vol. 91, nr 1
145-159
EN
The two areas of grammar systems and P systems, which have provided interesting computational models in the study of formal string language theory have been in the recent past effectively linked in [4] by incorporating into P systems, a communication mode called t-mode of cooperating distributed grammar systems. On the other hand cooperating array grammar systems [5] and array P systems [1] have been developed in the context of two-dimensional picture description. In this paper, motivated by the study of [4], these two systems are studied by linking them through the t-communication mode, thus bringing out the picture description power of these systems.
5
Content available remote On Algebraic Structure of Neighborhoods of Cellular Automata-Horse Power Problem-
Nishio H., Margenstern M., Haeseler F. von
Fundamenta Informaticae
|
2007
|
Vol. 78, nr 3
397-416
EN
In a previous paper we formulated and analyzed the structure of neighborhoods of cellular automata in an algebraic setting such that the cellular space S is represented by the Cayley graph of a finitely generated group and the neighbors are defined as a semigroup generated by the neighborhood N as a subset of S, Nishio and Margenstern 2004 [14,15]. Particularly we discussed the horse power problem whether the motion of a horse (knight) fills the infinite chess board or Z^2- that is, an algebraic problem whether a subset of a group generates it or not. Among others we proved that a horse fills Z^2 even when its move is restricted to properly chosen 3 directions and gave a necessary and sufficient condition for a generalized 3-horse to fill Z^2. This paper gives further developments of the horse power problem, say, on the higher dimensional Euclidean grid, the hexagonal grid and the hyperbolic plane.
6
Content available remote Time-Varying Distributed H Systems: An Overview
Margenstern M., Verlan S., Rogozhin Y.
Fundamenta Informaticae
|
2005
|
Vol. 64, nr 1-4
291-306
EN
Time-varying distributed H systems are a well known model of molecular computing. In this article we present an overview of this model, its history, related results, and open problems.
7
Content available remote About Splicing P Systems with One Membrane
Verlan S., Margenstern M.
Fundamenta Informaticae
|
2005
|
Vol. 65, nr 3
279--290
EN
In this article we consider splicing P systems with one membrane. We show that the original definition of splicing P systems is not complete and we propose several variants in order to complete it. We show that the choice of the variant is important and that the computational power of splicing P systems with one membrane directly depends on it.
8
Content available remote Tree operations in P systems and [lambda]-calculus
Jonoska N., Margenstern M.
Fundamenta Informaticae
|
2004
|
Vol. 59, nr 1
67-90
EN
In this paper we introduce a membrane system (named lP systems) in which the computation is performed through certain operations on the tree structure of the membranes. The objects within the membranes play the role of catalysts for the operations. The result of the computation is the final configuration of the system. We show that lP systems can simulate pure l-calculus and so they have universal computational power. We also show that NP-complete problems can be solved in polynomial time in this way by showing that 3SAT is solvable in linear time with linear input.
9
Content available remote Register Cellular Automata in the Hyperbolic Plane
Grigorieff S., Margenstern M.
Fundamenta Informaticae
|
2004
|
Vol. 61, nr 1
19--27
EN
In this paper, we consider cellular automata on special grids of the hyperbolic plane: the grids are constructed on infinigons, i.e. polygons with infinitely many sides. We show that the truth of arithmetical formulas can be decided in finite time with infinite initial recursive configurations. Next, we define a new kind of cellular automata, endowed with data and more powerful operations which we call register cellular automata. This time, starting from finite configurations, it is possible to decide the truth of arithmetic formulas in linear time with respect to the size of the formula.
10
Content available remote Tools for devising cellular automata in the hyperbolic 3D space
Margenstern M., Skordev G.
Fundamenta Informaticae
|
2003
|
Vol. 58, nr 3,4
369--398
EN
The study of cellular automata (CA) on tilings of hyperbolic plane was initiated in [3]. Appropriate tools were developed which allow linear algorithms to implement cellular automata on the tiling of the hyperbolic plane with the regular rectangular pentagon. In this paper we tackle the problem of devising similar tools in the case of the 3D hyperbolic space. The tools are given for the rectangular dodecahedral tiling of the 3D hyperbolic space. We give an algorithm which computes all needed information from the number of a cell. The algorithm is cubic in time and quadratic in space.
11
Content available remote On the Infinigons of the Hyperbolic Plane, A combinatorial approach
Margenstern M.
Fundamenta Informaticae
|
2003
|
Vol. 56, nr 3
255-272
EN
In this paper, we pay a new visit to an object of hyperbolic geometry which, perhaps, did not draw on itself all the attention it may deserve. The paper gives a simple definition of this object, infinigons, which was implicit in general considerations about tilings of the hyperbolic plane, and which was not definied in its all possible extensions. From the simple construction of the infinigons and using the ideas of the splitting method being introduced by the author in the case of tilings being based on the replication of regular polygons, we give an algorithmic construction of the infinigrids. On the way, we give a simple geometrical characterisation of the infinigons in terms of pencils of lines.
12
Content available remote Self-describing Turing machines
Margenstern M., Rogozhin Y.
Fundamenta Informaticae
|
2002
|
Vol. 50, nr 3,4
285-303
EN
After a sketchy historical account on the question of self-describeness and self-reproduction, and after discussing the definition of suitable encodings for self-describeness, we give the construction of several self-describing Turing machines, namely self-describing machines with, respectively, 350, 267, 224 and 206 instructions.
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.