Technopedia Center
PMB University Brochure
Faculty of Engineering and Computer Science
S1 Informatics S1 Information Systems S1 Information Technology S1 Computer Engineering S1 Electrical Engineering S1 Civil Engineering

faculty of Economics and Business
S1 Management S1 Accountancy

Faculty of Letters and Educational Sciences
S1 English literature S1 English language education S1 Mathematics education S1 Sports Education
  • Registerasi
  • Brosur UTI
  • Kip Scholarship Information
  • Performance
  1. Weltenzyklopädie
  2. Quadratfreies Wort – Wikipedia
Quadratfreies Wort – Wikipedia 👆 Click Here!
aus Wikipedia, der freien Enzyklopädie

Unter einem quadratfreien Wort (englisch squarefree word) versteht man in der Theoretischen Informatik ein Wort, das kein (nicht-leeres) Quadrat eines anderen Wortes enthält.

Definition

[Bearbeiten | Quelltext bearbeiten]

Ein Quadrat (englisch square) ist die zweite Potenz eines Wortes, zum Beispiel ( a b c ) 2 = a b c a b c {\displaystyle (abc)^{2}=abcabc} {\displaystyle (abc)^{2}=abcabc}. In der natürlichen Wortbildung werden solche Wörter als reduplizierte Wörter bezeichnet. Beispiele für solche sind Mama, Papa und Bonbon. Ein quadratfreies Wort ist dann ein Wort, das selbst kein nicht-leeres Quadrat enthält. Zum Beispiel ist das Wort abc quadratfrei, Schiff dagegen nicht, weil es das Quadrat ff enthält.

Eine vergleichbare Definition lässt sich auch für andere mathematische Objekte geben, siehe quadratfrei.

Eigenschaften

[Bearbeiten | Quelltext bearbeiten]

Die einzigen binären, d. h. aus nur zwei Buchstaben bestehenden, quadratfreien Wörter sind a, b, ab, ba, aba, bab und das leere Wort. Für ein Alphabet aus mindestens drei Buchstaben gibt es jedoch beliebig lange quadratfreie Wörter.

Die Anzahl der ternären quadratfreien Wörter der Länge n = 1, 2, … ist 1, 3, 6, 12, 18, 30, 42, 60, … (Folge A006156 in OEIS).
Die Anzahl der quaternären quadratfreien Wörter der Länge n = 1, 2, … ist 4, 12, 36, 96, 264, 696, … (Folge A051041 in OEIS).

Literatur

[Bearbeiten | Quelltext bearbeiten]
  • Jean-Paul Allouche, Jeffrey Shallit: Automatic sequences: theory, applications, generalizations. Cambridge University Press, 2003, ISBN 0-521-82332-3 (eingeschränkte Vorschau in der Google-Buchsuche). 

Weblinks

[Bearbeiten | Quelltext bearbeiten]
  • Eric W. Weisstein: Squarefree Word. In: MathWorld (englisch).
Abgerufen von „https://de.teknopedia.teknokrat.ac.id/w/index.php?title=Quadratfreies_Wort&oldid=225267498“
Kategorie:
  • Theorie formaler Sprachen

  • indonesia
  • Polski
  • العربية
  • Deutsch
  • English
  • Español
  • Français
  • Italiano
  • مصرى
  • Nederlands
  • 日本語
  • Português
  • Sinugboanong Binisaya
  • Svenska
  • Українська
  • Tiếng Việt
  • Winaray
  • 中文
  • Русский
Sunting pranala
Pusat Layanan

UNIVERSITAS TEKNOKRAT INDONESIA | ASEAN's Best Private University
Jl. ZA. Pagar Alam No.9 -11, Labuhan Ratu, Kec. Kedaton, Kota Bandar Lampung, Lampung 35132
Phone: (0721) 702022
Email: pmb@teknokrat.ac.id