Equations between Regular Terms and an Application to Process Logic (Q3713595)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3943016
Language Label Description Also known as
default for all languages
No label defined
    English
    Equations between Regular Terms and an Application to Process Logic
    scientific article; zbMATH DE number 3943016

      Statements

      Equations between Regular Terms and an Application to Process Logic (English)
      0 references
      0 references
      0 references
      0 references
      0 references
      1985
      0 references
      logic of programs
      0 references
      validity problem
      0 references
      regular expressions
      0 references
      satisfiability problem
      0 references
      context-free language
      0 references
      Process logic combines the features of both, propositional dynamic logic (PDL) and temporal logic (TL). So it admits us to speak directly, both on the input-output as well as on run-time properties of programs. Let us fix two finite alphabets \(P_ 1,...,P_ n\) of basic program letters and \(a_ 1,...,a_ m\) of atomic formula letters. If P, P' are programs (e.g., basic programs), so are P;P', \(P\cup P'\), \(P^*\). If A, B are formulae, so are \(\neg A\), \(A\vee B\). If additionally P is a program, then \(<P>A\) is a formula. The above definitions give us PDL. We also consider three types of formulas: if A, B are formulae, so are \(fA\), A\(sufB\), A\(chopB.\) A model of process logic is a triple (W,r,R) where W is a set of states, while r and R are assignments of paths (path \(= finite/\inf inite\) sequence of states) to, respectively, basic formulae and programs. To any atomic objects a set of paths is assigned. Having a model, we define the validity of formulae as follows: Let p is a path. Then \(p\vDash a_ i\) iff \(p\in r(a_ i)\). We standardly extend R to programs. Then \(p\vDash <P>A\) iff there exists q in R(P) such that pq is defined and \(pq\vDash A\) (in particular, p have to be finite). Logical connectives are defined standardly. \(p\vDash fA\) iff the first state of p, say q, satisfies A, i.e. \(q\vDash A\). \(p\vDash AsufB\) iff there exists q suffix p such that \(q\vDash B\), and if both, t is a suffix of p and q is a suffix of t, then \(t\vDash A\). Finally, \(p\vDash AchopB\) iff there exist q, t such that \(p=qt\) and \(q\vDash A\) and \(t\vDash B\). A model will be called local iff, for any path p, \(p\vDash a\Leftrightarrow p\vDash fa\) for all basic predicates a. D. Kozen's theorem is that the validity problem for formulae of process logic on all logic models is decidable (though non- elementary). The paper's main result is that this problem on all models becomes already undecidable. A number of related assertions are also proved. The proof is based on investigations of regular equations. Let S be a finite alphabet and let \(X=\{X_ 1,...,X_ j,...\}\) be the set of ''variables''. Next, let t, t' be two regular expressions over \(S\cup X\). Then, \(t=t'\) is called a regular equation. The equation is called satisfiable over S iff there exist languages \(L_ 1,...,L_ j,..\). such that the substitution of them instead of \(X_ 1,X_ 2,..\). resp., makes the equality \(t=t'\) true. The authors prove the following assertions: The satisfiability problem even for *-free regular equations is undecidable. Given a context-free language L over S, there exists a finite, satisfiable systemof *-free regular equations such that for any alphabet G extending S,and for any solution \(L_ 1,L_ 2,..\). of the system over G, \(L_ 1\) is just L. If a system of regular equations has a unique solution (to an approximation of the variables presented in the system) then this solution is recursive.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references