Safety and liveness of -context-free languages

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Formal languages and automata (68Q45) Distributed algorithms (68W15)

Review text

Let \(\Sigma\) be an alphabet. An \(\omega\)-language L over \(\Sigma\) is called safe if the following condition is satisfied for every \(\omega\)- word x over \(\Sigma\) : if every prefix of x can be extended to an \(\omega\)-word in L then \(x\in L\). The \(\omega\)-language L is said to be live if every word can be extended to an \(\omega\)-word in L. These definitions are motivated by considerations concerning concurrent systems. It is known that every \(\omega\)-regular language can be represented as the intersection of a safe \(\omega\)-regular language with a live \(\omega\)-regular language \textit{B. Alpern}, and \textit{F. B. Schneider} [Distrib. Comput. 2, 117-126 (1987; Zbl 0641.68039)]. The central issue of this paper is to investigate a possible generalization of this result to \(\omega\)-context-free languages. Some sufficient conditions are provided which hold true in quite a few interesting cases; however, an example is also provided which shows that a full generalization is not possible.

Recommendations

Cites work

Cited in

(2)

This page was built for publication: Safety and liveness of \(\omega\)-context-free languages

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