Abstract
In this paper, we introduce a new model of automata, called input-synchronized alternating finite automata (i-SAFAs), and study the power of i-SAFAs. We here consider two types of i-SAFAs, oneway i-SAFAs and two-way i-SAFAs. Then we show that (1) the class of languages accepted by one-way i-SAFAs is equal to the class of regular languages, (2) two-way i-SAFAs are more powerful than one-way i-SAFAs, that is, there exists a language L such that L is accepted by a two-way i-SAFA but not accepted by any one-way i-SAFAs. In addition, we show that the class of languages accepted by f(n) parallel-bounded two-way i-SAFAs is included in Nspace(S(n)), where S(n) = minn log n, f(n) log n.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
A.K. Chandra, D.C. Kozen and L.J. Stockmeyer, Alternation, J. Assoc. Comput. Mach. 28,1, 114–133, 1981.
O.H. Ibarra and N.Q. Tran, On communication-bounded synchronized alternating finite automata, Acta Informatica, 31,4, 315–327, 1994.
J. Dassow, J. Hromkovic, J. Karhuaki, B. Rovan and A. Slobodova, On the power of synchronization in parallel computation, In Proc. 14th MFCS’89, LNCS 379, 196–206, 1989.
J.E. Hopcroft and J.D. Ullman, Introduction to automata theory language and computation, Addison Wesley, Reading Mass, 1979.
J. Hromkovic, K. Inoue, B. Rovan, A. Slobodova, I. Takanami and K.W. Wagner, On the power of one-way synchronized alternating machines with small space, International Journal of Foundations of Computer Science, 3,1, 65–79, 1992.
J. Hromkovic and K. Inoue, A note on realtime one-way synchronized alternating one-counter automata, Theoret. Comput. Sci., 108,2, 393–400, 1993.
J. Hromkovic, B. Rovan and A. Slobodova, Deterministic versus nondeterministic space in terms of synchronized alternating machines, Theoret. Comput. Sci., 132,2, 319–336, 1994.
R.E. Ladner, R.J. Ripton and L.J. Stockmeyer, Alternating pushdown and stack automata, SIAM J. Computing, 13,1, 1984.
A. Slobodova, On the power of communication in alternating machines, In Proc. 13th MFCS’88, LNCS 324, 518–528, 1988.
M.Y. Vardi, Alternating automata and program verification, In Computer Science Today-Recent Trends and Developments, LNCS 1000, 471–485, 1996.
H. Yamamoto, An automata-based recognition algorithm for semi-extended regular expressions, manuscript, 2000.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Yamamoto, H. (2000). On the Power of Input-Synchronized Alternating Finite Automata. In: Du, DZ., Eades, P., Estivill-Castro, V., Lin, X., Sharma, A. (eds) Computing and Combinatorics. COCOON 2000. Lecture Notes in Computer Science, vol 1858. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44968-X_45
Download citation
DOI: https://doi.org/10.1007/3-540-44968-X_45
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67787-1
Online ISBN: 978-3-540-44968-3
eBook Packages: Springer Book Archive