Róbert Szelepcsényi

Róbert Szelepcsényi

Róbert Szelepcsényi (* 19. August 1966 in Zilina[1]) ist ein slowakischer Informatiker ungarischer Abstammung.

Szelepcsenyi, der Sohn des Musikers Jan Szelepcsenyi (* 1937), bewies als Student an der Comenius-Universität in Bratislava 1987[2] unabhängig von Neil Immerman den Satz von Immerman und Szelepcsényi in der Komplexitätstheorie, wofür beide 1995 den Gödel-Preis erhielten. Der Satz besagt, dass ein nicht-deterministischer Automat zu einem Problem auch das komplementäre Problem lösen kann bei asymptotischen gleichem zur Verfügung stehendem Speicherraum. Für die zeitliche Komplexität ist das Problem ungelöst (2010) und es wird allgemein vermutet, dass ein entsprechender solcher Satz in diesem Fall nicht gilt.

1993 erhielt er einen Master Abschluss an der University of Rochester, war an der Universität Chicago[3] und war Ende der 1990er Jahre an der Slowakischen Akademie der Wissenschaften.[4]

Einzelnachweise

  1. Geburtsdaten nach Milan Strhan, David Daniel (Herausgeber) Slovakia and the slovaks- a concise encyclopedia, Encyclopedial Institute of the Slovak Academy of Sciences 1994
  2. Róbert Szelepcsényi The Method of Forced Enumeration for Nondeterministic Automata, Acta Informatica, Band 26, 1988, S. 279-284
  3. Ehemalige Wissenschaftler in der Abteilung theoretische Informatik Universität Chicago
  4. University of Rochester, Department of Computer Science

Wikimedia Foundation.

Игры ⚽ Нужно решить контрольную?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Róbert Szelepcsényi — (1967) (pronounced|ˈrɔːbert ˈseleptʃeːɲɪ) was a Slovak student of Hungarian descent, member of the Faculty of Mathematics, Physics and Informatics of Comenius University in Bratislava.His results on the closure of nondeterministic space under… …   Wikipedia

  • Róbert Szelepcsényi — (n. 1967) fue un estudiante eslovaco de descendencia húngara, miembro de la Facultad de Matemáticas, Física e Informática de la Universidad Comenius de Bratislava, ubicada en la capital eslovaca Bratislava. Sus resultados en la clausura de… …   Wikipedia Español

  • Immerman–Szelepcsényi theorem — The Immerman–Szelepcsényi Theorem was proven independently by Neil Immerman and Róbert Szelepcsényi in 1987, for which they shared the 1995 Gödel Prize. In its general form the theorem states that NSPACE = co NSPACE. In other words, if a… …   Wikipedia

  • Prix Gödel — Nommé en l honneur du logicien Kurt Gödel, le prix Gödel a été créé en 1992 par l European Association for Theoretical Computer Science (EATCS), l Association for Computing Machinery (ACM) et le groupe de l ACM sur l algorithmique et la théorie… …   Wikipédia en Français

  • Automate linéairement borné — En informatique théorique, et en particulier en théorie des automates, un automate linéairement borné (en anglais linear bounded automaton, abrégé en LBA) est une machine de Turing non déterministe assujettie à des restrictions dans son mode… …   Wikipédia en Français

  • List of multiple discoveries — Main article: Multiple discovery Copernicus …   Wikipedia

  • List of independent discoveries — Independent discoveries in science, termed multiples by Robert K. Merton, are instances in which similar discoveries are made by scientists working independently of each other. [http://books.google.com/books?vid=ISBN0226520714 id=eprv7hMdO IC… …   Wikipedia

  • Géraud Sénizergues — est professeur d informatique à l Université de Bordeaux et membre du Laboratoire bordelais de recherche en informatique. Récipiendaire du Prix Gödel en 2002 pour avoir démontré la décidabilité de l égalité des langages reconnus par des automates …   Wikipédia en Français

  • Johan Håstad — Johan Håstad, né en 1960, est un informaticien théorique suédois connu particulièrement pour son travail sur la complexité algorithmique. Il a reçu le Prix Gödel en 1994 et 2011 et le Doctoral Dissertation Award de l Association for Computing… …   Wikipédia en Français

  • László Lovász — (9 mars 1948, à Budapest ) est un mathématicien connu pour ses travaux en combinatoire et dans la théorie des graphes. Sommaire …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”