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

Page 1

Displaying 1 – 6 of 6

Showing per page

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

Currently displaying 1 – 6 of 6

Page 1