An arithmetical hierarchy in propositional dynamic logic

DOI10.1016/0890-5401(89)90033-3MaRDI QIDQ1119628zbMATH OpenOpenAlexFDO

Authors Sorin Istrail

Publication date 1989

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0890-5401(89)90033-3

zbMATH Keywords

alternation of modalitiesarithmetical hierarchyBerman-Paterson theoremexpressive powerKleene-Mostowski hierarchypropositional dynamic logictests

Mathematics Subject Classification ID

Logic in computer science (03B70) General topics in the theory of software (68N01) Abstract data types; algebraic specification (68Q65)

Review text

Let \(\Sigma_ n^{PDL}\) and \(\Pi_ n^{PDL}\) denote the classes of formulas of propositional dynamic logic of the form \(<a_ 1>[a_ 2]<a_ 3>...\{a_ n\}p\) and \([a_ 1]<a_ 2>[a_ 3]...\{a_ n\}p\), respectively, where \(a_ i\) are modality-free programs, p is a modality- free formula and \(\{a_ n\}\) denotes \([a_ n]\) or \(<a_ n>\) depending on parity of n. It is shown that in some models \(\Sigma_ n^{PDL}\) and \(\Pi_ n^{PDL}\)-formulas define exactly the \(\Sigma^ 0_ n\) and \(\Pi^ 0_ n\)-sets of the Kleene-Mostowski hierarchy. It follows that alternation of modalities defines a strict hierarchy of PDL-formulas relative to their expressive power. Another corollary is the Berman- Paterson theorem: PDL with tests is strongly more expressive than PDL without tests. There are some inaccuracies in the proof but they are easily improvable.

Recommendations

• Arithmetical interpretations of dynamic logic
• The logic of arithmetical hierarchy
• Foundations of Information and Knowledge Systems
• Arity and alternation: a proper hierarchy in higher order logics
• A proper hierarchy of propositional sequent calculi
• scientific article; zbMATH DE number 1555183
• An arithmetical view to first-order logic
• Arity hierarchy for temporal logics
• scientific article; zbMATH DE number 7668091
• scientific article; zbMATH DE number 3968565

Cites work

• scientific article; zbMATH DE number 1032009 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• scientific article; zbMATH DE number 3413820 (Why is no real title available?)
• Propositional dynamic logic is weaker without tests
• Propositional dynamic logic of regular programs

Cited in

(4)

• Refined hierarchy of formulas
• scientific article; zbMATH DE number 4174914 (Why is no real title available?)
• SEPARATING AUXILIARY ARITY HIERARCHY OF FIRST-ORDER INCREMENTAL EVALUATION SYSTEMS USING (3K+1)-ary INPUT RELATIONS
• A CHARACTERIZATION OF THE ARITHMETICAL HIERARCHY BY LANGUAGE EQUATIONS

This page was built for publication: An arithmetical hierarchy in propositional dynamic logic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1119628)