Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Acta Informatica
Erschienen in: Acta Informatica 5/2021

17.02.2020 | Original Article

Complement for two-way alternating automata

verfasst von: Viliam Geffert, Christos A. Kapoutsis, Mohammad Zakzok

Erschienen in: Acta Informatica | Ausgabe 5/2021

Einloggen

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 its language. Complementing is trivial for halting 2AFAs, by swapping 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, it was not known whether the cost of complementing is polynomial in n in the general case. Here we shall show that 2AFAs can be complemented by using \(O(n^7)\) states.
Nächster Artikel Indecision and delays are the parents of failure—taming them algorithmically by synthesizing delay-resilient control

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Fußnoten
1
Throughout the paper, m denotes the length of the input and n the number of states.
 
2
Sometimes, we call this tree “standard”, since other trees induced by the same configuration graph will also be used later.
 
3
This means that \({\mathsf {A}}\) must be in an accepting state when it halts; the position of the input head at this moment is not relevant; such configuration has no sons; and the entire subtree degenerates into a single node.
 
4
Both \(\langle {}d,r{}\rangle \in D{\times }Q\) and \(dr\in D{\cdot }Q\) represent an ordered pair satisfying \(d\in D\) and \(r\in Q\). We introduce a superfluous binary operator in order not to complicate notation more than necessary.
 
5
The chronological order in which \(\kappa _{\scriptscriptstyle {j_{\pi }}},\ldots ,\kappa _{\scriptscriptstyle {j_1}}\) are determined as accepting does not correspond to the order in which \({\mathsf {A}}'\) traverses from these configurations to \(\kappa \). For example, in Fig. 1, the configuration \(\langle {}q_{\scriptscriptstyle {0}},3{}\rangle \) is determined as accepting earlier than \(\langle {}q_{\scriptscriptstyle {0}},5{}\rangle \), but \(\langle {}q_{\scriptscriptstyle {1}},4{}\rangle \) is visited from \(\langle {}q_{\scriptscriptstyle {0}},5{}\rangle \) earlier than from \(\langle {}q_{\scriptscriptstyle {0}},3{}\rangle \).
 
6
It should be pointed out that \(\kappa \) can also be visited in the mode “\(\mathsf {{}from}\_{\mathsf {succ}}\)” by traversals from configurations that are not its valid sons. However, by (a.1), such visits do not modify the read–write contents in the cell.
 
Literatur
1.
Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The Design and Analysis of Computer Algorithms. Addison-Wesley, Boston, MA (1976)MATH
2.
Berman, L., Chang, J.H., Ibarra, O.H., Ravikumar, B.: Some observations concerning alternating turing machines using small space. Inf. Process. Lett. 25, 1–9 (1987). (Corr. ibid., 27, p. 53, 1988.)MathSciNetCrossRef
3.
Birget, J.-C.: Partial orders on words, minimal elements of regular languages, and state complexity. Theor. Comput. Sci. 119, 267–91 (1993)MathSciNetCrossRef
4.
Bovet, D.P., Crescenzi, P.: Introduction to the Theory of Complexity. Prentice Hall, Upper Saddle River, NJ (1994)MATH
5.
Brassard, G., Bratley, P.: Fundamentals of Algorithmics. Prentice Hall, Upper Saddle River, NJ (1996)MATH
6.
7.
8.
9.
Geffert, V.: Complement for two-way alternating automata. In: Proceedings on Computer Science Theory and Applications in Russia, Lecture Notes in Computer Science, vol. 10846, pp. 132–44. Springer (2018)
10.
Geffert, V., Mereghetti, C., Pighizzini, G.: Complementing two-way finite automata. Inf. Comput. 205, 1173–87 (2007)MathSciNetCrossRef
11.
Geffert, V., Okhotin, A.: Transforming two-way alternating finite automata to one-way nondeterministic automata. In: Proceedings on Mathematical Foundations of Computer Science Part I, Lecture Notes in Computer Science, vol. 8634, pp. 291–302. Springer (2014)
12.
Hopcroft, J., Motwani, R., Ullman, J.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Boston, MA (2001)MATH
13.
14.
Kapoutsis, Ch.A.: Size complexity of two-way finite automata. In: Proceedings on Developments in Language Theory, Lecture Notes in Computer Science, vol. 5583, pp. 47–66. Springer (2009)
15.
Kapoutsis, Ch.A.: Minicomplexity. J. Autom. Lang. Combin. 17, 205–24 (2012)
16.
Kunc, M., Okhotin, A.: Reversibility of computations in graph-walking automata. In: Proceedings on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, vol. 8087, pp. 595–606. Springer (2013)
17.
Ladner, R.E., Lipton, R.J., Stockmeyer, L.J.: Alternating pushdown and stack automata. SIAM J. Comput. 13, 135–55 (1984)MathSciNetCrossRef
18.
Liśkiewicz, M., Reischuk, R.: Computing with sublogarithmic space. In: Hemaspaandra, L., Selman, A. (eds.) Complexity Theory Retrospective II. Springer, Berlin (1997)
19.
Papadimitriou, Ch.H.: Computational Complexity. Addison-Wesley, Boston, MA (1994)
20.
Sakoda, W., Sipser, M.: Nondeterminism and the size of two-way finite automata. In: Proceedings on ACM Symposium Theory of Computing, pp. 275–86 (1978)
21.
22.
Sipser, M.: Introduction to the Theory of Computation, 2nd edn. Thomson Course Technology, Boston, MA (2006)MATH
23.
Szelepcsényi, R.: The method of forced enumeration for nondeterministic automata. Acta Inform. 26, 279–84 (1988)MathSciNetCrossRef
24.
Szepietowski, A.: Turing Machines with Sublogarithmic Space. Lecture Notes in Computer Science, vol. 843. Springer, Berlin (1994)CrossRef
Metadaten
Titel
Complement for two-way alternating automata
verfasst von
Viliam Geffert
Christos A. Kapoutsis
Mohammad Zakzok
Publikationsdatum
17.02.2020
Verlag
Springer Berlin Heidelberg
Erschienen in
Acta Informatica / Ausgabe 5/2021
Print ISSN: 0001-5903
Elektronische ISSN: 1432-0525
DOI
https://doi.org/10.1007/s00236-020-00373-8

Premium Partner

    Bildnachweise