The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
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...
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...
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