Page 1
José L. Balcázar Navarro (1989)
Revista Matemática de la Universidad Complutense de Madrid
Using polynomial time self-reducibility structures, we characterize certain helping notions, show how the characterization provides the main tool for the proof of known relationships between decisional and functional NP-complete problems, and extend this relationships to the case of optimization NP-complete problems.
Stefan Węgrzyn, Ryszard Winiarczyk, Lech Znamirowski (2003)
International Journal of Applied Mathematics and Computer Science
Recent research on the nanotechnological processes of molecular products and object synthesis as well as research on the nanosystems of informatics, stimulates the development of technical systems of informatics. Until now, they have been used mainly for computational tasks when, similarly to biological organisms, they allowed the development of self-replicating products and complete objects. One can focus here on the model of a circulation of materials, information and energy in a biological cell,...
Thomas Lickteig, Klaus Meer (1997)
Revista Matemática de la Universidad Complutense de Madrid
We study matrix calculations such as diagonalization of quadratic forms under the aspect of additive complexity and relate these complexities to the complexity of matrix multiplication. While in Bürgisser et al. (1991) for multiplicative complexity the customary thick path existence argument was sufficient, here for additive complexity we need the more delicate finess of the real spectrum (cf. Bochnak et al. (1987), Becker (1986), Knebusch and Scheiderer (1989)) to obtain a complexity relativization....
M. Krause, Ch. Meinel, St. Waack (1992)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Matthias Krause (1992)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Karel Čulík II (1967)
Kybernetika
S. A. Greibach, C. Wrathall (1986)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
G. Buntrock, F. Drewes, C. Lautemann, T. Mossakowski (1991)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Violetta Lonati, Matteo Pradella (2011)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Wang automata are devices for picture language recognition recently introduced by us, which characterize the class REC of recognizable picture languages. Thus, Wang automata are equivalent to tiling systems or online tessellation acceptors, and are based like Wang systems on labeled Wang tiles. The present work focus on scanning strategies, to prove that the ones Wang automata are based on are those following four kinds of movements: boustrophedonic, “L-like”, “U-like”, and spirals.
Violetta Lonati, Matteo Pradella (2011)
RAIRO - Theoretical Informatics and Applications
Wang automata are devices for picture language recognition recently introduced by us, which characterize the class REC of recognizable picture languages. Thus, Wang automata are equivalent to tiling systems or online tessellation acceptors, and are based like Wang systems on labeled Wang tiles. The present work focus on scanning strategies, to prove that the ones Wang automata are based on are those following four kinds of movements: boustrophedonic, “L-like”, “U-like”, and spirals.
Martin Kutrib, Matthias Wendlandt (2012)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
We introduce and investigate string assembling systems which form a computational model that generates strings from copies out of a finite set of assembly units. The underlying mechanism is based on piecewise assembly of a double-stranded sequence of symbols, where the upper and lower strand have to match. The generation is additionally controlled by the requirement that the first symbol of a unit has to be the same as the last symbol of the strand generated so far, as well as by the distinction...
Martin Kutrib, Matthias Wendlandt (2012)
RAIRO - Theoretical Informatics and Applications
We introduce and investigate string assembling systems which form a computational model that generates strings from copies out of a finite set of assembly units. The underlying mechanism is based on piecewise assembly of a double-stranded sequence of symbols, where the upper and lower strand have to match. The generation is additionally controlled by the requirement that the first symbol of a unit has to be the same as the last symbol of the strand generated so far, as well as by the distinction...
V. Geffert (1993)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Abuzer Yakaryılmaz (2012)
RAIRO - Theoretical Informatics and Applications
In automata theory, quantum computation has been widely examined for finite state machines, known as quantum finite automata (QFAs), and less attention has been given to QFAs augmented with counters or stacks. In this paper, we focus on such generalizations of QFAs where the input head operates in one-way or realtime mode, and present some new results regarding their superiority over their classical counterparts. Our first result is about the nondeterministic...
Abuzer Yakaryılmaz (2012)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
In automata theory, quantum computation has been widely examined for finite state machines, known as quantum finite automata (QFAs), and less attention has been given to QFAs augmented with counters or stacks. In this paper, we focus on such generalizations of QFAs where the input head operates in one-way or realtime mode, and present some new results regarding their superiority over their classical counterparts. Our first result is about the nondeterministic acceptance mode: Each quantum model...
Abuzer Yakaryılmaz (2012)
RAIRO - Theoretical Informatics and Applications
In automata theory, quantum computation has been widely examined for finite state machines, known as quantum finite automata (QFAs), and less attention has been given to QFAs augmented with counters or stacks. In this paper, we focus on such generalizations of QFAs where the input head operates in one-way or realtime mode, and present some new results regarding their superiority over their classical counterparts. Our first result is about the nondeterministic...
Karel Ii Culik, Arto Salomaa, Derick Wood (1984)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Page 1