Schnittproblem

Schnittproblem

Das Schnittproblem ist ein Problem der theoretischen Informatik. Es ist die Frage, ob die Schnittmenge zweier formaler Sprachen, die durch Grammatiken gegeben sein sollen, leer ist.

Für zwei reguläre Sprachen ist der Schnitt wieder regulär, und damit ist das Problem äquivalent zum Leerheitsproblem, das heißt, dass die Antwort auf die Frage zum Schnittproblem berechenbar ist.

Siehe auch


Wikimedia Foundation.

Игры ⚽ Нужна курсовая?

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

  • Äquivalenzproblem — Als Äquivalenzproblem bezeichnet man in der Theoretischen Informatik das Problem, zu entscheiden, ob zwei formale Definitionen von zwei Sprachen L1 und L2 äquivalent sind, also L1 = L2 gilt. So können die Sprachen durch Grammatiken, oder… …   Deutsch Wikipedia

  • Bo'az Klartag — (hebräisch ‏בועז קלרטג‎; * 25. April 1978) ist ein israelischer Mathematiker. Klartag gewann 1996 eine Silbermedaille auf der Internationalen Mathematikolympiade in Bombay. Er studierte (1997 Bachelor, 2000 Master Abschluss summa cum… …   Deutsch Wikipedia

Share the article and excerpts

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