On Classes of Program Schemata

Citations Over TimeTop 10% of 1972 papers

Abstract

We define the following classes of program schemata: ${\text{P}} = $ class of schemes using a finite number of simple variables; ${\text{P}}_{\text{A}} = $ class of schemes using simple and subscripted variables (arrays); ${\text{P}}_{{\text{Ae}}} = $ class of schemes in ${\text{P}}_{\text{A}} = $, with the addition of an equality test on subscript values; ${\text{P}}_{\text{R}} = $ class of schemes allowing recursive functions; ${\text{P}}_{\text{L}} = $ class of schemes allowing labels as values; ${\text{P}}_{\text{M}} = $ class of schemes allowing a finite number of special markers as values; ${\text{P}}_{{\text{pds}}} = $ class of schemes using pushdown stores. With these, we can also discuss, for example, ${\text{P}}_{{\text{AM}}} $, the class of schemes allowing arrays, and special markers as values ; and ${\text{P}}_{{\text{AL}}} $, the class of schemes allowing arrays, and labels as values. We argue that ${\text{P}}_{\text{A}}$, ${\text{P}}_{\text{R}}$, and ${\text{P}}_{\text{L}}$ faithfully represent mechanisms of subscripting, recursion, and labels as values, that are present in many “real” programming languages. We show that \[ {\text{P}} < {\text{P}}_{\text{R}} < {\text{P}}_{\text{A}} \equiv {\text{P}}_{{\text{AM}}} \equiv {\text{P}}_{{\text{pdsM}}} \equiv {\text{P}}_{{\text{Ae}}} \equiv {\text{EF}}, \] where EF is Strong’s class of effective functionals, assuming total functions and predicates. The inclusions ${\text{P}} < {\text{P}}_{\text{R}} < {\text{P}}_{\text{A}} $ and equivalences ${\text{P}}_{{\text{AL}}} \equiv {\text{P}}_{{\text{AM}}} \equiv {\text{P}}_{{\text{pdsM}}} \equiv {\text{P}}_{{\text{Ae}}} $ are effective. For example, given a program scheme in ${\text{P}}_{{\text{AM}}} $ we can construct an equivalent one in ${\text{P}}_{{\text{AL}}} $. However, we show that for any scheme in ${\text{P}}_{{\text{AM}}} $ an equivalent ${\text{P}}_{\text{A}} $ scheme exists, but also prove it cannot (in general) be constructed! We conjecture that ${\text{P}}_{{\text{A}}} $, ${\text{P}}_{{\text{AL}}} $, and equivalent classes are indeed “universal.” The above results assume that the uninterpreted functions and predicates are total. We discuss the problems which arise when they are partial. We define the class of multischemes and outline the relationship between the class ${\text{P}}_{{\text{Ae}}} $, multischemes, and Strong’s nondeterministic and deterministic effective functionals.

Related Papers

• → Text data compression ratio as a text attribute for a language-independent text art extraction method(2010)6 cited
• → A Comprehensive Review on Text Classification and Text Mining Techniques Using Spam Dataset Detection(2023)8 cited
• Research on Text Mining Techniques Web-Based(2007)
• → Monitoring of Insects with Public Participation. Layman’s Report(2017)
• → Monitoraggio di Insetti con la Partecipazione Pubblica. Layman’s Report(2017)