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.
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,...
After a translation of an input string, , to an output string, , a self- reproducing pushdown transducer can make a self-reproducing step during which it moves to its input tape and translates it again. In this self- reproducing way, it can repeat the translation -times for any . 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...
In the paper the semantics of MML Query queries is given. The formalization is done according to [4]
Semantics of order directives of MML Query is presented. The formalization is done according to [1]
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...
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 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....
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.