Copy
Tsunehiro YOSHINAGA, Katsushi INOUE, "Alternating Finite Automata with Counters and Stack-Counters Operating in Realtime" in IEICE TRANSACTIONS on Information,
vol. E78-D, no. 8, pp. 929-938, August 1995, doi: .
Abstract: This paper investigates the accepting powers of one-way alternatiog finite automata with counters and stack-counters (lafacs's) which operate in realtime. (The difference between counter" and stack-counter" is that the latter can be entered without the contents being changed, but the former cannot.) For each k0 and l0 ((k, l)(0, 0)), let 1AFACS(k, l, real) denote the class of sets accepted by realtime one-way alternating finite automata with k counters and l stack-counters, and let 1UFACS(k, l, real) (1NFACS(k, l, real)) denote the class of sets accepted by realtime one-way alternating finite automata with k counters and l stack-counters which have only universal (existential) states. We first investigate a relationship among the accepting powers of realtime lafacs's with only universal states, with only existential states, and with full alternation, and show, for example, that for each k0 and l0 ((k, l)(0, 0)), 1UFACS(k, l, real) 1NFACS(k, l, real) 1AFACS(k, l, real). We then investigate hierarchical properties based on the number of counters and stack-counters, and show, foe example, that for each k0 and l0 ((k, l)(0, 0)), and each X{U, N}, 1XFACS(k1, l, real)1AFACS(k, l, real)φ. We finally investigate a relationship between counters and stack-counters, and show, for example, that for each k0, l0 and m1, and each X{U, N}, 1XFACS(k, lm, real)1AFACS(k2m1, l, real)φ.
URL: https://globals.ieice.org/en_transactions/information/10.1587/e78-d_8_929/_p
Copy
@ARTICLE{e78-d_8_929,
author={Tsunehiro YOSHINAGA, Katsushi INOUE, },
journal={IEICE TRANSACTIONS on Information},
title={Alternating Finite Automata with Counters and Stack-Counters Operating in Realtime},
year={1995},
volume={E78-D},
number={8},
pages={929-938},
abstract={This paper investigates the accepting powers of one-way alternatiog finite automata with counters and stack-counters (lafacs's) which operate in realtime. (The difference between counter" and stack-counter" is that the latter can be entered without the contents being changed, but the former cannot.) For each k0 and l0 ((k, l)(0, 0)), let 1AFACS(k, l, real) denote the class of sets accepted by realtime one-way alternating finite automata with k counters and l stack-counters, and let 1UFACS(k, l, real) (1NFACS(k, l, real)) denote the class of sets accepted by realtime one-way alternating finite automata with k counters and l stack-counters which have only universal (existential) states. We first investigate a relationship among the accepting powers of realtime lafacs's with only universal states, with only existential states, and with full alternation, and show, for example, that for each k0 and l0 ((k, l)(0, 0)), 1UFACS(k, l, real) 1NFACS(k, l, real) 1AFACS(k, l, real). We then investigate hierarchical properties based on the number of counters and stack-counters, and show, foe example, that for each k0 and l0 ((k, l)(0, 0)), and each X{U, N}, 1XFACS(k1, l, real)1AFACS(k, l, real)φ. We finally investigate a relationship between counters and stack-counters, and show, for example, that for each k0, l0 and m1, and each X{U, N}, 1XFACS(k, lm, real)1AFACS(k2m1, l, real)φ.},
keywords={},
doi={},
ISSN={},
month={August},}
Copy
TY - JOUR
TI - Alternating Finite Automata with Counters and Stack-Counters Operating in Realtime
T2 - IEICE TRANSACTIONS on Information
SP - 929
EP - 938
AU - Tsunehiro YOSHINAGA
AU - Katsushi INOUE
PY - 1995
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E78-D
IS - 8
JA - IEICE TRANSACTIONS on Information
Y1 - August 1995
AB - This paper investigates the accepting powers of one-way alternatiog finite automata with counters and stack-counters (lafacs's) which operate in realtime. (The difference between counter" and stack-counter" is that the latter can be entered without the contents being changed, but the former cannot.) For each k0 and l0 ((k, l)(0, 0)), let 1AFACS(k, l, real) denote the class of sets accepted by realtime one-way alternating finite automata with k counters and l stack-counters, and let 1UFACS(k, l, real) (1NFACS(k, l, real)) denote the class of sets accepted by realtime one-way alternating finite automata with k counters and l stack-counters which have only universal (existential) states. We first investigate a relationship among the accepting powers of realtime lafacs's with only universal states, with only existential states, and with full alternation, and show, for example, that for each k0 and l0 ((k, l)(0, 0)), 1UFACS(k, l, real) 1NFACS(k, l, real) 1AFACS(k, l, real). We then investigate hierarchical properties based on the number of counters and stack-counters, and show, foe example, that for each k0 and l0 ((k, l)(0, 0)), and each X{U, N}, 1XFACS(k1, l, real)1AFACS(k, l, real)φ. We finally investigate a relationship between counters and stack-counters, and show, for example, that for each k0, l0 and m1, and each X{U, N}, 1XFACS(k, lm, real)1AFACS(k2m1, l, real)φ.
ER -
English
