Characterizations of the decidability of some problems for regular trace languages

IJ J. Aalbersberg; H. J. Hoogeboom

doi:10.1007/BF02088289

Characterizations of the decidability of some problems for regular trace languages

IJ J. Aalbersberg, H. J. Hoogeboom

Research output: Contribution to journal › Article › peer-review

42 Scopus citations

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.

Original language	English
Pages (from-to)	1-19
Number of pages	19
Journal	Mathematical Systems Theory
Volume	22
Issue number	1
DOIs	https://doi.org/10.1007/BF02088289
State	Published - Dec 1989
Externally published	Yes

Access to Document

10.1007/BF02088289

Cite this

@article{7a6b205f682645f7957400e776bb67fd,

title = "Characterizations of the decidability of some problems for regular trace languages",

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.",

author = "Aalbersberg, {IJ J.} and Hoogeboom, {H. J.}",

year = "1989",

month = dec,

doi = "10.1007/BF02088289",

language = "Ingl{\'e}s",

volume = "22",

pages = "1--19",

journal = "Mathematical Systems Theory",

issn = "0025-5661",

publisher = "Springer New York",

number = "1",

}

TY - JOUR

T1 - Characterizations of the decidability of some problems for regular trace languages

AU - Aalbersberg, IJ J.

AU - Hoogeboom, H. J.

PY - 1989/12

Y1 - 1989/12

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0002457698&partnerID=8YFLogxK

U2 - 10.1007/BF02088289

DO - 10.1007/BF02088289

M3 - Artículo

AN - SCOPUS:0002457698

SN - 0025-5661

VL - 22

SP - 1

EP - 19

JO - Mathematical Systems Theory

JF - Mathematical Systems Theory

IS - 1

ER -

Characterizations of the decidability of some problems for regular trace languages

Abstract

Access to Document

Other files and links

Fingerprint

Cite this