Displaying 41 – 60 of 407

Showing per page

Self-reducibility structures and solutions of NP problems.

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.

Self-replication processes in nanosystems of informatics

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,...

Self-reproducing pushdown transducers

Alexander Meduna, Luboš Lorenc (2005)

Kybernetika

After a translation of an input string, x , to an output string, y , a self- reproducing pushdown transducer can make a self-reproducing step during which it moves y to its input tape and translates it again. In this self- reproducing way, it can repeat the translation n -times for any n 1 . This paper demonstrates that every recursively enumerable language can be characterized by the domain of the translation obtained from a self- reproducing pushdown transducer that repeats its translation no more than...

Semantics of MML Query

Grzegorz Bancerek (2012)

Formalized Mathematics

In the paper the semantics of MML Query queries is given. The formalization is done according to [4]

Semantics of MML Query - Ordering

Grzegorz Bancerek (2013)

Formalized Mathematics

Semantics of order directives of MML Query is presented. The formalization is done according to [1]

Semantics of value recursion for monadic input/output

Levent Erkök, John Launchbury, Andrew Moran (2002)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Monads have been employed in programming languages for modeling various language features, most importantly those that involve side effects. In particular, Haskell’s IO monad provides access to I/O operations and mutable variables, without compromising referential transparency. Cyclic definitions that involve monadic computations give rise to the concept of value-recursion, where the fixed-point computation takes place only over the values, without repeating or losing effects. In this paper, we...

Semantics of value recursion for Monadic Input/Output

Levent Erkök, John Launchbury, Andrew Moran (2010)

RAIRO - Theoretical Informatics and Applications

Monads have been employed in programming languages for modeling various language features, most importantly those that involve side effects. In particular, Haskell's IO monad provides access to I/O operations and mutable variables, without compromising referential transparency. Cyclic definitions that involve monadic computations give rise to the concept of value-recursion, where the fixed-point computation takes place only over the values, without repeating or losing effects. In this paper,...

Semi-algebraic complexity-additive complexity of diagonalization of quadratic forms.

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....

Semi-commutations and Partial commutations

M. Clerbout, Y. Roos, I. Ryl (2010)

RAIRO - Theoretical Informatics and Applications

The aim of this paper is to show that a semi-commutation function can be expressed as the compound of a sequential transformation, a partial commutation function, and the reverse transformation. Moreover, we give a necessary and sufficient condition for the image of a regular language to be computed by the compound of two sequential functions and a partial commutation function.

Currently displaying 41 – 60 of 407