Equations between Regular Terms and an Application to Process Logic

From MaRDI portal





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 \(

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

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.











This page was built for publication: Equations between Regular Terms and an Application to Process Logic

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