Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

AN EFFICIENT ALGORITHM FOR CONTAINMENT PROBLEM

IP.com Disclosure Number: IPCOM000128470D
Original Publication Date: 1984-Jan-01
Included in the Prior Art Database: 2005-Sep-16
Document File: 7 page(s) / 101K

Publishing Venue

Software Patent Institute

Related People

Rajlich, Vaclav: AUTHOR [+3]

Abstract

Containment problems are important problems, because verification of specifications can be formally stated as a containment problem. The paper introduces a necessary and sufficient condition for containment of two languages. Disjoint-future automata are defined, and a one-pass algorithm for the containment problem is introduced.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 20% of the total text.

Page 1 of 7

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

AN EFFICIENT ALGORITHM FOR CONTAINMENT PROBLEM

Vaclav Rajlich

CRL-TR-9-84

THE UNIVERSITY OF MICHIGAN COMPUTING RESEARCH LABORATORY1

JANUARY 1984

NOVEMBER 1984 (Revision 1)

Room 1079, East Engineering Building

Ann Arbor, Michigan 48109
USA
Tel: (313) 763 An Efficient Algorithm for Containment Problem Vaclav Rajlich
Department of Computer and Communication Science University of Michigan
Ann Arbor, M1 48109

Abstract

Containment problems are important problems, because verification of specifications can be formally stated as a containment problem. The paper introduces a necessary and sufficient condition for containment of two languages. Disjoint-future automata are defined, and a one- pass algorithm for the containment problem is introduced.

[ Chapter ] 1. INTRODUCTION

The containment problems can be characterized in the following way: Let P and Q be automata, and L(P) and L(Q) be languages they accept, respectively, then does L(P) ⊂ L(Q)? There is considerable literature which deals with containment problems; for overview, see 23

It should be noted that the containment problems play a very important role in the context of the so-called specifications and top-down program design. In that situation, the behavior of data structures, subsystems, modules, etc. is specified by a specification language. The language specifies what is a correct sequence of data structure access, or what is a correct sequence of procedure calls, etc. This is particularly important in top- down program design,45 where the only

1 Any opinions, findings, and conclusions or recommendations expresseed in this publication are those of the author.

2 [ 1 ] Hopcroft, J. E., Ullman, J. D., Introduction to Automata Theory, Languages, and Computation, Addison- Wesley, Reading, MA.

3 [ 3 ] Hunt, H. B. III., Rosenkrantz, D. J., Szymanski, T. G., "On the equivalence, containment, and covering problems for the regular and context free languages," J. of Computer and System Sci. Vol.12, (1976), pp.222-258.

4 [ 5 ] Rajlich, V., "Stepwise refinement revisited," to be published in The Journal of Systems and Software, Vol.4, No.4, (1984).

5 [ 6 ] Riddle, W. E., Wileden, J. C., Sayler, J. H., Segal, A. R., Stavely, A. M., "Behavior modeling during software design," IEEE Trans. Software Engineering, Vol. SE-4, 283- 292.

University of Michigan Computing Research Laboratory Page 1 Jan 01, 1984

Page 2 of 7

AN EFFICIENT ALGORITHM FOR CONTAINMENT PROBLEM

thing known about lower modules may be the specifications, i.e. the sequencing of the procedure calls. During the design verification, the specifications may be the only available aid. For an overview of regular languages as specification languages, see 67

To prove that a program satisfies the specifications means to prove that the set of all traces of that program is a subset of the specification language, i.e. it means to solve the containment problem. However in their...