Characterizations of the decidability of some problems for regular trace languages |
| |
| Authors: | IJ J Aalbersberg H J Hoogeboom |
| |
| Affiliation: | (1) Department of Computer Science, Leiden University, P.O. Box 9512, 2300 RA Leiden, The Netherlands;(2) Present address: Philips Research Laboratories, P.O. Box 80.000, 5600 JA Eindhoven, The Netherlands |
| |
| Abstract: | The decidability of the equivalence problem and the disjointness problem for regular trace languages is considered. By describing the structure of the independence relations involved, precise characterizations are given of those concurrency alphabets for which these problems are decidable. In fact, the first problem is decidable if and only if the independence relation is transitive, while the second problem is decidable if and only if the independence relation is a so-called transitive forest. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
