J. Sziray

6603287726

Publications - 15

Computational complexity in test-generation algorithms

J. Sziray

Publication Name: Proceedings of 2014 9th International Design and Test Symposium Idt 2014

Publication Date: 2015-02-10

Volume: Unknown

Issue: Unknown

Page Range: 124-129

Description:

The paper is concerned with analyzing and comparing two exact algorithms from the viewpoint of computational complexity. Both serve for calculating fault-detection tests of digital circuits. The first one is the so-called composite justification, and the second is the D-algorithm. The analysis will be performed on combinational logic networks at the gate level. Here single and multiple stuck-at logic faults will be considered. As a result, it is pointed out that the composite justification requires significantly less computational step than the D-algorithm and its modifications. The difference manifests itself especially in terms of multiple faults. From this fact it has been conjectured that possibly no other algorithm is available in this field with fewer computational steps. If the claim holds, then it follows directly that the test-calculation problem is of exponential time, and so are all the other NP-complete problems. It may also be expected that the minimal complexity of composite justification applies to any modeling level (either low or high) of digital circuits, just like the exponential-time solution.

Open Access: Yes

DOI: 10.1109/IDT.2014.7038599

Test generation for short-circuit faults in digital circuits

J. Sziray

Publication Name: Studies in Computational Intelligence

Publication Date: 2014-02-03

Volume: 530

Issue: Unknown

Page Range: 313-319

Description:

In the first part, the paper presents a test calculation principlewhich serves for producing tests of logic faults in digital circuits. The name of the principle is composite justification. The considered faultmodel includes stuck-at-0/1 logic faults. Both single and multiple faults are included. In this paper only combinational logic is taken into consideration. The computations are performed at the gate level. The calculation principle is comparatively simple. It is based only on successive linevalue justification, and it yields an opportunity to be realized by an efficient computer program. The first part serves for presenting the basic principle which is used in the second part of the paper. The second part deals with another fault class, namely, short-circuit or bridging faults. A short circuit is an erroneous galvanic connection between two circuit lines. Here, a new algorithm is presented for generating tests, where the composite justification is extended to handle this type of faults, as well. © Springer International Publishing Switzerland 2014.

Open Access: Yes

DOI: 10.1007/978-3-319-03206-1_21

Evaluation of boolean graphs in software testing

J. Sziray

Publication Name: Iccc 2013 IEEE 9th International Conference on Computational Cybernetics Proceedings

Publication Date: 2013-11-07

Volume: Unknown

Issue: Unknown

Page Range: 225-230

Description:

The paper presents an algorithm for producing the logic conditions that result in the effects of a cause-effect graph belonging to a given software. These conditions yield the test cases of the software. The algorithm applies a three-valued Boolean algebra, and is based on the successive justification of logic values in a combinational network, where the primary inputs are the causes, and the primary outputs are the effects. The computations are performed by traversing a decision tree, where backtracking is required if a decision leads to a logic contradiction. The main advantage of the algorithm is that it reduces the number of decisions to a great extent by using don't care values in the process. The calculation principle is comparatively simple. It is based only on successive line-value justification, and it yields an opportunity to be realized by an efficient computer program. The logic model introduced in the paper is completely general, in that it is applicable to any kind of cause-effect graphs, without any constraint. © 2013 IEEE.

Open Access: Yes

DOI: 10.1109/ICCCyb.2013.6617593

Test calculation for logic and short-circuit faults in digital circuits

J. Sziray

Publication Name: Ines 2012 IEEE 16th International Conference on Intelligent Engineering Systems Proceedings

Publication Date: 2012-10-01

Volume: Unknown

Issue: Unknown

Page Range: 121-124

Description:

In the first part, the paper presents a test calculation principle which serves for producing tests of logic faults in digital circuits. The name of the principle is composite justification. The considered fault model includes stuck-at-0/1 logic faults. Both single and multiple faults are included. In this paper only combinational logic is taken into consideration. The computations are performed at the gate level. In the second part of the paper, the composite justification is extended to an other fault class, namely, short-circuit faults. A short circuit is an erroneous galvanic coupling between two circuit lines. The calculation principle is comparatively simple. It is based only on successive line-value justification, and it yields an opportunity to be realized by an efficient computer program. © 2012 IEEE.

Open Access: Yes

DOI: 10.1109/INES.2012.6249815

Test generation and computational complexity

J. Sziray

Publication Name: Proceedings of IEEE Pacific Rim International Symposium on Dependable Computing Prdc

Publication Date: 2011-12-01

Volume: Unknown

Issue: Unknown

Page Range: 286-287

Description:

The paper is concerned with analyzing and comparing two exact algorithms from the viewpoint of computational complexity. They are: composite justification and the D-algorithm. Both serve for calculating fault-detection tests of digital circuits. As a result, it is pointed out that the composite justification requires significantly less computational step than the D-algorithm. From this fact it has been conjectured that possibly no other algorithm is available in this field with fewer computational steps. If the claim holds, then it follows directly that the test-generation problem is of exponential time, and so are all the other NP-complete problems in the field of computation theory. © 2011 IEEE.

Open Access: Yes

DOI: 10.1109/PRDC.2011.40

A test model for hardware and software

J. Sziray

Publication Name: Proceedings of IEEE Pacific Rim International Symposium on Dependable Computing Prdc

Publication Date: 2011-12-01

Volume: Unknown

Issue: Unknown

Page Range: 292-293

Description:

The paper presents a unified test model which is a mapping scheme for describing the one-to-one correspondence between the input and output domains of a given hardware or software system. Here the test inputs and the fault classes are also involved. The test model incorporates both the verification and the validation schemes for the hardware and software. © 2011 IEEE.

Open Access: Yes

DOI: 10.1109/PRDC.2011.41

Computational complexity in logic testing

J. Sziray

Publication Name: Ines 2010 14th International Conference on Intelligent Engineering Systems Proceedings

Publication Date: 2010-07-26

Volume: Unknown

Issue: Unknown

Page Range: 97-102

Description:

The paper is concerned with analyzing and comparing two exact algorithms from the viewpoint of computational complexity. Both are for calculating fault-detection tests for digital circuits. The first one is the so-called composite justification, and the second is the D-algorithm. The analysis will be performed on combinational logic networks at the gate level. Here single and multiple stuck-at logic faults will be considered. As a result, it is pointed out that the composite justification requires significantly less computational step than the D-algorithm and its modifications. From this fact it has been concluded that possibly no other algorithm is available in this field with fewer computational steps. If it holds, then it follows directly that the test calculation problem is of exponential-time, and so are any other NP-complete problems. © 2010 IEEE.

Open Access: Yes

DOI: 10.1109/INES.2010.5483865

Switch-level test calculation for CMOS circuits

J. Sziray

Publication Name: Proceedings International Workshop on Microprocessor Test and Verification

Publication Date: 2009-12-01

Volume: Unknown

Issue: Unknown

Page Range: 41-48

Description:

The paper presents a test calculation principle which serves for producing tests of switch-level logic faults in CMOS digital circuits. The considered fault model includes stuck-at-0/1 logic faults on the connecting control lines, as well as switch faults in the transistors. Both single and multiple faults are included. The transistor faults manifest themselves in stuck open (open circuit) and stuck short (short circuit) behavior. In this paper only combinational logic is taken into consideration. The computations are performed at the transistor level directly, i. e., by using the original transistor schematic solely, without any logic conversion. The calculation principle is comparatively simple. It is based only on successive line-value justification, and it yields an opportunity to be realized by an efficient computer program. © 2009 IEEE.

Open Access: Yes

DOI: 10.1109/MTV.2009.24

Transistor-level test calculation for CMOS circuits

J. Sziray

Publication Name: Iccc 2009 IEEE 7th International Conference on Computational Cybernetics

Publication Date: 2009-12-01

Volume: Unknown

Issue: Unknown

Page Range: 85-90

Description:

The paper presents a test calculation principle which serves for producing tests of transistor-level faults in CMOS digital circuits. The considered fault model includes stuck-at-0/1 logic faults on the connecting control lines, as well as switch faults in the transistors. Both single and multiple faults are included. The transistor faults manifest themselves in stuck open (open circuit) and stuck short (short circuit) behavior. In this paper only combinational logic circuits are taken into consideration. The calculation principle is comparatively simple. It is based only on successive line-value justification, and it yields an opportunity to be realized by an efficient computer program. ©2009IEEE.

Open Access: Yes

DOI: 10.1109/ICCCYB.2009.5393957

A computational model for inference chains in expert systems

J. Sziray

Publication Name: Proceedings 2009 International Conference on Intelligent Engineering Systems Ines 2009

Publication Date: 2009-11-02

Volume: Unknown

Issue: Unknown

Page Range: 183-188

Description:

This paper deals with the calculations performed in the reasoning process of rule-based expert systems, where inference chains are applied. It presents a logic model for representing the rules and the rule base of a given system. Also, the fact base of the same expert system is involved in the logic model. The proposed equivalent representation manifests itself in a logic network. After that, a four-valued logic algebra is introduced. This algebra is used for the calculations where forward chaining is carried out. Next, the notion of line-value justification is described. This operation is applied in the backward chaining process, also on the base of the previously introduced four-valued logic. The paper describes two exact algorithms which serve for the forward and backward chaining processes. These algorithms make it possible to be implemented by a computer program, resulting in an efficient inference engine of an expert system. The achieved result enhances the reliability and usability of the intelligent software systems which is extremely important in embedded environments. ©2009 IEEE.

Open Access: Yes

DOI: 10.1109/INES.2009.4924759

Test calculation for logic and delay faults in digital circuits

J. Sziray

Publication Name: Proceedings International Workshop on Microprocessor Test and Verification

Publication Date: 2007-12-01

Volume: Unknown

Issue: Unknown

Page Range: 20-29

Description:

The paper presents a test calculation principle which serves for producing tests for logic and delay faults in digital circuits. Switch-level logic faults in CMOS circuits are also considered. The delay faults manifest themselves in the incorrect timing behavior of some logic elements within the network. Both single and multiple faults are included. The proposed method handles multi-valued logic, where the number of logic values is unlimited. The level of circuit modeling is also allowed to vary in a wide range: switch level, gate level, functional level, register-transfer level are equally allowed. Both combinational and sequential circuits are considered. The principle is comparatively simple, and it yields an opportunity to be realized by an efficient computer program. © 2006 IEEE.

Open Access: Yes

DOI: 10.1109/MTV.2006.21

A logic model for inference chains in expert systems

J. Sziray

Publication Name: International Conference on Artificial Intelligence and Pattern Recognition 2007 Aipr 2007

Publication Date: 2007-12-01

Volume: Unknown

Issue: Unknown

Page Range: 243-248

Description:

This paper deals with the calculations performed in the reasoning process of rule-based expert systems, where inference chains are applied. It presents a logic model for representing the rules and the rule base of a given system. Also, the fact base of the same expert system is involved in the logic model. The proposed equivalent representation manifests itself in a logic network. After that, a four-valued logic algebra is introduced. This algebra is used for the calculations where forward chaining is carried out. Next, the notion of line-value justification is described. This operation is applied in the backward chaining process, also on the base of the previously introduced four-valued logic. The paper describes two exact algorithms which serve for the forward and backward chaining processes. These algorithms make it possible to be implemented by a computer program, resulting in an efficient inference engine of an expert system. The achieved result enhances the reliability and usability of the intelligent software systems which is extremely important in embedded environments.

Open Access: Yes

DOI: DOI not available

Logic testing of CMOS structures

J. Sziray

Publication Name: Iccc 2004 Second IEEE International Conference on Computational Cybernetics Proceedings

Publication Date: 2004-12-01

Volume: Unknown

Issue: Unknown

Page Range: 59-64

Description:

The paper presents a test calculation principle which serves for producing tests of switch-level logic faults in CMOS digital circuits. The considered fault model includes stuck-at-0/1 logic faults on the connecting lines, as well as switch faults in the transistors. Both single and multiple faults are included. The transistor faults manifest themselves in stuck open (open circuit) and stuck short (short circuit) behavior. In this paper only combinational logic circuits are taken into consideration. The calculation principle is comparatively simple. It is based only on successive line-value justification, and it yields an opportunity to be realized by an efficient computer program. ©2004 IEEE.

Open Access: Yes

DOI: DOI not available

A Test Model for Hardware and Software Systems

J. Sziray

Publication Name: Journal of Advanced Computational Intelligence and Intelligent Informatics

Publication Date: 2004-09-01

Volume: 8

Issue: 5

Page Range: 523-529

Description:

The paper is concerned with the general aspects of testing complex hardware and software systems. First a mapping scheme as a test model is presented for an arbitrary given system. This scheme serves for describing the one-to-one correspondence between the input and output domains of the system, where the test inputs and fault classes are also involved. The presented test model incorporates both the verification and the validation schemes for hardware and software. The significance of the model is that it alleviates the clear differentiation between verification and validation tests, which is important and useful in the process of test design and evaluation. On the other hand, this model provides a clear overview on the various purpose test sets, which helps in organizing and applying these sets. The second part of the paper examines the case when the hardware and software are designed by using formal specification. Here the consequences and problems of formal methods, and their impacts on verification and validation are discussed.

Open Access: Yes

DOI: 10.20965/jaciii.2004.p0523

Comprehensive method for the test calculation of complex digital circuits

J. Sziray

Publication Name: Periodica Polytechnica Electrical Engineering

Publication Date: 1997-01-01

Volume: 41

Issue: 4

Page Range: 251-257

Description:

The paper presents a general test calculation principle which serves for producing tests for a wide range of possible faults: stuck-at-constant logic level (single, multiple), bridging (single), as well as behavioral (functional, single) faults. The proposed method handles multi-valued logic, where the number of logic values is unlimited. The level of circuit modeling is also allowed to vary in a wide range: switch level, gate level, functional level, etc. are equally allowed. Both combinational and sequential circuits are considered. The principle is comparatively simple, and it yields an opportunity to be realized by an efficient computer program.

Open Access: Yes

DOI: DOI not available