article

Complementing two-way finite automata

Authors:

Viliam Geffert,

Carlo Mereghetti,

Giovanni PighizziniAuthors Info & Claims

Information and Computation, Volume 205, Issue 8

Pages 1173 - 1187

https://doi.org/10.1016/j.ic.2007.01.008

Published: 01 August 2007 Publication History

Abstract

We study the relationship between the sizes of two-way finite automata accepting a language and its complement. In the deterministic case, for a given automaton (2dfa) with n states, we build an automaton accepting the complement with at most 4n states, independently of the size of the input alphabet. Actually, we show a stronger result, by presenting an equivalent 4n-state 2dfa that always halts. For the nondeterministic case, using a variant of inductive counting, we show that the complement of a unary language, accepted by an n-state two-way automaton (2nfa), can be accepted by an O(n^8)-state 2nfa. Here we also make 2nfa's halting. This allows the simulation of unary 2nfa's by probabilistic Las Vegas two-way automata with O(n^8) states.

References

[1]

P. Berman, A. Lingas, On the complexity of regular languages in terms of finite automata. Tech. Report 304, Polish Academy of Sciences, 1977.

[2]

Dietzelfelbinger, M., Kutylowski, M. and Reischuk, R., Exact lower bounds for computing Boolean functions on CREW PRAMs. J. Comput. Syst. Sci. v48. 231-254.

Digital Library

[3]

Geffert, V., Tally versions of the Savitch and Immerman--Szelepcsényi theorems for sublogarithmic space. SIAM J. Comput. v22. 102-113.

[4]

Geffert, V., Mereghetti, C. and Pighizzini, G., Converting two-way nondeterministic automata into simpler automata. Theoret. Comput. Sci. v295. 189-203.

[5]

Goldstine, J., Kappes, M., Kintala, C., Leung, H., Malcher, A. and Wotschke, D., Descriptional complexity of machines with limited resources. J. Universal Comput. Sci. v8. 193-234.

[6]

Hopcroft, J. and Ullman, J., Introduction to Automata Theory, Languages, and Computation. 1979. Addison-Wesley, Reading, MA.

[7]

Hromkovič, J. and Schnitger, G., On the power of Las Vegas II: two-way finite automata. Theoret. Comput. Sci. v262. 1-24.

Digital Library

[8]

Hromkovič, J. and Schnitger, G., On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata. Inform. Comput. v169. 284-296.

Digital Library

[9]

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

[10]

Jirásek, J., Jirásková, G. and Szabari, A., State complexity of concatenation and complementation. Int. J. Found. Comput. Sci. v16. 511-529.

[11]

C. Kapoutsis, Deterministic moles cannot solve liveness, in: Proc. 7th Int. Workshop on Descriptional Complexity of Formal Systems (DCFS 2005), University of St. Milano, Como, Italy, 2005, pp. 194--205.

[12]

A. Kondacs, J. Watrous, On the power of quantum finite state automata, in: Proc. 38th Symp. Found. Comp. Sci. (FOCS 1997), IEEE Computer Society Press, 1997, pp. 66--75.

[13]

Mera, F. and Pighizzini, G., Complementing unary nondeterministic automata. Theoret. Comput. Sci. v330. 349-360.

Digital Library

[14]

Mereghetti, C. and Pighizzini, G., Two-way automata simulations and unary languages. J. Aut. Lang. Combin. v5. 287-300.

[15]

A. Meyer, M. Fischer, Economy of description by automata, grammars, and formal systems, in: Proc. 12th Ann. IEEE Symp. on Switching and Automata Theory, 1971, pp. 188--191.

[16]

Moore, C. and Crutchfield, J., Quantum automata and quantum grammars. Theoret. Comput. Sci. v237. 275-306.

Digital Library

[17]

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

Digital Library

[18]

Rabin, M.O., Probabilistic automata. Inform. Control. v6. 230-245.

[19]

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

[20]

Sipser, M., Lower bounds on the size of sweeping automata. J. Comput. Syst. Sci. v21. 195-202.

[21]

Sipser, M., Halting space bounded computations. Theoret. Comput. Sci. v10. 335-338.

[22]

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

[23]

Vardi, M.Y., A note on the reduction of two-way automata to one-way automata. Inform. Process. Lett. v30. 261-264.

Digital Library

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
Geffert VKapoutsis CZakzok M(2022)Improved complement for two-way alternating automataActa Informatica10.1007/s00236-021-00414-w59:5(619-669)Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1007/s00236-021-00414-w
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

Index Terms

Complementing two-way finite automata
1. Computing methodologies
  1. Artificial intelligence
    1. Natural language processing
  2. Machine learning
    1. Machine learning approaches
      1. Logical and relational learning
        Inductive logic learning
2. Theory of computation
  1. Formal languages and automata theory

Recommendations

Complementing unary nondeterministic automata
Descriptional complexity of formal systems

We compare the nondeterministic state complexity of unary regular languages and that of their complements: if a unary language L has a succinct nondeterministic finite automaton, then nondeterminism is useless in order to recognize its complement, ...
Complementing two-way finite automata
DLT'05: Proceedings of the 9th international conference on Developments in Language Theory

We study the relationship between the sizes of two-way finite automata accepting a language and its complement. In the deterministic case, by adapting Sipser's method, for a given automaton (2dfa) with n states we build an automaton accepting the ...
Converting two-way nondeterministic unary automata into simpler automata

We show that, on inputs of length exceeding 5n2, any n-state unary two-way nondeterministic finite automaton (2nfa) can be simulated by a (2n+2)-state quasi-sweeping 2nfa. Such a result, besides providing a “normal form” for 2nfa's, enables us to get a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Information and Computation

Information and Computation Volume 205, Issue 8

August, 2007

179 pages

ISSN:0890-5401

Issue’s Table of Contents

Copyright © Elsevier Inc. © 2007.

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 August 2007

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

23
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 01 Nov 2024

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
Geffert VKapoutsis CZakzok M(2022)Improved complement for two-way alternating automataActa Informatica10.1007/s00236-021-00414-w59:5(619-669)Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1007/s00236-021-00414-w
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
Petrov SOkhotin A(2021)On the Transformation of Two-Way Deterministic Finite Automata to Unambiguous Finite AutomataLanguage and Automata Theory and Applications10.1007/978-3-030-68195-1_7(81-93)Online publication date: 1-Mar-2021
https://dl.acm.org/doi/10.1007/978-3-030-68195-1_7
Guillon BPrigioniero L(2018)Linear-Time Limited AutomataDescriptional Complexity of Formal Systems10.1007/978-3-319-94631-3_11(126-138)Online publication date: 25-Jul-2018
https://dl.acm.org/doi/10.1007/978-3-319-94631-3_11
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
Montoya JCasas D(2016)On the Real-state Processing of Regular Operations and The Sakoda-Sipser ProblemElectronic Notes in Theoretical Computer Science (ENTCS)10.1016/j.entcs.2016.02.003321:C(23-39)Online publication date: 14-Mar-2016
https://dl.acm.org/doi/10.1016/j.entcs.2016.02.003
Okhotin ASalomaa K(2015)Descriptional complexity of unambiguous input-driven pushdown automataTheoretical Computer Science10.1016/j.tcs.2014.11.015566:C(1-11)Online publication date: 9-Feb-2015
https://dl.acm.org/doi/10.1016/j.tcs.2014.11.015
Kapoutsis CPighizzini G(2015)Two-Way Automata Characterizations of L/poly Versus NLTheory of Computing Systems10.1007/s00224-014-9560-x56:4(662-685)Online publication date: 1-May-2015
https://dl.acm.org/doi/10.1007/s00224-014-9560-x
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents