Levi lemma

Levi lemma

In mathematics, in the area of combinatorics, the Levi lemma states that, for all strings "u", "v","x" and "y", if "uv"="xy", then there exists a string "w" such that either

:"uw=x" and "v"="wy"

or

:"u"="xw" and "wv"="y"

That is, there is a string "w" that is "in the middle", and can be grouped to one side or the other. [Mathematical Foundations of Computer Science 2004 Jiří Fiala, Václav Koubek, Jan Kratochvíl ISBN 3540228233, 9783540228233]

The above is known as the Levi lemma for strings; the lemma can occur in a more general form in graph theory and in monoid theory; for example, there is a more general Levi lemma for traces.

ee also

*String operations
*String functions (programming)
*Transfinite strings

References


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Satz von Beppo Levi — Der Satz von der monotonen Konvergenz, auch Satz von Beppo Levi genannt (nach Beppo Levi), ist ein wichtiger Satz aus der Maß und Integrationstheorie, einem Teilgebiet der Mathematik. Er trifft eine Aussage darüber, unter welchen Voraussetzungen… …   Deutsch Wikipedia

  • Gauss's lemma (Riemannian geometry) — In Riemannian geometry, Gauss s lemma asserts that any sufficiently small sphere centered at a point in a Riemannian manifold is perpendicular to every geodesic through the point. More formally, let M be a Riemannian manifold, equipped with its… …   Wikipedia

  • List of mathematics articles (L) — NOTOC L L (complexity) L BFGS L² cohomology L function L game L notation L system L theory L Analyse des Infiniment Petits pour l Intelligence des Lignes Courbes L Hôpital s rule L(R) La Géométrie Labeled graph Labelled enumeration theorem Lack… …   Wikipedia

  • Trace monoid — In mathematics and computer science, a trace is a set of strings, wherein certain letters in the string are allowed to commute, but others are not. It generalizes the concept of a string, by not forcing the letters to always be in a fixed order,… …   Wikipedia

  • String operations — In computer science, in the area of formal language theory, frequent use is made of a variety of string functions; however, the notation used is different from that used on computer programming, and some commonly used functions in the theoretical …   Wikipedia

  • Differential geometry of surfaces — Carl Friedrich Gauss in 1828 In mathematics, the differential geometry of surfaces deals with smooth surfaces with various additional structures, most often, a Riemannian metric. Surfaces have been extensively studied from various perspectives:… …   Wikipedia

  • Liste mathematischer Sätze — Inhaltsverzeichnis A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A Satz von Abel Ruffini: eine allgemeine Polynomgleichung vom …   Deutsch Wikipedia

  • Determinant — This article is about determinants in mathematics. For determinants in epidemiology, see Risk factor. In linear algebra, the determinant is a value associated with a square matrix. It can be computed from the entries of the matrix by a specific… …   Wikipedia

  • Maxwell'sche Gleichungen — Die vier maxwellschen Gleichungen beschreiben die Erzeugung von elektrischen und magnetischen Feldern durch Ladungen und Ströme, sowie die Wechselwirkung zwischen diesen beiden Feldern, die bei zeitabhängigen Feldern als Zeitentwicklung in… …   Deutsch Wikipedia

  • Maxwell-Gleichung — Die vier maxwellschen Gleichungen beschreiben die Erzeugung von elektrischen und magnetischen Feldern durch Ladungen und Ströme, sowie die Wechselwirkung zwischen diesen beiden Feldern, die bei zeitabhängigen Feldern als Zeitentwicklung in… …   Deutsch Wikipedia

Share the article and excerpts

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