Given a recognizable trace language T there always exists a minimum (up to isomorphism) monoid automation which recognizes T. In this paper we consider finite state asynchronous automata, introduced by W. Zielonka (''Notes on Finite Asynchronous Automata,'' Technical Report, Institute of Mathematics, Warsaw Technical University, 1984) and we show that this result cannot be extended to this model. More precisely, we exhibit a recognizable trace language which does not admit a unique minimum asynchronous automaton. This result solves an open problem posed by Zielonka. We further prove that every recognizable trace language defined on a concurrent alphabet with a transitive dependency relation admits a unique minimum asynchronous automation. In the second part of this paper we investigate the equivalence problem for regular trace languages. This problem has been investigated by many authors: in particular, Aalbersberg and Hoogeboom (1987) have shown that the equivalence problem for regular trace languages defined over a concurrent alphabet [SIGMA, C] is decidable if and only if the concurrency relation C is transitive. We show that this result does not hold when we restrict our attention to unambiguous regular trace languages we exhibit a concurrent alphabet [SIGMA', C'] with a non transitive concurrency relation such that the equivalence problem for unambiguous regular trace languages on [SIGMA', C'] can be decided in polynomial time. Further we show that the problem of distinguishing whether or not a regular expression on a concurrent alphabet [SIGMA, C] defines an unambiguous regular trace language is undecidable. (C) 1994 Academic Press, Inc.

On the existence of minimum asynchronous automata and on the equivalence problem for unambiguous regular trace languages / D. Bruschi, G. Pighizzini, N. Sabadini. - In: INFORMATION AND COMPUTATION. - ISSN 0890-5401. - 108:2(1994), pp. 262-285.

On the existence of minimum asynchronous automata and on the equivalence problem for unambiguous regular trace languages

D. Bruschi
Primo
;
G. Pighizzini
Secondo
;
1994

Abstract

Given a recognizable trace language T there always exists a minimum (up to isomorphism) monoid automation which recognizes T. In this paper we consider finite state asynchronous automata, introduced by W. Zielonka (''Notes on Finite Asynchronous Automata,'' Technical Report, Institute of Mathematics, Warsaw Technical University, 1984) and we show that this result cannot be extended to this model. More precisely, we exhibit a recognizable trace language which does not admit a unique minimum asynchronous automaton. This result solves an open problem posed by Zielonka. We further prove that every recognizable trace language defined on a concurrent alphabet with a transitive dependency relation admits a unique minimum asynchronous automation. In the second part of this paper we investigate the equivalence problem for regular trace languages. This problem has been investigated by many authors: in particular, Aalbersberg and Hoogeboom (1987) have shown that the equivalence problem for regular trace languages defined over a concurrent alphabet [SIGMA, C] is decidable if and only if the concurrency relation C is transitive. We show that this result does not hold when we restrict our attention to unambiguous regular trace languages we exhibit a concurrent alphabet [SIGMA', C'] with a non transitive concurrency relation such that the equivalence problem for unambiguous regular trace languages on [SIGMA', C'] can be decided in polynomial time. Further we show that the problem of distinguishing whether or not a regular expression on a concurrent alphabet [SIGMA, C] defines an unambiguous regular trace language is undecidable. (C) 1994 Academic Press, Inc.
Settore INF/01 - Informatica
1994
Article (author)
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/187656
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 5
social impact