Trace languages have been introduced in order to describe the behaviour of concurrent systems in the same way as usual formal languages do for sequential system. They can be defined as subsets of a free partially commutative monoid and a theory of trace languages can be developed, generalizing the usual formal languages theory. In this paper, the time complexity of membership problems for regular and context-free trace languages is investigated. It is proved that the membership problem for context free trace languages can be solved in time O(BM(nα)), where α is the dimension of the greatest clique of the concurrency relation C and BM(n) is the time required for multiplying two arbitrary n × n boolean matrices. For regular trace languages, our method gives an algorithm which requires O(nα) time. Finally, the uniform membership problem is shown to be NP-complete. © 1989.
Bertoni, A., Mauri, G., Sabadini, N. (1989). Membership problems for regular and context free trace languages. INFORMATION AND COMPUTATION, 82(2), 135-150 [10.1016/0890-5401(89)90051-5].
Membership problems for regular and context free trace languages
MAURI, GIANCARLO;
1989
Abstract
Trace languages have been introduced in order to describe the behaviour of concurrent systems in the same way as usual formal languages do for sequential system. They can be defined as subsets of a free partially commutative monoid and a theory of trace languages can be developed, generalizing the usual formal languages theory. In this paper, the time complexity of membership problems for regular and context-free trace languages is investigated. It is proved that the membership problem for context free trace languages can be solved in time O(BM(nα)), where α is the dimension of the greatest clique of the concurrency relation C and BM(n) is the time required for multiplying two arbitrary n × n boolean matrices. For regular trace languages, our method gives an algorithm which requires O(nα) time. Finally, the uniform membership problem is shown to be NP-complete. © 1989.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.