In this paper we characterize concurrent alphabets for which every recognizable trace language admits a minimum finite state asynchronous automaton. Furthermore, we consider the equivalence problem for unambiguous regular trace languages, and prove that in some cases it is decidable even if the concurrency relation is not transitive
On the existence of the minimum asynchronous automaton and on decision problems for unambiguous regular trace languages / D. Bruschi, G. Pighizzini, N. Sabadini - In: STACS 88 : 5th Annual Symposium on Theoretical Aspects of Computer Science, Bordeaux, France, February 11-13, 1988 : proceedings / [a cura di] R. Cori, M. Wirsing. - Berlin : Springer, 1988. - ISBN 9783540188346. - pp. 334-345 (( Intervento presentato al 5. convegno Annual Symposium on Theoretical Aspects of Computer Science (STACS) tenutosi a Bordeaux nel 1988 [10.1007/BFb0035857].
On the existence of the minimum asynchronous automaton and on decision problems for unambiguous regular trace languages
D. BruschiPrimo
;G. PighizziniSecondo
;
1988
Abstract
In this paper we characterize concurrent alphabets for which every recognizable trace language admits a minimum finite state asynchronous automaton. Furthermore, we consider the equivalence problem for unambiguous regular trace languages, and prove that in some cases it is decidable even if the concurrency relation is not transitive
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
