Können formale Sprachen zum Studium der mathematischen Notation verwendet werden?

8

Frage: Gibt es Einführungstexte in der formalen Sprache oder in der Programmiersprachentheorie, in denen erläutert wird, wie sie auf das Studium der optimalen Notation angewendet werden können?

Insbesondere interessiert mich, was Stapelsprachen, Analysebäume und Indizes sind und wie man vorhersagt, wann eine bestimmte Art von Notation zu exponentieller Redundanz führt.

Ich habe im Grunde keinen Hintergrund in formaler Sprache / Grammatik oder Programmiertheorie, da ich als Hauptfach Mathematik nur Algorithmen und Graphentheorie sowie sehr bescheidene Kenntnisse der Komplexitätstheorie und der Booleschen Funktionen gelernt habe. Wenn also die einzigen Bücher, die dies diskutieren, nicht einleitend sind, wäre ich dankbar für Antworten, die sowohl solche Bücher auflisten, in denen die Explosion der exponentiellen Notation diskutiert wird, als auch einführende Bücher, die sich auf die Bücher vorbereiten, die sich direkt mit meiner Frage befassen.

Kontext: Diese Frage ist in erster Linie von einer Antwort auf Physics.SE inspiriert , die besagt:

Es ist sehr einfach (rigoros) zu beweisen, dass es keine Klammernotation gibt, die Tensorindexkontraktionen reproduziert, da Klammern durch eine Stapelsprache (kontextfreie Grammatik in Chomskys Klassifikation) analysiert werden, während Indizes auf diese Weise nicht analysiert werden können, da sie allgemein sind Grafiken. Die Klammern erzeugen Analysebäume, und Sie haben immer exponentiell viele maximale Bäume in einem Diagramm, sodass die Notation exponentiell redundant ist.

Im weiteren Verlauf der Antwort werden andere Beispiele für das "Aufblasen der exponentiellen Notation" diskutiert, beispielsweise mit Petri-Netzen in der Computerbiologie.

Es gibt auch andere Fälle, in denen die mathematische Notation schwer zu analysieren ist, beispielsweise wie hier erwähnt , wenn Funktionen und Funktionen, die auf das Argument angewendet werden, nicht klar voneinander unterschieden werden. Dies kann besonders verwirrend werden, wenn die Funktion zum Argument und das Argument zur Funktion wird, z . B. hier .

Chill2Macht
quelle
3
Diese Frage klingt sehr weit gefasst. Können Sie es eingrenzen? Können Sie auch Ihre Begriffe definieren? Was genau meinst du mit "optimaler Notation"? Was meinen Sie mit "exponentieller Redundanz" oder "Exponential Notation Blowup"? In welchem ​​Kontext, wenn Sie über Notation sprechen? Notation zum Ausdrücken welcher Art von Aussagen?
DW
3
Außerdem möchten Sie lernen, was Analysebäume usw. sind. Nun, all das zu erklären wäre viel zu lang, um es in einer einzigen Antwort zu liefern. Ich schlage vor, Sie lesen Standardreferenzen (z. B. Lehrbücher, Online-Kursnotizen). Wenn Sie beim Lesen bestimmte Fragen haben, kommen Sie zurück und fragen Sie nach den spezifischen Dingen, bei denen Sie verwirrt sind.
DW
3
Ich denke immer noch, dass es zu breit ist. Es ist besser, eine Referenz für ein einzelnes Thema anzufordern. Wenn Sie nur Referenzen anfordern möchten, die Stapelsprachen, Analysebäume und Indizes abdecken, ist der Rest (über Notationsredundanz usw.) irrelevant und ablenkend und sollte entfernt werden. Zum Schluss und vor allem: Welche Recherchen haben Sie bereits durchgeführt? Welche Referenzen haben Sie bereits gefunden? Warum hast du sie abgelehnt? Welche Kriterien planen Sie für die Bewertung von Referenzen? Welchen Hintergrund haben Sie beispielsweise bereits und auf welchem ​​Niveau sollte sich das Lehrbuch befinden?
DW
3
Grundsätzlich möchten Sie eine Referenz für die formale Sprachtheorie. Ein Standard ist infolab.stanford.edu/~ullman/ialc.html , aber Sie wissen, dass es Universitätskurse gibt, die sich diesem Thema widmen. Das Thema ist sehr weit gefasst, also erwarte es nicht an einem Nachmittag ;-)
Chi
3
Was soll "optimale Notation" sein?
Raphael

Antworten:

6
  1. Die formale Sprachtheorie befasst sich nicht mit der Semantik der Sprache. Das mag seltsam erscheinen, da wir Sprache eher als einen Mechanismus zur Kommunikation von etwas betrachten, aber wenn Sie darüber nachdenken, gibt es (zumindest) zwei Ebenen des Sprachverständnisses: die Oberflächenebene, in der die Sprache ein Strom ist von Lexemen und der zugrunde liegenden Bezeichnungsebene, die mehr oder weniger von der Oberflächendarstellung getrennt ist. (Chomsky stellte eine mittlere "Transformations" -Ebene auf, um einige Einschränkungen bei CFGs zu umgehen, aber das ist hier nicht relevant.) Folglich ist es möglich, "dasselbe" in verschiedenen Sprachen zu sagen. Chomsky ist kein Whorfianer. (Siehe Wikipedia für eine kurze Übersicht mit einigen Referenzen).

  2. Eine kontextfreie Grammatik reicht jedoch nicht aus, um korrekte und falsche Äußerungen zu unterscheiden. Chomsky bot das klassische Beispiel: Farblose Ideen schlafen wütend (was er als US-Amerikaner falsch geschrieben hat). Siehe auch Wikipedia . (Leider hat Wikipedia keine kanadische englische Version.) Die genaue Trennung zwischen syntaktischen und semantischen Fehlern ist schwer, wenn nicht unmöglich abzugrenzen, und es gab erhebliche Debatten über dieses Thema in CS-Bereichen, auf die ich nicht eingehen werde versuche sogar hier zu diskutieren, weil ich dabei immer in Schwierigkeiten gerate. Wir können jedoch eine klassische grammatikalische Regel identifizieren, die in vielen menschlichen Sprachen vorhanden ist: Substantiv / Verb-Übereinstimmung. Ich bin anderer MeinungS.N.P.sichnGV.P.sichnG|N.P.plureinlV.P.plureinlEs ist jedoch leicht zu erkennen, wie die Aufzählung in der Sprache mit komplizierteren Übereinstimmungsregeln (z. B. Geschlecht) außer Kontrolle geraten kann.

  3. N.P.S.N.P.X.V.P.X.X.

  4. Das ist genau das Problem bei Tensorindexkontraktionen. Eine Tensorindexkontraktion stellt besondere Anforderungen an die Verwendung von Indexvariablen: Eine Indexvariable muss genau zweimal verwendet werden. In diesem Fall kann sie nicht auf der linken Seite oder genau einmal, in der sie sich auf der linken Seite befinden muss. Handseite. (Da ich kein Physiker bin, wäre ich versucht, dies dahingehend zusammenzufassen, dass eine Indexvariable insgesamt genau zweimal vorkommen muss. Es gibt jedoch eine semantische Unterscheidung zwischen freien und Platzhaltervariablen, die für das Verständnis der Ausdruck.) Hier gibt es keine einfache endliche Sammlung von Indexvariablen und keine Begrenzung der Anzahl der verwendeten Platzhalter. Darüber hinaus hat das Umbenennen von Platzhaltern keinen Einfluss auf die Semantik, sofern die neuen Namen nicht an anderer Stelle im Ausdruck verwendet werden.

  5. Es ist tatsächlich möglich, die Behauptung, dass kontextfreie Grammatiken keine kontextbezogene Übereinstimmung erfassen können, wie in den vorherigen Beispielen, rigoros zu beweisen. Ich denke, das hat etwas mit dem zu tun, was die zitierte Behauptung behauptet. Je nachdem, wie omnicurious Sie sind, finden Sie es vielleicht interessant, mehr zu lernen, aber ich denke nicht, dass es für die philosophischen oder physischen Einsichten, die Sie zu suchen scheinen, besonders relevant sein wird.

  6. Die anderen verlinkten Artikel über unglückliche Oberflächenformen in mathematischer Notation sind einfach anekdotisch; Keiner von ihnen macht, soweit ich sehen kann, einen tiefen oder sogar oberflächlichen Punkt relevant für die formale Sprachtheorie, so wie der möglicherweise berühmte Witz, dass der Fisch eines Mannes das Poisson eines anderen Mannes ist, nicht einmal vage Aufschluss über die Romantik-Linguistik gibt, aber es ist immer noch lustig (IMO).

Rici
quelle
Das ist interessant - ich wusste nicht, dass es eine solche Überschneidung zwischen Linguistik und Informatik gibt. Dies scheint sehr relevant zu sein, da eines der Dinge, die mich an der Tensor / Einstein-Notation sehr verwirren, die Unterscheidung zwischen freien und Platzhaltervariablen ist, siehe z. B. math.stackexchange.com/questions/2001893/… Für die Aufzeichnung ist das Problem die Antwort Ich erwähnte, dass die Referenzierung in Klammern und nicht in der Indexnotation an sich erfolgt, obwohl ich das Argument selbst nicht verstehe.
Chill2Macht
Das heißt, wenn Klammern "stapelweise analysiert" werden, bedeutet dies, dass sie "Stapelsprachen" sind, was bedeutet, dass sie "Analysebäumen" entsprechen, während die Indexnotation angeblich "allgemeinen Diagrammen" entspricht und die Anzahl der (maximalen) Bäume in einem Diagramm wächst exponentiell mit der Größe des Diagramms, was bedeutet also irgendwie, dass es exponentiell viele Klammerausdrücke gibt, die alle dasselbe bedeuten wie ein einzelner Indexausdruck? Ich weiß, was ein Stapel ist (LIFO) und ich weiß, was ein maximaler Spanning Tree ist, aber ich bin mir nicht sicher, was unter Parsing oder Parsing Tree zu verstehen ist.
Chill2Macht
2
Um eine kontextfreie Grammatik zu analysieren, benötigen Sie einen "Push-Down-Automaten", eine endliche Zustandsmaschine mit einem Stapel. (Sie benötigen auch ein Orakel oder einen Algorithmus oder Geduld, um die richtige Aktion zu finden; der theoretische Automat ist nicht deterministisch.) Daher "Stapelsprache". Das Problem bei Ausdrücken in Klammern sind nicht die Klammern, sondern die Tatsache, dass sie keine Indizes haben.
Rici