Feature #27

Convert QDDs to regular expressions for display

Added by Grégoire Sutre over 6 years ago. Updated over 5 years ago.

Status:Closed Start date:07/22/2010
Priority:Normal Due date:10/12/2011
Assignee:Tristan Le Gall % Done:

100%

Category:-
Target version:1.2

Description

The debugging output currently displays recognizable languages of queue contents as lists of states and transitions of the corresponding QDDs. In many cases, regular expressions would be easier to read.

Note: the development of this feature is not worth the effort if QDDs are only displayed for debugging.

History

Updated by Grégoire Sutre over 6 years ago

  • Assignee set to Tristan Le Gall

Updated by Tristan Le Gall over 6 years ago

  • Status changed from New to In Progress
  • % Done changed from 0 to 20

Working on this

Updated by Grégoire Sutre almost 6 years ago

  • Target version set to 1.x

Updated by Tristan Le Gall over 5 years ago

  • % Done changed from 20 to 100

SCM library allow us to display regular expressions insted of QDD, but they are not easier to read and there is no known algorithm to always find "simple" regular expression.

Not: this was implemented months ago. I just forgot to update this feature.

Updated by Tristan Le Gall over 5 years ago

  • Status changed from In Progress to Resolved

Updated by Grégoire Sutre over 5 years ago

  • Status changed from Resolved to In Progress

I find the output difficult to use, but maybe this is because I'm used to the automaton output.

Comparison for simple sets:

  • For { ## }:
      { nodes = 0 => attrvertex = 0; pred = []; succ = [1];;
                1 => attrvertex = 1; pred = [0]; succ = [];;
        arcs = (0,1) => {(##,Top)};
        info = { initial = [|[0]; [1]|];
                 final = [|[0]; [1]|];
                 det=true; min=true; counter=2;
                 partition={(##,Top); (c,Top); (d,Top); (o,Top)}; }; }
    

    versus
      E.{(##,Top)}+{(##,Top)}).E+E.{(##,Top)}+{(##,Top)}
    
  • For { o## }:
      { nodes = 0 => attrvertex = 0; pred = []; succ = [2];;
                1 => attrvertex = 1; pred = [2]; succ = [];;
                2 => attrvertex = 0; pred = [0]; succ = [1];;
        arcs = (0,2) => {(o,Top)};
               (2,1) => {(##,Top)};
        info = { initial = [|[0]; [1]|];
                 final = [|[2]; [1]|];
                 det=true; min=false; counter=3;
                 partition={(##,Top); (c,Top); (d,Top); (o,Top)}; }; }
    

    versus
      (E.{(o,Top)}.{(##,Top)}+{(o,Top)}.{(##,Top)}).E
      +
      E.{(o,Top)}.{(##,Top)}+{(o,Top)}.{(##,Top)}
    
  • For { oc## }:
      { nodes = 0 => attrvertex = 0; pred = []; succ = [1];;
                1 => attrvertex = 0; pred = [0]; succ = [3];;
                2 => attrvertex = 1; pred = [3]; succ = [];;
                3 => attrvertex = 0; pred = [1]; succ = [2];;
        arcs = (0,1) => {(o,Top)};
               (1,3) => {(c,Top)};
               (3,2) => {(##,Top)};
        info = { initial = [|[0]; [2]|];
                 final = [|[3]; [2]|];
                 det=true; min=false; counter=4;
                 partition={(##,Top); (c,Top); (d,Top); (o,Top)}; }; }
    

    versus
      (E.{(o,Top)}.{(c,Top)}.{(##,Top)}
      +
      {(o,Top)}.{(c,Top)}.{(##,Top)}).E
      +
      E.{(o,Top)}.{(c,Top)}.{(##,Top)}
      +
      {(o,Top)}.{(c,Top)}.{(##,Top)}
    
  • For { (oc)^+## }:
      { nodes = 0 => attrvertex = 0; pred = []; succ = [1];;
                1 => attrvertex = 0; pred = [0 2]; succ = [2];;
                2 => attrvertex = 0; pred = [1]; succ = [1 3];;
                3 => attrvertex = 1; pred = [2]; succ = [];;
        arcs = (0,1) => {(o,Top)};
               (1,2) => {(c,Top)};
               (2,1) => {(o,Top)};
               (2,3) => {(##,Top)};
        info = { initial = [|[0]; [3]|];
                 final = [|[2]; [3]|];
                 det=true; min=false; counter=4;
                 partition={(##,Top); (c,Top); (d,Top); (o,Top)}; }; }
    

    versus
      (E.{(o,Top)}.{(c,Top)}.({(o,Top)}.{(c,Top)})*.{(##,Top)}
      +
      {(o,Top)}.{(c,Top)}.({(o,Top)}.{(c,Top)})*.{(##,Top)}).E
      +
      E.{(o,Top)}.{(c,Top)}.({(o,Top)}.{(c,Top)})*.{(##,Top)}
      +
      {(o,Top)}.{(c,Top)}.({(o,Top)}.{(c,Top)})*.{(##,Top)}
    

Updated by Grégoire Sutre over 5 years ago

  • Priority changed from Low to Normal
  • Target version changed from 1.x to 1.2

Updated by Tristan Le Gall over 5 years ago

+ même syntaxe que les expressions régulières du langage d'entrée

Updated by Tristan Le Gall over 5 years ago

  • Status changed from In Progress to Resolved

output regexp have the same syntax as input regexp

Updated by Grégoire Sutre over 5 years ago

  • Due date set to 10/12/2011
  • Status changed from Resolved to Closed

It is not clear at this time how to obtain a better output, i.e., simpler regular expressions. So let's close this issue for now, since it is probably not worth spending more development time on this.

Also available in: Atom PDF