Find Common word und find common run Methoden

PG A4
Verfügbare Informationen zu "Find Common word und find common run Methoden"

  • Qualität des Beitrags: 0 Sterne
  • Beteiligte Poster: Björn - Steve
  • Forum: PG A4
  • Forenbeschreibung: Forum zur Projektgruppe A4 07/08
  • aus dem Unterforum: Allgemeines
  • Antworten: 4
  • Forum gestartet am: Montag 02.04.2007
  • Sprache: deutsch
  • Link zum Originaltopic: Find Common word und find common run Methoden
  • Letzte Antwort: vor 16 Jahren, 8 Monaten, 16 Tagen, 44 Minuten
  • Alle Beiträge und Antworten zu "Find Common word und find common run Methoden"

    Re: Find Common word und find common run Methoden

    Björn - 09.07.2007, 23:38

    Find Common word und find common run Methoden
    Die Algorithmen in den Klassen OmegaCheckIntersecion,ParityCheckIntersecion,
    RabinCheckIntersection und BuchiCheckIntersection sind fehlerhaft (hätte mir früher auffallen müssen)- werde hier aber nicht ins Detail gehen.
    Auch dort muß Ich mit Tarjan arbeiten (brauche auch hier die größten starken Zusammenhangskomponenten). Aus diesem Grunde werden im Laufe der Woche alle CheckIntersection Klassen auf eine einzige Klasse reduziert werden, und zwar auf OmegaCheckIntersection (um den Code klein zu halten).



    Re: Find Common word und find common run Methoden

    Steve - 10.07.2007, 08:59


    Oha das klingt übel ... und das klingt nach einer Menge Arbeit, die den Bach runter ist. Kannst du denn Teile davon weiter verwenden oder musst du alles neu machen?



    Re: Find Common word und find common run Methoden

    Björn - 10.07.2007, 17:23


    Das ganze ist nicht so schlimm (aber schon etwas ärgerlich), zusammengefügt werden die Klassen weil eh viel doppelt (und dreifach ist- bis zu zehnfach). Der Vorteil ist, dass Ich jetzt nicht mehr zwischen generalisierten Buchi und dem normalen Buchi unterscheiden muss. Und die meisten Methoden waren eh schon in irgendeiner Form in den verschiedenen Klassen also mehraufwand von noch maximal 6 Stunden (sollte also demnächst erst die Korrektheit von solchen Algorithmen beweisen und nicht erst wenn Ich dazu keine passende Literatur finde, drauf los programmieren). Das gute ist mittlerweile habe Ich im Kopf wie Ich für die Algorithmen die Korrektheit (skizziere) bzw. beweise.
    Ich schätze bis Donnerstag bin Ich damit auf jedenfall fertig.

    Um genau zu sein das Problem war: nehme einen Automaten mit 4 Zuständen q0,...,q3. Transitionen: q0-a->q1 ,q1-b->q2,q2-c->q1,
    q1-d->q3,q3-e->q1. Ein Produktautomat egal welchen Typus der aus zwei Automaten mit genau diesen Transitionen und Zuständen besteht, hat genau die selben Zustände und Transitionen.
    Für einen Buchi setzte q3 für den ersten und q2 für den zweiten als akzeptierend. Der Produkt Automat ist damit ein generalisierter buchi automat (die akzeptanzmenge des ersten + die akzeptanzmenge des zweiten) der nicht leer ist, aber nach dem verwendeten Algorithmus wäre er leer gewesen.
    Für den Parity Automat (minimum akzeptanz), setze q0,q1,q2 für den ersten Parity Automat auf 3 und q3 auf 2 für den zweiten Parity Automaton setze q0,q1,q3 auf 3 und q2 auf 2. Auch hier kann man den Produktautomat als generalisierten Buchi Automaten ansehen der genau die selben Worte wie oben akzeptiert.
    Für den Rabin Automat sieht es ähnlich aus - nur ein Rabin Paar jeweils und die E Komponente jeweils leer die F Komponente hat einmal q2 und einmal q3.



    Re: Find Common word und find common run Methoden

    Björn - 11.07.2007, 16:46


    Ok die Klasse ist fertig und auch schon seit heute Nacht im Netz - heißt aber im Augenblick noch OmegaCheckIntersection2. Die anderen klassen werde Ich demnächst entfernen (niedrige Priorität) und auch dafür sorgen dass die DoubleDFS Klassen nicht mehr sowohl im analysis package als auch im operation package stehen. Und auch das Verschieben von ein paar Methoden in der OmegaAnalysis Klasse in die GraphAlgorithms Klasse hat eine niedrige Priorität. - Algorithmen sind auf jetzt jedenfall Korrekt (so dass Ich die Wiki Artikel fertig schreiben kann)- das Testen hat niedrige Priorität wird irgendwann in der Vorlesungsfreien Zeit gemacht (wenn Ich Zeit habe).

    Bis Morgen wird auch definitiv die OmegaAnalysis Klasse fertig sein.
    Und auch hoffentlich auch die Minimierungsmethoden für die Akzeptanzbedingungen (bis auf die für den Streett Automaten).



    Mit folgendem Code, können Sie den Beitrag ganz bequem auf ihrer Homepage verlinken



    Weitere Beiträge aus dem Forum PG A4

    OmegaAutomaton - gepostet von Alina am Mittwoch 05.09.2007
    Info vom Diplomanden - gepostet von KnThrak am Mittwoch 18.04.2007



    Ähnliche Beiträge wie "Find Common word und find common run Methoden"

    am liabstn find i jo in fünfzehnten mai - crazyliljess (Dienstag 11.05.2004)
    find ich schon witzig - bulldozer (Freitag 13.07.2007)
    +++ 4.Runde +++ - eazyberny (Mittwoch 23.07.2008)
    ICH FIND DAS FORUM COOL - tobi (Montag 16.07.2007)
    Wanted - Ben (Samstag 13.09.2008)
    Find ich witzig - Anonymous (Donnerstag 24.11.2005)
    Hehe ich find den cool! - farina (Freitag 30.07.2004)
    where to find merchandise in Germany? - plastickarma (Freitag 17.08.2007)
    On The Road To Find Out - Butterfly (Samstag 21.07.2007)
    find ich super hier - Anonymous (Dienstag 17.08.2004)