\alpha\) (after) are compared. The three new ones are throughout (during) - \(\alpha\) holds in any (some) state in every computation of P, and preserves - if \(\alpha\) holds in some state in a computation of P, it holds in all subsequent states. While in the deterministic case, none of these increases the power of the corresponding logic, in the nondeterministic case this is no more true for during. This operator can be however expressed by means of array assignments or rich tests. At least one of the proofs of the paper is not customary for the dynamic logic area applying the theory of computational complexity: The assumption that a tree scheme without during can recognize the set of bit strings with even number of 1's contradicts a result concerning Boolean circuit complexity.
- Definability by programs in first-order structures
- Definability in dynamic logic
- Equivalences among logics of programs
- Expressing program looping in regular dynamic logic
- scientific article; zbMATH DE number 3848600 (Why is no real title available?)
- scientific article; zbMATH DE number 3968564 (Why is no real title available?)
- scientific article; zbMATH DE number 3675301 (Why is no real title available?)
- Parity, circuits, and the polynomial-time hierarchy
- Some relationships between logics of programs and complexity theory
This page was built for publication: ``During cannot be expressed by ``after
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1085154)
