Deciding Properties of Nonregular Programs

Résumé du livre

Abstract: "We consider extensions of propositional dynamic logic (PDL) with nonregular programs. We provide three general decidability results, showing that for each language L in some class, PDL, with L added to the set of regular programs as a new program, is decidable. The first class contains context-free languages accepted by pushdown automata that act only on the basis of their input symbol, except to decide whether they reject or continue. The second class contains all languages (even non- context-free) accepted by deterministic stack machines, but which have a unique new symbol prefixing each word