Alternation and Bounded Concurrency Are Reverse Equivalent

Numerous models of concurrency have been considered in the framework of automata. Among the more interesting concurrency models are classical nondeterminism and pure concurrency, the two facets of alternation, and the bounded concurrency model. Bounded concurrency was previously considered to be sim...

Full description

Saved in:
Bibliographic Details
Published in:Information and computation 1999-08, Vol.152 (2), p.173-187
Main Authors: Hirst, Tirza, Lewenstein, Moshe
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
alternation automata
Applied sciences
Automata. Abstract machines. Turing machines
bounded concurrency
Computer science
control theory
systems
Exact sciences and technology
finite automata
nondeterminism
succinctness
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Numerous models of concurrency have been considered in the framework of automata. Among the more interesting concurrency models are classical nondeterminism and pure concurrency, the two facets of alternation, and the bounded concurrency model. Bounded concurrency was previously considered to be similar to nondeterminism and pure concurrency in the sense of the succinctness of automata augmented with these features. In this paper we show that, when viewed more broadly, the power (of succinctness) of bounded concurrency is in fact most similar to the power of alternation. Our contribution is that, just like nondeterminism and pure concurrency are “complement equivalent,” bounded concurrency and alternation are “reverse equivalent” over finite automata. The reverse equivalence is expressed by the existence of polynomial transformations, in both directions, between bounded concurrency and alternation for the reverse of the language accepted by the other. It follows, that bounded concurrency is double-exponentially more succinct than DFAs with respect to reverse, while alternation only saves one exponent. This is as opposed to the direct case where alternation saves two exponents and bounded concurrency saves only one. An immediate corollary is that for languages over a one-letter alphabet, bounded concurrency and alternation are equivalent. We complete the picture of succinctness results for these languages by considering the different combinations of the concurrency models using additional lower bounds.
ISSN:0890-5401
1090-2651
DOI:10.1006/inco.1999.2796