More Web Proxy on the site http://driver.im/

article

An alternating hierarchy for finite automata

Author:

Viliam GeffertAuthors Info & Claims

Theoretical Computer Science, Volume 445

Pages 1 - 24

https://doi.org/10.1016/j.tcs.2012.04.044

Published: 01 August 2012 Publication History

Abstract

We study the polynomial state complexity classes 2@S"k and 2@P"k, that is, the hierarchy of problems that can be solved with a polynomial number of states by two-way alternating finite automata (2Afas) making at most k-1 alternations between existential and universal states, starting in an existential or universal state, respectively. This hierarchy is infinite: for k=2,3,4,..., both 2@S"k"-"1 and 2@P"k"-"1 are proper subsets of 2@S"k and of 2@P"k, since the conversion of a one-way @S"k- or @P"k-alternating automaton with n states into a two-way automaton with a smaller number of alternations requires 2^n^/^4^-^O^(^k^) states. The same exponential blow-up is required for converting a @S"k-bounded 2Afa into a @P"k-bounded 2Afa and vice versa, that is, 2@S"k and 2@P"k are incomparable. In the case of @S"k-bounded 2Afas, the exponential gap applies also for intersection, while in the case of @P"k-bounded 2Afas for union. The same results are established for one-way alternating finite automata. This solves several open problems raised in [C. Kapoutsis, Size complexity of two-way finite automata, in: Proc. Develop. Lang. Theory, in: Lect. Notes Comput. Sci., vol. 5583, Springer-Verlag, 2009, pp. 47-66.]

References

[1]

Rabin, M. and Scott, D., Finite automata and their decision problems. IBM J. Res. Develop. v3. 114-125.

[2]

Shepherdson, M., The reduction of two-way automata to one-way automata. IBM J. Res. Develop. v3. 198-200.

[3]

Lupanov, O., Über den Vergleich zweier Typen endlicher Quellen. Probl. Kybern. v6. 329-335.

[4]

Moore, F., On the bounds for state-set size in the proofs of equivalence between deterministic, nondeterministic, and two-way finite automata. IEEE Trans. Comput. vC-20. 1211-1214.

Digital Library

[5]

Salomaa, A., Wood, D. and Yu, S., On the state complexity of reversals of regular languages. Theoret. Comput. Sci. v320. 315-329.

Digital Library

[6]

W. Sakoda, M. Sipser, Nondeterminism and the size of two-way finite automata, in: Proc. ACM Symp. Theory of Comput., 1978, pp. 275-286.

[7]

Chrobak, M. and Chrobak, M., Finite automata and unary languages. Theoret. Comput. Sci. v47. 149-158.

Digital Library

[8]

Kapoutsis, C., Size complexity of two-way finite automata. In: Lect. Notes Comput. Sci., vol. 5583. Springer-Verlag. pp. 47-66.

Digital Library

[9]

Papadimitriou, C., Computational Complexity. 1994. Addison-Wesley.

[10]

Sipser, M., Introduction to the Theory of Computation. 2006. 2nd ed. Thomson Course Technology.

[11]

Chandra, A., Kozen, D. and Stockmeyer, L., Alternation. J.~Assoc. Comput. Mach. v28. 114-133.

Digital Library

[12]

Bovet, D. and Crescenzi, P., Introduction to the Theory of Complexity. 1994. Prentice Hall.

[13]

Li¿kiewicz, M. and Reischuk, R., Computing with sublogarithmic space. In: Hemaspaandra, L., Selman, A. (Eds.), Complexity Theory Retrospective~II, Springer-Verlag.

[14]

Immerman, N., Nondeterministic space is closed under complementation. SIAM J. Comput. v17. 935-938.

[15]

Szelepcsényi, R., The method of forced enumeration for nondeterministic automata. Acta Inform. v26. 279-284.

[16]

Braunmühl, B., Gengler, R. and Rettinger, R., The alternation hierarchy for sublogarithmic space is infinite. Comput. Complexity. v3. 207-230.

Digital Library

[17]

Geffert, V., A~hierarchy that does not collapse: alternations in low level space. RAIRO Inform. Théor. Appl. v28. 465-512.

[18]

Li¿kiewicz, M. and Reischuk, R., The sublogarithmic alternating space world. SIAM J. Comput. v25. 828-861.

[19]

Iwama, K., ASPACE(o(loglogn)) is regular. SIAM J. Comput. v22. 136-146.

[20]

Hopcroft, J., Motwani, R. and Ullman, J., Introduction to Automata Theory, Languages, and Computation. 2007. 3rd ed. Prentice Hall.

[21]

Berman, L., Chang, J., Ibarra, O., Ravikumar, B., Berman, L., Chang, J., Ibarra, O. and Ravikumar, B., Some observations concerning alternating Turing machines using small space. Inform. Process. Lett. v25. 1-9.

[22]

Geffert, V., Nondeterministic computations in sublogarithmic space and space constructibility. SIAM J. Comput. v20. 484-498.

[23]

Mereghetti, C. and Pighizzini, G., Optimal simulations between unary automata. SIAM J. Comput. v30. 1976-1992.

Cited By

Yamakami T(2024)Unambiguous and Co-nondeterministic Computations of Finite Automata and Pushdown Automata Families and the Effects of Multiple CountersTheory and Applications of Models of Computation10.1007/978-981-97-2340-9_2(14-25)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1007/978-981-97-2340-9_2
Han YKim SKo SSalomaa K(2023)Existential and Universal Width of Alternating Finite AutomataDescriptional Complexity of Formal Systems10.1007/978-3-031-34326-1_4(51-64)Online publication date: 4-Jul-2023
https://dl.acm.org/doi/10.1007/978-3-031-34326-1_4
Geffert VKapoutsis CZakzok M(2021)Complement for two-way alternating automataActa Informatica10.1007/s00236-020-00373-858:5(463-495)Online publication date: 1-Oct-2021
https://dl.acm.org/doi/10.1007/s00236-020-00373-8
Show More Cited By

An alternating hierarchy for finite automata
1. Theory of computation

Recommendations

State hierarchy for one-way finite automata

Quite recently, it has been shown that, for each n, and each d between n and 2ⁿ, there exists a regular language for which each optimal nondeterministic one-way finite state automaton (nfa) uses exactly n states, but its optimal deterministic ...
Magic numbers in the state hierarchy of finite automata

A number d is magic for n, if there is no regular language for which an optimal nondeterministic finite state automaton (nfa) uses exactly n states and, at the same time, the optimal deterministic finite state automaton (dfa) uses exactly d states. We ...
Oblivious two-way finite automata: Decidability and complexity

We investigate the descriptional complexity and decidability of obliviousness for two-way finite automata. In particular, we consider the simulation of two-way deterministic finite automata (2DFAs) by oblivious 2DFAs, the simulation of oblivious 2DFAs ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Theoretical Computer Science

Theoretical Computer Science Volume 445, Issue

August, 2012

98 pages

ISSN:0304-3975

Issue’s Table of Contents

Copyright © Elsevier B.V. © 2012.

Publisher

Elsevier Science Publishers Ltd.

United Kingdom

Publication History

Published: 01 August 2012

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Yamakami T(2024)Unambiguous and Co-nondeterministic Computations of Finite Automata and Pushdown Automata Families and the Effects of Multiple CountersTheory and Applications of Models of Computation10.1007/978-981-97-2340-9_2(14-25)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1007/978-981-97-2340-9_2
Han YKim SKo SSalomaa K(2023)Existential and Universal Width of Alternating Finite AutomataDescriptional Complexity of Formal Systems10.1007/978-3-031-34326-1_4(51-64)Online publication date: 4-Jul-2023
https://dl.acm.org/doi/10.1007/978-3-031-34326-1_4
Geffert VKapoutsis CZakzok M(2021)Complement for two-way alternating automataActa Informatica10.1007/s00236-020-00373-858:5(463-495)Online publication date: 1-Oct-2021
https://dl.acm.org/doi/10.1007/s00236-020-00373-8
Keeler CSalomaa K(2021)Width Measures of Alternating Finite AutomataDescriptional Complexity of Formal Systems10.1007/978-3-030-93489-7_8(88-99)Online publication date: 5-Sep-2021
https://dl.acm.org/doi/10.1007/978-3-030-93489-7_8
Keeler CSalomaa K(2020)Combining Limited Parallelism and Nondeterminism in Alternating Finite AutomataDescriptional Complexity of Formal Systems10.1007/978-3-030-62536-8_8(91-103)Online publication date: 24-Aug-2020
https://dl.acm.org/doi/10.1007/978-3-030-62536-8_8
Keeler CSalomaa K(2020)Alternating Finite Automata with Limited Universal BranchingLanguage and Automata Theory and Applications10.1007/978-3-030-40608-0_13(196-207)Online publication date: 4-Mar-2020
https://dl.acm.org/doi/10.1007/978-3-030-40608-0_13
Geffert V(2018)Complement for Two-Way Alternating AutomataComputer Science – Theory and Applications10.1007/978-3-319-90530-3_12(132-144)Online publication date: 6-Jun-2018
https://dl.acm.org/doi/10.1007/978-3-319-90530-3_12
Jirskov GOkhotin A(2017)On the state complexity of operations on two-way finite automataInformation and Computation10.1016/j.ic.2016.12.007253:P1(36-63)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1016/j.ic.2016.12.007
Geffert VGuillon BPighizzini G(2014)Two-way automata making choices only at the endmarkersInformation and Computation10.1016/j.ic.2014.08.009239:C(71-86)Online publication date: 1-Dec-2014
https://dl.acm.org/doi/10.1016/j.ic.2014.08.009
Balodis K(2013)One alternation can be more powerful than randomization in small and fast two-way finite automataProceedings of the 19th international conference on Fundamentals of Computation Theory10.1007/978-3-642-40164-0_7(40-47)Online publication date: 19-Aug-2013
https://dl.acm.org/doi/10.1007/978-3-642-40164-0_7
Show More Cited By

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents