476 |
476 |
477 def pruneRexp(r: ARexp, allowableTerms: List[Rexp]) : ARexp = { |
477 def pruneRexp(r: ARexp, allowableTerms: List[Rexp]) : ARexp = { |
478 r match { |
478 r match { |
479 case ASEQ(bs, r1, r2) => |
479 case ASEQ(bs, r1, r2) => |
480 val termsTruncated = allowableTerms.collect(rt => rt match { |
480 val termsTruncated = allowableTerms.collect(rt => rt match { |
481 case SEQ(r1p, r2p) if(r2p == erase(r2)) => r1p |
481 case SEQ(r1p, r2p) if(r2p == erase(r2)) => r1p//if(r2p == erase(r2)) |
482 }) |
482 }) |
483 val pruned : ARexp = pruneRexp(r1, termsTruncated) |
483 val pruned : ARexp = pruneRexp(r1, termsTruncated) |
484 pruned match { |
484 pruned match { |
485 case AZERO => AZERO |
485 case AZERO => AZERO |
486 case AONE(bs1) => fuse(bs ++ bs1, r2) |
486 case AONE(bs1) => fuse(bs ++ bs1, r2) |
487 case pruned1 => ASEQ(bs, pruned1, r2) |
487 case pruned1 => ASEQ(bs, pruned1, r2) |
488 } |
488 } |
489 |
489 |
490 case AALTS(bs, rs) => |
490 case AALTS(bs, rs) => |
491 //allowableTerms.foreach(a => println(shortRexpOutput(a))) |
491 //allowableTerms.foreach(a => println(shortRexpOutput(a))) |
492 val rsp = rs.map(r => pruneRexp(r, allowableTerms)).filter(r => r != AZERO) |
492 val rsp = rs.map(r => |
|
493 pruneRexp(r, allowableTerms) |
|
494 ) |
|
495 .filter(r => r != AZERO) |
493 rsp match { |
496 rsp match { |
494 case Nil => AZERO |
497 case Nil => AZERO |
495 case r1::Nil => fuse(bs, r1) |
498 case r1::Nil => fuse(bs, r1) |
496 case rs1 => AALTS(bs, rs1) |
499 case rs1 => AALTS(bs, rs1) |
497 } |
500 } |
507 |
510 |
508 } |
511 } |
509 |
512 |
510 |
513 |
511 def distinctBy4(xs: List[ARexp], acc: List[Rexp] = Nil) : List[ARexp] = xs match { |
514 def distinctBy4(xs: List[ARexp], acc: List[Rexp] = Nil) : List[ARexp] = xs match { |
|
515 |
512 case Nil => Nil |
516 case Nil => Nil |
513 case x :: xs => |
517 case x :: xs => |
|
518 //assert(acc.distinct == acc) |
514 val erased = erase(x) |
519 val erased = erase(x) |
515 if(acc.contains(erased)) |
520 if(acc.contains(erased)) |
516 distinctBy4(xs, acc) |
521 distinctBy4(xs, acc) |
517 else{ |
522 else{ |
518 val addToAcc = breakIntoTerms(erased).filter(r => !acc.contains(oneSimp(r))) |
523 val addToAcc = breakIntoTerms(erased).filter(r => !acc.contains(oneSimp(r))) |
519 val xp = pruneRexp(x, addToAcc) |
524 //val xp = pruneRexp(x, addToAcc) |
520 xp match { |
525 pruneRexp(x, addToAcc) match { |
521 case AZERO => distinctBy4(xs, addToAcc.map(oneSimp(_)) ::: acc) |
526 case AZERO => distinctBy4(xs, addToAcc.map(oneSimp(_)) ::: acc) |
522 case xPrime => xPrime :: distinctBy4(xs, addToAcc.map(oneSimp(_)) ::: acc) |
527 case xPrime => xPrime :: distinctBy4(xs, addToAcc.map(oneSimp(_)) ::: acc) |
523 } |
528 } |
524 |
529 |
525 } |
530 } |
825 ) |
830 ) |
826 println("the total number of terms is") |
831 println("the total number of terms is") |
827 //println(refSize) |
832 //println(refSize) |
828 println(pderSTAR.size) |
833 println(pderSTAR.size) |
829 |
834 |
830 // val A : Rexp= ("c" | (ONE | "b") ~ "d") ~((ONE).%) |
835 val A : Rexp= ("c" | (ONE | "b") ~ "d") ~((ONE).%) |
831 // val B : Rexp = ((ONE).%) |
836 val B : Rexp = ((ONE).%) |
832 // val C : Rexp = ("d") ~ ((ONE).%) |
837 val C : Rexp = ("d") ~ ((ONE).%) |
833 // val PRUNE_REG : Rexp = (A | B | C) |
838 val PRUNE_REG : Rexp = (C | B | A) |
834 // val APRUNE_REG = internalise(PRUNE_REG) |
839 val APRUNE_REG = internalise(PRUNE_REG) |
835 // val program_solution = pruneRexp(APRUNE_REG, breakIntoTerms(PRUNE_REG)) |
840 // val program_solution = pruneRexp(APRUNE_REG, breakIntoTerms(PRUNE_REG)) |
836 // println("program executes and gives: as disired!") |
841 // println("program executes and gives: as disired!") |
837 // println(shortRexpOutput(erase(program_solution))) |
842 // println(shortRexpOutput(erase(program_solution))) |
838 |
843 val simpedPruneReg = strongBsimp(APRUNE_REG) |
839 for(i <- List( 4, 8, 9, 17, 29) ){// 100, 400, 800, 840, 841, 900 |
844 println(shortRexpOutput(erase(simpedPruneReg))) |
|
845 for(i <- List(100, 900 ) ){// 100, 400, 800, 840, 841, 900 |
840 val prog0 = "a" * i |
846 val prog0 = "a" * i |
841 //println(s"test: $prog0") |
847 //println(s"test: $prog0") |
842 println(s"testing with $i a's" ) |
848 println(s"testing with $i a's" ) |
843 val bd = bdersSimp(prog0, STARREG)//DB |
849 //val bd = bdersSimp(prog0, STARREG)//DB |
844 val sbd = bdersSimpS(prog0, STARREG)//strongDB |
850 val sbd = bdersSimpS(prog0, STARREG)//strongDB |
845 starPrint(erase(sbd)) |
851 starPrint(erase(sbd)) |
846 val subTerms = breakIntoTerms(erase(sbd)) |
852 val subTerms = breakIntoTerms(erase(sbd)) |
847 val subTermsLarge = breakIntoTerms(erase(bd)) |
853 //val subTermsLarge = breakIntoTerms(erase(bd)) |
848 |
854 |
849 println(s"subterms of regex with strongDB: ${subTerms.length}, standard DB: ${subTermsLarge.length}") |
855 println(s"subterms of regex with strongDB: ${subTerms.length}")//, standard DB: ${subTermsLarge.length}") |
850 |
856 |
851 |
857 |
852 |
858 |
853 println("the number of distinct subterms for bsimp with strongDB and standardDB") |
859 println("the number of distinct subterms for bsimp with strongDB") |
854 println(subTerms.distinct.size) |
860 println(subTerms.distinct.size) |
855 println(subTermsLarge.distinct.size) |
861 //println(subTermsLarge.distinct.size) |
856 println("which coincides with the number of PDER terms") |
862 println("which coincides with the number of PDER terms") |
857 |
863 |
858 |
864 |
859 // println(shortRexpOutput(erase(sbd))) |
865 // println(shortRexpOutput(erase(sbd))) |
860 // println(shortRexpOutput(erase(bd))) |
866 // println(shortRexpOutput(erase(bd))) |
861 |
867 |
862 println("pdersize, original, strongSimp, bsimp") |
868 println("pdersize, original, strongSimp") |
863 println(refSize, size(STARREG), asize(sbd), asize(bd)) |
869 println(refSize, size(STARREG), asize(sbd)) |
864 |
870 |
865 val vres = strong_blexing_simp( STARREG, prog0) |
871 val vres = strong_blexing_simp( STARREG, prog0) |
866 println(vres) |
872 println(vres) |
867 } |
873 } |
868 // println(vs.length) |
874 // println(vs.length) |