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 2 Next

Displaying 21 – 40 of 126

Showing per page

Complexity theoretical results on nondeterministic graph-driven read-once branching programs

Beate Bollig (2003)

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 (BP1s) have been studied intensively. Recently two restricted nondeterministic (parity) BP1 models, called nondeterministic (parity) graph-driven BP1s and well-structured nondeterministic (parity) graph-driven BP1s, have been investigated. The consistency test for a BP-model M is the test whether a given BP is really a BP of model M . Here it is proved that the consistency test...

Complexity Theoretical Results on Nondeterministic Graph-driven Read-Once Branching Programs

Beate Bollig (2010)

RAIRO - Theoretical Informatics and Applications

Branching programs are a well-established computation model for boolean functions, especially read-once branching programs (BP1s) have been studied intensively. Recently two restricted nondeterministic (parity) BP1 models, called nondeterministic (parity) graph-driven BP1s and well-structured nondeterministic (parity) graph-driven BP1s, have been investigated. The consistency test for a BP-model M is the test whether a given BP is really a BP of model M. Here it is proved that the consistency...

Dedicated spectral method of Boolean function decomposition

Piotr Porwik, Radomir Stankovic (2006)

International Journal of Applied Mathematics and Computer Science

Spectral methods constitute a useful tool in the analysis and synthesis of Boolean functions, especially in cases when other methods reduce to brute-force search procedures. There is renewed interest in the application of spectral methods in this area, which extends also to the closely connected concept of the autocorrelation function, for which spectral methods provide fast calculation algorithms. This paper discusses the problem of spectral decomposition of Boolean functions using the Walsh transform...

Depth lower bounds for monotone semi-unbounded fan-in circuits

Jan Johannsen (2001)

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

The depth hierarchy results for monotone circuits of Raz and McKenzie [5] are extended to the case of monotone circuits of semi-unbounded fan-in. It follows that the inclusions N C i ⊆ S A C i ⊆ A C i are proper in the monotone setting, for every i ≥ 1 .

Depth Lower Bounds for Monotone Semi-Unbounded Fan-in Circuits

Jan Johannsen (2010)

RAIRO - Theoretical Informatics and Applications

The depth hierarchy results for monotone circuits of Raz and McKenzie [5] are extended to the case of monotone circuits of semi-unbounded fan-in. It follows that the inclusions NCi ⊆ SACi ⊆ ACi are proper in the monotone setting, for every i ≥ 1.

Design of mealy finite-state machines with the transformation of object codes

Alexander Barkalov, Alexander Barkalov (2005)

International Journal of Applied Mathematics and Computer Science

An optimization method of the logic circuit of a Mealy finite-state machine is proposed. It is based on the transformation of object codes. The objects of the Mealy FSM are internal states and sets of microoperations. The main idea is to express the states as some functions of sets of microoperations (internal states) and tags. The application of this method is connected with the use of a special code converter in the logic circuit of an FSM. An example of application is given. The effectiveness...

Efficient calculation of the Reed-Muller form by means of the Walsh transform

Piotr Porwik (2002)

International Journal of Applied Mathematics and Computer Science

The paper describes a spectral method for combinational logic synthesis using the Walsh transform and the Reed-Muller form. A new algorithm is presented that allows us to obtain the mixed polarity Reed-Muller expansion of Boolean functions. The most popular minimisation (sub-minimisation) criterion of the Reed-Muller form is obtained by the exhaustive search of all the polarity vectors. This paper presents a non-exhaustive method for Reed-Muller expansions. The new method allows us to build the...

Essential Arity Gap of Boolean Functions

Shtrakov, Slavcho (2008)

Serdica Journal of Computing

In this paper we investigate the Boolean functions with maximum essential arity gap. Additionally we propose a simpler proof of an important theorem proved by M. Couceiro and E. Lehtonen in [3]. They use Zhegalkin’s polynomials as normal forms for Boolean functions and describe the functions with essential arity gap equals 2. We use to instead Full Conjunctive Normal Forms of these polynomials which allows us to simplify the proofs and to obtain several combinatorial results concerning the Boolean functions...

Gate circuits in the algebra of transients

Janusz Brzozowski, Mihaela Gheorghiu (2005)

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

We study simulation of gate circuits in the infinite algebra of transients recently introduced by Brzozowski and Ésik. A transient is a word consisting of alternating 0 s and 1 s; it represents a changing signal. In the algebra of transients, gates process transients instead of 0 s and 1 s. Simulation in this algebra is capable of counting signal changes and detecting hazards. We study two simulation algorithms: a general one that works with any initial state, and a special one that applies only if...

Gate circuits in the algebra of transients

Janusz Brzozowski, Mihaela Gheorghiu (2010)

RAIRO - Theoretical Informatics and Applications


We study simulation of gate circuits in the infinite algebra of transients recently introduced by Brzozowski and Ésik. A transient is a word consisting of alternating 0s and 1s; it represents a changing signal. In the algebra of transients, gates process transients instead of 0s and 1s. Simulation in this algebra is capable of counting signal changes and detecting hazards. We study two simulation algorithms: a general one that works with any initial state, and a special one that applies only if...

Currently displaying 21 – 40 of 126