Irredundant Algorithms for Traversing Directed Graphs: The Deterministic Case

Problems of testing program systems modeled by deterministic finite automata are considered. The necessary (and, sometimes, sufficient) component of such testing is a traversal of the graph of the automaton state transitions. The main attention is given to the so-called irredundant traversal algorit...

Full description

Saved in:
Bibliographic Details
Published in:Programming and computer software 2003-09, Vol.29 (5), p.245-258
Main Authors: Bourdonov, I. B, Kossatchev, A. S, Kuliamin, V. V
Format: Article
Language:English
Subjects:
Algorithms
Graph theory
Graphs
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Problems of testing program systems modeled by deterministic finite automata are considered. The necessary (and, sometimes, sufficient) component of such testing is a traversal of the graph of the automaton state transitions. The main attention is given to the so-called irredundant traversal algorithms (algorithms for traversing unknown graphs, or on-line algorithms), which do not require an a priori knowledge of the total graph structure.
ISSN:0361-7688
1608-3261
DOI:10.1023/A:1025733107700