On the existence of the minimum asynchronous automaton and on decision problems for unambiguous regular trace languages. (English) Zbl 0644.68099
STACS 88, Theoretical aspects of computer science, Proc. 5th Annu. Symp., Bordeaux/France 1988, Lect. Notes Comput. Sci. 294, 334-345 (1988).
Summary: [For the entire collection see Zbl 0635.00015.]
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.
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.
