On the Complexity of the Evaluation of Transient Extensions of Boolean Functions

Autor: Yuli Ye, Janusz A. Brzozowski, Baiyu Li
Jazyk: angličtina
Rok vydání: 2010
Předmět:
FOS: Computer and information sciences
Hazard (logic)
Discrete Mathematics (cs.DM)
Computer science
0102 computer and information sciences
02 engineering and technology
Hardware_PERFORMANCEANDRELIABILITY
Computational Complexity (cs.CC)
computer.software_genre
Multi valued
01 natural sciences
lcsh:QA75.5-76.95
Computer Science (miscellaneous)
0202 electrical engineering
electronic engineering
information engineering

Transient (computer programming)
Algebra over a field
Boolean function
Programming language
lcsh:Mathematics
020207 software engineering
16. Peace & justice
lcsh:QA1-939
Algebra
Computer Science - Computational Complexity
010201 computation theory & mathematics
020201 artificial intelligence & image processing
lcsh:Electronic computers. Computer science
Scientific publishing
computer
Computer Science - Discrete Mathematics
Zdroj: Electronic Proceedings in Theoretical Computer Science, Vol 31, Iss Proc. DCFS 2010, Pp 27-37 (2010)
ISSN: 2075-2180
Popis: Transient algebra is a multi-valued algebra for hazard detection in gate circuits. Sequences of alternating 0's and 1's, called transients, represent signal values, and gates are modeled by extensions of boolean functions to transients. Formulas for computing the output transient of a gate from the input transients are known for NOT, AND, OR} and XOR gates and their complements, but, in general, even the problem of deciding whether the length of the output transient exceeds a given bound is NP-complete. We propose a method of evaluating extensions of general boolean functions. We introduce and study a class of functions with the following property: Instead of evaluating an extension of a boolean function on a given set of transients, it is possible to get the same value by using transients derived from the given ones, but having length at most 3. We prove that all functions of three variables, as well as certain other functions, have this property, and can be efficiently evaluated.
Comment: In Proceedings DCFS 2010, arXiv:1008.1270
Databáze: OpenAIRE