A Boolean Matrix Method for the Computation of Linear Precedence Functions,

reportActive / Technical Report | Accession Number: AD0747036 | Need Help?

Abstract:

A modified version of Bells Boolean matrix method for the computation of linear precedence functions associated with a conflict-free matrix of precedence relations is given. This new algorithm not only detects when the precedence functions do not exist, but also provides an indication of why they do not exist, so that corrective action can be taken is possible. Necessary and sufficient conditions for the existence of precedence functions are given. The use of Boolean matrices to prove the existence of precedence functions associated with classes of conflict-free grammars is illustrated through an example. Author

Author(s):
Martin, David F.
Author Organization(s):
CALIFORNIA UNIV LOS ANGELES SCHOOL OF ENGINEERING AND APPLIED SCIENCE
Supplementary Note:
Sponsored in part by Atomic Energy Commission, Contract AT(11-1)-Gen-10.
Pagination:
0027

Security Markings

DOCUMENT & CONTEXTUAL SUMMARY

Distribution:
Approved For Public Release

RECORD

Collection: TR
Identifying Numbers
Report Number(s):
AFOSR-TR-72-1503
Contract/Grant Number(s):
N00014-69-A-0200-4027, AF-AFOSR-1915-70
Project Number(s):
NR-048-129, AF-9769
Monitor Series:
TR-72-1503
 Subject Terms
Communities of Interest:
No COI(s) Identified
Descriptor(s):
*PROGRAMMING LANGUAGES, CONTEXT FREE GRAMMARS, SYNTAX, MATHEMATICAL LOGIC, ALGEBRA, MATRICES(MATHEMATICS), SPECIAL FUNCTIONS(MATHEMATICS)
Field(s)/Group(s):
Linguistics, Computer Programming and Software
Keyword(s):
BOOLEAN MATRICES, SYNTACTIC ANALYSIS
Report Date:
1972 Jun 01