Paper Info
Title
Alternating Finite Automata With Counters And Stack-Counters Operating In Realtime
Abstract
This paper investigates the accepting powers of one-way alternating finite automata with counters and stack-counters (1afacs'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 k greater than or equal to 0 and l greater than or equal to 0 ((k,l)double dagger(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 1afacs's with only universal states, with only existential states, and with full alternation, and show, for example, that for each k greater than or equal to 0 and l greater than or equal to 0((k,l)double dagger(0,0)), 1UFACS(k,l,real) boolean OR 1NFACS(k,l,real) not equal subset of 1AFACS(k,l,real). We then investigate hierarchical properties based on the number of counters and stack-counters, and show, for example, that for each k greater than or equal to 0 and l greater than or equal to 0 ((k,l)double dagger(0,0)), and each XE({U,N}, 1XFACS (k+1,l,real)-1AFACS (k,l,real)double dagger phi. We finally investigate a relationship between counters and stack-counters, and show, for example, that for each k greater than or equal to 0, l greater than or equal to 0 and m greater than or equal to 1, and each X is an element of{U,N}, 1XFACS(k,l+m,real)-1AFACS (k+2m - 1,l,real)double dagger phi.
Year
Venue
Keywords
1995
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS
ALTERNATION, REALTIME COMPUTATION, ONE-WAY COUNTER AUTOMATA, ONE-WAY STACK-COUNTER AUTOMATA, COMPUTATIONAL COMPLEXITY
Field
DocType
Volume
Mobile automaton,Computer science,Finite-state machine,Theoretical computer science,ω-automaton,Computational complexity theory,Alternation (linguistics)
Journal
E78D
Issue
ISSN
Citations 
8
0916-8532
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Tsunehiro Yoshinaga166.98
Katsushi Inoue251574.43