All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 4 Next

Displaying 61 – 80 of 126

Showing per page

On the continuity set of an Omega rational function

Olivier Carton, Olivier Finkel, Pierre Simonnet (2008)

RAIRO - Theoretical Informatics and Applications

In this paper, we study the continuity of rational functions realized by Büchi finite state transducers. It has been shown by Prieur that it can be decided whether such a function is continuous. We prove here that surprisingly, it cannot be decided whether such a function f has at least one point of continuity and that its continuity set C(f) cannot be computed. In the case of a synchronous rational function, we show that its continuity set is rational and that it can be computed. Furthermore...

Pipelined decomposable BSP computers

Martin Beran (2002)

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

The class of weak parallel machines is interesting, because it contains some realistic parallel machine models, especially suitable for pipelined computations. We prove that a modification of the bulk synchronous parallel (BSP) machine model, called decomposable BSP (dBSP), belongs to the class of weak parallel machines if restricted properly. We will also correct some earlier results about pipelined parallel Turing machines.

Pipelined Decomposable BSP Computers

Martin Beran (2010)

RAIRO - Theoretical Informatics and Applications

The class of weak parallel machines is interesting, because it contains some realistic parallel machine models, especially suitable for pipelined computations. We prove that a modification of the bulk synchronous parallel (BSP) machine model, called decomposable BSP (dBSP), belongs to the class of weak parallel machines if restricted properly. We will also correct some earlier results about pipelined parallel Turing machines.

Reaction automata working in sequential manner

Fumiya Okubo (2014)

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

Based on the formal framework of reaction systems by Ehrenfeucht and Rozenberg [Fund. Inform. 75 (2007) 263–280], reaction automata (RAs) have been introduced by Okubo et al. [Theoret. Comput. Sci. 429 (2012) 247–257], as language acceptors with multiset rewriting mechanism. In this paper, we continue the investigation of RAs with a focus on the two manners of rule application: maximally parallel and sequential. Considering restrictions on the workspace and the λ-input mode, we introduce the corresponding...

Restricted nondeterministic read-once branching programs and an exponential lower bound for integer multiplication

Beate Bollig (2001)

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

Branching programs are a well established computation model for Boolean functions, especially read-once branching programs have been studied intensively. In this paper the expressive power of nondeterministic read-once branching programs, more precisely the class of functions representable in polynomial size, is investigated. For that reason two restricted models of nondeterministic read-once branching programs are defined and a lower bound method is presented. Furthermore, the first exponential...

Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication

Beate Bollig (2010)

RAIRO - Theoretical Informatics and Applications

Branching programs are a well established computation model for Boolean functions, especially read-once branching programs have been studied intensively. In this paper the expressive power of nondeterministic read-once branching programs, more precisely the class of functions representable in polynomial size, is investigated. For that reason two restricted models of nondeterministic read-once branching programs are defined and a lower bound method is presented. Furthermore, the first exponential...

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

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

Currently displaying 61 – 80 of 126