Skip to main content

2018 | OriginalPaper | Buchkapitel

Complement for Two-Way Alternating Automata

verfasst von : Viliam Geffert

Erschienen in: Computer Science – Theory and Applications

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We consider the problem of converting a two-way alternating finite automaton (2AFA) with n states to a 2AFA accepting the complement of the original language. Complementing is trivial for halting 2AFAs, by inverting the roles of existential and universal decisions and the roles of accepting and rejecting states. However, since 2AFAs do not have resources to detect infinite loops by counting executed steps, the best construction known so far required \(\varOmega (4^n)\) states. Here we shall show that the cost of complementing is polynomial in n. This complementary simulation does not eliminate infinite loops.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Fußnoten
1
Throughout the paper, m denotes the length of the input and n the number of states.
 
2
Such configuration has no sons and the entire subtree degenerates into a single node.
 
Literatur
1.
Zurück zum Zitat Aho, A., Hopcroft, J., Ullman, J.: The Design and Analysis of Computer Algorithms. Addison-Wesley, Boston (1976)MATH Aho, A., Hopcroft, J., Ullman, J.: The Design and Analysis of Computer Algorithms. Addison-Wesley, Boston (1976)MATH
2.
Zurück zum Zitat Berman, L., Chang, J., Ibarra, O., Ravikumar, B.: Some observations concerning alternating Turing machines using small space. Inf. Process. Lett. 25, 1–9 (1987). Corr. ibid. 27, p. 53 (1988)MathSciNetCrossRefMATH Berman, L., Chang, J., Ibarra, O., Ravikumar, B.: Some observations concerning alternating Turing machines using small space. Inf. Process. Lett. 25, 1–9 (1987). Corr. ibid. 27, p. 53 (1988)MathSciNetCrossRefMATH
3.
Zurück zum Zitat Birget, J.: Partial orders on words, minimal elements of regular languages, and state complexity. Theor. Comput. Sci. 119, 267–291 (1993)MathSciNetCrossRefMATH Birget, J.: Partial orders on words, minimal elements of regular languages, and state complexity. Theor. Comput. Sci. 119, 267–291 (1993)MathSciNetCrossRefMATH
4.
Zurück zum Zitat Brassard, G., Bratley, P.: Fundamentals of Algorithmics. Prentice Hall, Upper Saddle River (1996)MATH Brassard, G., Bratley, P.: Fundamentals of Algorithmics. Prentice Hall, Upper Saddle River (1996)MATH
7.
Zurück zum Zitat Geffert, V.: Alternating space is closed under complement and other simulations for sublogarithmic space. Inf. Comput. 253, 163–178 (2017)MathSciNetCrossRefMATH Geffert, V.: Alternating space is closed under complement and other simulations for sublogarithmic space. Inf. Comput. 253, 163–178 (2017)MathSciNetCrossRefMATH
8.
10.
Zurück zum Zitat Hopcroft, J., Motwani, R., Ullman, J.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Boston (2001)MATH Hopcroft, J., Motwani, R., Ullman, J.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Boston (2001)MATH
14.
15.
Zurück zum Zitat Liśkiewicz, M., Reischuk, R.: Computing with sublogarithmic space. In: Hemaspaandra, L., Selman, A. (eds.) Complexity Theory Retrospective II. Springer, New York (1997). ISBN 978-0-387-94973-4 Liśkiewicz, M., Reischuk, R.: Computing with sublogarithmic space. In: Hemaspaandra, L., Selman, A. (eds.) Complexity Theory Retrospective II. Springer, New York (1997). ISBN 978-0-387-94973-4
16.
Zurück zum Zitat Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, Boston (1994)MATH Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, Boston (1994)MATH
Metadaten
Titel
Complement for Two-Way Alternating Automata
verfasst von
Viliam Geffert
Copyright-Jahr
2018
DOI
https://doi.org/10.1007/978-3-319-90530-3_12