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
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Buchtitelbild

2015 | OriginalPaper | Buchkapitel

Unambiguity in Automata Theory

verfasst von : Thomas Colcombet

Erschienen in: Descriptional Complexity of Formal Systems

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

Determinism of devices is a key aspect throughout all of computer science, simply because of considerations of efficiency of the implementation. One possible way (among others) to relax this notion is to consider unambiguous machines: non-deterministic machines that have at most one accepting run on each input.
In this paper, we will investigate the nature of unambiguity in automata theory, presenting the cases of standard finite words up to infinite trees, as well as data-words and tropical automata. Our goal is to show how this notion of unambiguity is so far not well understood, and how embarrassing open questions remain open.

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 "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

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
Nächstes Kapitel Partial Derivative Automaton for Regular Expressions with Shuffle
Fußnoten
1
An automaton is polynomially ambiguous if the number of accepting runs over an input is bounded by a polynomial in the length of the input.
 
2
Other choices are possible, but these distinctions do not make any difference here.
 
3
In the context of trees, two forms of determinism for automata are possible: top-down determinism, i.e., from root to leaves, and bottom-up determinism, i.e., from leaves to root. The former (considered here) is known to be strictly weaker than general automata, even over finite trees. The later does not make real sense over infinite trees, since there may be no leaves.
 
4
A language of infinite trees is bi-unambiguous if it is accepted by a unambiguous infinite tree automaton as well as its complement.
 
5
Strictly speaking, Conjecture 6 is wrong, but has a corrected version.
 
Literatur
1.
Almagor, S., Boker, U., Kupferman, O.: What’s decidable about weighted automata? In: Bultan, T., Hsiung, P.-A. (eds.) ATVA 2011. LNCS, vol. 6996, pp. 482–491. Springer, Heidelberg (2011) CrossRef
2.
Berstel, J.: Transductions and Context-Free Languages. Leitfäden der Angewandten Mathematik und Mechanik [Guides to Applied Mathematics and Mechanics], vol. 38. B.G. Teubner, Stuttgart (1979)
3.
Berstel, J., Sakarovitch, J.: Recent results in the theory of rational sets. In: Gruska, J., Rovan, B., Wiedermann, J. (eds.) Mathematical Foundations of Computer Science (Bratislava 1986). LNCS, vol. 233, pp. 15–28. Springer, Berlin (1986) CrossRef
4.
Bilkowski, M., Skrzypczak, M.: Unambiguity and uniformization problems on infinite trees. In: CSL, volume of LIPIcs, pp. 81–100 (2013)
5.
Bojańczyk, M., Lasota, S.: Fraenkel-mostowski sets with non-homogeneous atoms. In: Finkel, A., Leroux, J., Potapov, I. (eds.) RP 2012. LNCS, vol. 7550, pp. 1–5. Springer, Heidelberg (2012) CrossRef
6.
Cadilhac, M., Finkel, A., McKenzie, P.: Unambiguous constrained automata. Int. J. Found. Comput. Sci. 24(7), 1099–1116 (2013)MATHMathSciNetCrossRef
7.
Carayol, A., Löding, C.: MSO on the infinite binary tree: choice and order. In: Duparc, J., Henzinger, T.A. (eds.) CSL 2007. LNCS, vol. 4646, pp. 161–176. Springer, Heidelberg (2007) CrossRef
8.
Carayol, A., Löding, C., Niwiński, D., Walukiewicz, I.: Choice functions and well-orderings over the infinite binary tree. Cent. Eur. J. Math. 8(4), 662–682 (2010)MATHMathSciNetCrossRef
9.
10.
Colcombet, T.: Forms of determinism for automata. In: Dürr, C., Wilke, T. (eds.) STACS 2012: 29th International Symposium on Theoretical Aspects of Computer Science, Volume 14 of LIPIcs, pp. 1–23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2012)
11.
Colcombet, T., Puppis, G., Skrypczak, M.: Unambiguous register automata. Unpublished
12.
Coste, F., Fredouille, D.C.: Unambiguous automata inference by means of state-merging methods. In: Lavrač, N., Gamberger, D., Todorovski, L., Blockeel, H. (eds.) ECML 2003. LNCS (LNAI), vol. 2837, pp. 60–71. Springer, Heidelberg (2003) CrossRef
13.
14.
Droste, M., Kuske, D.: Weighted automata. To appear in Handbook AutoMathA (2013)
15.
Goldstine, J., Kappes, M., Kintala, C.M.R., Leug, H., Malcher, A., Wotschke, D.: Descriptional complexity of machines with limited resources. J. Univ. Comput. Sci. 8, 193–234 (2002)MATH
16.
17.
Holzer, M., Kutrib, M.: Descriptional complexity of (un)ambiguous finite state machines and pushdown automata. In: Kučera, A., Potapov, I. (eds.) RP 2010. LNCS, vol. 6227, pp. 1–23. Springer, Heidelberg (2010) CrossRef
18.
19.
Kirsten, D., Lombardy, S.: Deciding unambiguity and sequentiality of polynomially ambiguous min-plus automata. In: 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009, 26–28 February 2009, Freiburg, Germany, Proceedings, pp. 589–600 (2009)
20.
Klimann, I., Lombardy, S., Mairesse, J., Prieur, C.: Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton. Theor. Comput. Sci. 327(3), 349–373 (2004)MATHMathSciNetCrossRef
21.
Krob, D.: The equality problem for rational series with multiplicities in the tropical semiring is undecidable. Int. J. Algebra Comput. 4(3), 405–425 (1994)MATHMathSciNetCrossRef
22.
23.
Leung, H.: Separating exponentially ambiguous finite automata from polynomially ambiguous finite automata. SIAM J. Comput. 27(4), 1073–1082 (1998)MATHMathSciNetCrossRef
24.
Leung, H.: Descriptional complexity of NFA of different ambiguity. Int. J. Found. Comput. Sci. 16(5), 975–984 (2005)MATHCrossRef
25.
Leung, H.: Structurally unambiguous finite automata. In: Ibarra, O.H., Yen, H.-C. (eds.) CIAA 2006. LNCS, vol. 4094, pp. 198–207. Springer, Heidelberg (2006) CrossRef
26.
Lombardy, S., Mairesse, J.: Series which are both max-plus and min-plus are unambiguous. RAIRO - Theor. Inf. Appl. 40(1), 1–14 (2006)MATHMathSciNetCrossRef
27.
Lupanov, O.B.: A comparison of two types of finite sources. Problemy Kybernetiki 9, 321–326 (1963)
28.
Meyer, A.R., Fischer, M.J.: Economy of description by automata, grammars, and formal systems. In: Symposium on Switching and Automata Theory, pp. 188–191. IEEE (1971)
29.
Moore, F.R.: On the bounds for state-set size in the proofs of equivalence between deterministic, nondeterministic, and two-way finite automata. IEEE Trans. Comput. 20(10), 1211–1214 (1971)MATHCrossRef
30.
Niwiński, D., Walukiewicz, I.: Ambiguity problem for automata on infinite trees (1996). unpublished
31.
Okhotin, A., Salomaa, K.: Descriptional complexity of unambiguous input-driven pushdown automata. Theor. Comput. Sci. 566, 1–11 (2015)MATHMathSciNetCrossRef
32.
33.
Rabin, M.O.: Decidability of second-order theories and automata on infinite trees. Trans. Amer. Math. Soc. 141, 1–35 (1969)MATHMathSciNet
34.
35.
36.
Sakarovitch, J.: Elements of Automata Theory. Cambridge University Press, Cambridge (2009) MATHCrossRef
37.
Schmidt, E.M.: Succinctness of descriptions of context-free, regular and finite languages. Ph.D. thesis, Cornell University (1977)
38.
Schützenberger, M.-P.: On the definition of a family of automata. Inf. Control 4, 245–270 (1961)MATHCrossRef
39.
Schützenberger, M.-P.: Sur les relations fonctionnelles. In: Brakhage, H. (ed.) GI-Fachtagung 1975. LNCS, vol. 33, pp. 209–213. Springer, Heidelberg (1975)
40.
41.
Stearns, R.E., Hunt III, H.B.: On the equivalence and containment problems for unambiguous regular expressions, grammars, and automata. In: 22nd Annual Symposium on Foundations of Computer Science, Nashville, Tennessee, USA, 28–30 October 1981, pp. 74–81 (1981)
42.
Thomas, W.: Languages, automata and logic. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. 3, pp. 389–455. Springer, New York (1997). Chap. 7 CrossRef
43.
Weber, A.: Decomposing a k-valued transducer into k unambiguous ones. ITA 30(5), 379–413 (1996)MATH
Metadaten
Titel
Unambiguity in Automata Theory
verfasst von
Thomas Colcombet
Copyright-Jahr
2015
Buch
Descriptional Complexity of Formal Systems

Print ISBN: 978-3-319-19224-6

Electronic ISBN: 978-3-319-19225-3

Copyright-Jahr: 2015

DOI
https://doi.org/10.1007/978-3-319-19225-3_1