Equations between Regular Terms and an Application to Process Logic
Decidability of theories and sets of sentences (03B25) Modal logic (including the logic of norms) (03B45) Automata and formal grammars in connection with logical questions (03D05) Formal languages and automata (68Q45) Specification and verification (program logics, model checking, etc.) (68Q60) Abstract data types; algebraic specification (68Q65)
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.
- Process logic with regular formulas
- Process logic: Expressiveness, decidability, completeness
- Language equations
- Compositional reasoning using intervals and time reversal
- Computational completeness of equations over sets of natural numbers
- A decision procedure for propositional projection temporal logic with infinite models
- A Hierarchical Completeness Proof for Propositional Interval Temporal Logic with Finite Time
- scientific article; zbMATH DE number 3976998 (Why is no real title available?)
- scientific article; zbMATH DE number 3986629 (Why is no real title available?)
- scientific article; zbMATH DE number 35404 (Why is no real title available?)
- Theoretical Aspects of Computing – ICTAC 2005
- A Road Map of Interval Temporal Logics and Duration Calculi
- A Road Map of Interval Temporal Logics and Duration Calculi
- Decision problems for systems of language equations and inequations
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)