Journal article
On composition and lookahead delegation of e -services modeled by automata
Theoretical computer science, Vol.341(1), pp.344-363
2005
Handle:
https://hdl.handle.net/2376/114345
Abstract
Let
M
be a class of (possibly nondeterministic) language acceptors with a one-way input tape. A system
(
A
;
A
1
,
…
,
A
r
)
of automata in
M
is
composable if for every string
w
=
a
1
⋯
a
n
of symbols accepted by
A
, there is an assignment of each symbol
a
j
in
w
to one of the
A
i
's such that for each
1
⩽
i
⩽
r
, the subsequence of
w
assigned to
A
i
is accepted by
A
i
. For a nonnegative integer
k
, a
k
-
lookahead delegator for
(
A
;
A
1
,
…
,
A
r
)
is a deterministic machine
D
in
M
which, knowing (a) the current states of
A
,
A
1
,
…
,
A
r
and the accessible “local” information of each machine (e.g., the top of the stack if each machine is a pushdown automaton, whether a counter is zero or nonzero if each machine is a multicounter automaton, etc.), and (b) the
k
lookahead symbols to the right of the current input symbol being processed, can uniquely determine the
A
i
to assign the current symbol. Moreover, every string
w
accepted by
A
is also accepted by
D
; i.e., the subsequence of string
w
delegated by
D
to each
A
i
is accepted by
A
i
. Thus,
k
-lookahead delegation is a stronger requirement than composability, since the delegator
D
must be deterministic. A system that is composable may not have a
k
-delegator for any
k
.
We study the decidability of composability and existence of
k
-delegators for various classes of machines
M
. Our results generalize earlier ones (and resolve some open questions) concerning composability of deterministic finite automata as e-services to finite automata that are augmented with unbounded storage (e.g., counters and pushdown stacks) and finite automata with discrete clocks (i.e., discrete timed automata). The results have applications to automated composition of e-services.
Metrics
7 Record Views
Details
- Title
- On composition and lookahead delegation of e -services modeled by automata
- Creators
- Zhe Dang - School of Electrical Engineering and Computer Science, Washington State University, Pullman, WA 99164, USAOscar H Ibarra - Department of Computer Science, University of California, Santa Barbara, CA 93106, USAJianwen Su - Department of Computer Science, University of California, Santa Barbara, CA 93106, USA
- Publication Details
- Theoretical computer science, Vol.341(1), pp.344-363
- Academic Unit
- Electrical Engineering and Computer Science, School of
- Publisher
- Elsevier B.V
- Identifiers
- 99900548323801842
- Language
- English
- Resource Type
- Journal article