You are viewing a javascript disabled version of the site. Please enable Javascript for this site to function properly.
Go to headerGo to navigationGo to searchGo to contentsGo to footer
In content section. Select this link to jump to navigation

Some Properties of Trace Languages

Article type: Research Article

Authors: Rytter, Wojciech

Affiliations: Warsaw University

Abstract: In this paper we present an application of nondeterministic multihead automata to the membership problem for trace languages. Here our result shows that regular and context-free trace languages are not very complicated. On the other hand, we make two simple observations which are the evidence that regular trace languages are very complicated from the algebraic point of view.

Keywords: trace languages, time and space complexity, nondeterministic multihead automata

DOI: 10.3233/FI-1984-7108

Journal: Fundamenta Informaticae, vol. 7, no. 1, pp. 117-127, 1984

Received 13 January 1983
|
Published: 1 January 1984
Price: EUR 27.50
Show more