Skip to main content

2017 | OriginalPaper | Buchkapitel

Reversible Nondeterministic Finite Automata

verfasst von : Markus Holzer, Martin Kutrib

Erschienen in: Reversible Computation

Verlag: Springer International Publishing

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

search-config
loading …

Abstract

By former and recent results the model of reversible deterministic finite automata is well understood. On the other hand, reversible nondeterministic finite automata and their accepted languages have not systematically been considered in the literature. Here it turns out that reversible nondeterministic finite automata (\(\text {REV-NFA}\)s) are more powerful compared to their reversible deterministic counterparts, but still cannot accept all regular languages. Moreover, we compare the family of languages accepted by \(\text {REV-NFA}\)s to the language families accepted by deterministic and nondeterministic finite state automata with irreversibility degree k. Besides these results on the computational power of \(\text {REV-NFA}\)s we consider closure properties of the language family induced by these devices.

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!

Literatur
1.
Zurück zum Zitat Ambainis, A., Freivalds, R.: 1-way quantum finite automata: strengths, weakness and generalizations. In: Motwani, R. (ed.) Foundations of Computer Science (FOCS 1998), pp. 332–341. IEEE Computer Society (1998) Ambainis, A., Freivalds, R.: 1-way quantum finite automata: strengths, weakness and generalizations. In: Motwani, R. (ed.) Foundations of Computer Science (FOCS 1998), pp. 332–341. IEEE Computer Society (1998)
3.
Zurück zum Zitat Axelsen, H.B., Holzer, M., Kutrib, M.: The degree of irreversibility in deterministic finite automata. In: Han, Y.-S., Salomaa, K. (eds.) CIAA 2016. LNCS, vol. 9705, pp. 15–26. Springer, Cham (2016). doi:10.1007/978-3-319-40946-7_2 CrossRef Axelsen, H.B., Holzer, M., Kutrib, M.: The degree of irreversibility in deterministic finite automata. In: Han, Y.-S., Salomaa, K. (eds.) CIAA 2016. LNCS, vol. 9705, pp. 15–26. Springer, Cham (2016). doi:10.​1007/​978-3-319-40946-7_​2 CrossRef
4.
Zurück zum Zitat Axelsen, H.B., Glück, R.: A simple and efficient universal reversible turing machine. In: Dediu, A.-H., Inenaga, S., Martín-Vide, C. (eds.) LATA 2011. LNCS, vol. 6638, pp. 117–128. Springer, Heidelberg (2011). doi:10.1007/978-3-642-21254-3_8 CrossRef Axelsen, H.B., Glück, R.: A simple and efficient universal reversible turing machine. In: Dediu, A.-H., Inenaga, S., Martín-Vide, C. (eds.) LATA 2011. LNCS, vol. 6638, pp. 117–128. Springer, Heidelberg (2011). doi:10.​1007/​978-3-642-21254-3_​8 CrossRef
6.
Zurück zum Zitat García, P., de Parga, M.V., López, D.: On the efficient construction of quasi-reversible automata for reversible languages. Inform. Process. Lett. 107, 13–17 (2008)MathSciNetCrossRefMATH García, P., de Parga, M.V., López, D.: On the efficient construction of quasi-reversible automata for reversible languages. Inform. Process. Lett. 107, 13–17 (2008)MathSciNetCrossRefMATH
8.
Zurück zum Zitat Harrison, M.A.: Introduction to Formal Language Theory. Addison-Wesley, Boston (1978)MATH Harrison, M.A.: Introduction to Formal Language Theory. Addison-Wesley, Boston (1978)MATH
10.
Zurück zum Zitat Holzer, M., Salomaa, K., Yu, S.: On the state complexity of \(k\)-entry deterministic finite automata. J. Autom. Lang. Comb. 6, 453–466 (2001)MathSciNetMATH Holzer, M., Salomaa, K., Yu, S.: On the state complexity of \(k\)-entry deterministic finite automata. J. Autom. Lang. Comb. 6, 453–466 (2001)MathSciNetMATH
11.
Zurück zum Zitat Kappes, M.: Descriptional complexity of deterministic finite automata with multiple initial states. J. Autom. Lang. Comb. 5, 265–278 (2000)MathSciNetMATH Kappes, M.: Descriptional complexity of deterministic finite automata with multiple initial states. J. Autom. Lang. Comb. 5, 265–278 (2000)MathSciNetMATH
12.
Zurück zum Zitat Kobayashi, S., Yokomori, T.: Learning approximately regular languages with reversible languages. Theoret. Comput. Sci. 174, 251–257 (1997)MathSciNetCrossRefMATH Kobayashi, S., Yokomori, T.: Learning approximately regular languages with reversible languages. Theoret. Comput. Sci. 174, 251–257 (1997)MathSciNetCrossRefMATH
13.
Zurück zum Zitat Lavado, G.J., Pighizzini, G., Prigioniero, L.: Minimal and reduced reversible automata. In: Câmpeanu, C., Manea, F., Shallit, J. (eds.) DCFS 2016. LNCS, vol. 9777, pp. 168–179. Springer, Cham (2016). doi:10.1007/978-3-319-41114-9_13 CrossRef Lavado, G.J., Pighizzini, G., Prigioniero, L.: Minimal and reduced reversible automata. In: Câmpeanu, C., Manea, F., Shallit, J. (eds.) DCFS 2016. LNCS, vol. 9777, pp. 168–179. Springer, Cham (2016). doi:10.​1007/​978-3-319-41114-9_​13 CrossRef
14.
Zurück zum Zitat Lombardy, S.: On the construction of reversible automata for reversible languages. In: Widmayer, P., Eidenbenz, S., Triguero, F., Morales, R., Conejo, R., Hennessy, M. (eds.) ICALP 2002. LNCS, vol. 2380, pp. 170–182. Springer, Heidelberg (2002). doi:10.1007/3-540-45465-9_16 CrossRef Lombardy, S.: On the construction of reversible automata for reversible languages. In: Widmayer, P., Eidenbenz, S., Triguero, F., Morales, R., Conejo, R., Hennessy, M. (eds.) ICALP 2002. LNCS, vol. 2380, pp. 170–182. Springer, Heidelberg (2002). doi:10.​1007/​3-540-45465-9_​16 CrossRef
15.
Zurück zum Zitat Morita, K., Shirasaki, A., Gono, Y.: A 1-tape 2-symbol reversible Turing machine. Trans. IEICE E72, 223–228 (1989) Morita, K., Shirasaki, A., Gono, Y.: A 1-tape 2-symbol reversible Turing machine. Trans. IEICE E72, 223–228 (1989)
16.
Zurück zum Zitat Pin, J.-E.: On reversible automata. In: Simon, I. (ed.) LATIN 1992. LNCS, vol. 583, pp. 401–416. Springer, Heidelberg (1992). doi:10.1007/BFb0023844 Pin, J.-E.: On reversible automata. In: Simon, I. (ed.) LATIN 1992. LNCS, vol. 583, pp. 401–416. Springer, Heidelberg (1992). doi:10.​1007/​BFb0023844
17.
Metadaten
Titel
Reversible Nondeterministic Finite Automata
verfasst von
Markus Holzer
Martin Kutrib
Copyright-Jahr
2017
DOI
https://doi.org/10.1007/978-3-319-59936-6_3