\documentclass[a4paper,11pt]{article} %%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%% %% NON USARE MACRO CON MATH perché 4ht NON converte correttamente! %% $\mathup{qR}_3^*$ deve essere scritto direttamente! %%%%%%%%%%%%%%%%% \usepackage{lib/common_definitions} %### \begin{document} \title{CSTN Benchmarks} \author{Roberto Posenato\\ Dipartimento di Informatica\\ Università degli Studi di Verona, Italy} \date{2018-02-21} \ifpdf \maketitle \fi \section{Introduction} \blankfootnote{The original version of this document can be download at \url{http://profs.scienze.univr.it/~posenato/software/cstnu/tex/benchmarks.pdf}} We prepared two benchmarks for testing CSTN Dynamic Consistency (DC) checking algorithm: \href{http://profs.scienze.univr.it/~posenato/software/benchmarks/CSTNBenchmark2016.tgz}{CSTNBenchmark2016}, \href{http://profs.scienze.univr.it/~posenato/software/benchmarks/CSTNBenchmark2018.tgz}{CSTNBenchmark2018}, and \href{http://profs.scienze.univr.it/~posenato/software/benchmarks/CSTNUBenchmark2018.tgz}{CSTNUBenchmark2018}. CSTNBenchmark2016 and CSTNBenchmark2018 benchmarks contain CSTN instances while CSTNUBenchmark2018 contains CSTNU instances. All instances were determined transforming random workflows generated by the ATAPI Toolset~\cite{Lanz14b}. We considered a random workflow generator as source of random CSTN(U) instances for having a closer approximation to real-world instances and also for generating networks that are more difficult to check than those created haphazardly. The ATAPI toolset produces random workflows according to different input parameters that govern the number of tasks, the probability of having parallel (AND)\slash alternative (XOR) branches, the probability of inter-task temporal constraints, and so on. In particular, the ATAPIS toolset builds a workflow instance in two phases. In the first phase, it prepares the structure of the network in a ricorsive way starting from a pool of $N$ blocks representing tasks. At each cycle, randomly it removes two blocks from the pool and in a casual way decides how to combine them using an AND/XOR/SEQUENTIAL connector. The resulting block is then added to the pool. The generation phase ends when there is only one block in the pool. The probability to choose an AND or an XOR connector can be given as input ($P_A$, and $P_C$ parameters). Temporal constraints are added in the second phase considering some parameters that can be given as input. The following parameter-values were determined after some experiments where we tried to discover a good mix of them in order to guarantee not trivial consistent\slash not consistent instances. The chosen values were: each task duration is a subrange of $[2, 30]$, set randomly using a beta distribution, a connector duration has always range $[1, 10]$, delay between sequential tasks is a subrange of $[1, 25]$ chosen using a beta distribution, delay between a connector and a task is fixed to $[1, 100]$, and inter-activity temporal constraint between any pair of activities (i.e, tasks or connectors) is set with probability $0.2$. In case that a inter-activity temporal constraint is set, its range is a casual subrange of the [min distance, max distance] between the two activities, where min and max distances are calculated by the tool. As regards CSTN benchmarks, the general method used for building them was the following. First, workflow graphs were randomly generated by setting the number of tasks to $N$, the probability for parallel branches to $P_A$, the probability for alternative branches to $P_C$. The values of $N$, $P_A$, and $P_C$ were varied according to the test type, discussed in more detail below. Second, each workflow graph was translated into an equivalent CSTN using the method proposed in~\cite{CombiGMP14}. Task durations were represented as ordinary constraints in CSTN instances. As regards CSTNU benchmark, the method used was similar to the above one for CSTN benchmarks. The only difference was that all task durations were translated as contingent links in corresponding CSTNU instances. In the following section more details about the benchmarks are given. \section{CSTNBenchmark2016} This benchmark is composed of four sub-benchmarks (named as \textit{benchmarks} in papers~\cite{time2015,HunsbergerP16Icaps,CairoEtalTime2017}). Each sub-benchmark is composed of two sets: one set of DC CSTN instances and one set of NOT DC ones. Each sub-benchmark, characterized by a number $N$, is called \textbf{Size$N$} and contains CSTN instances (DC\slash NOT DC) generated by random workflow ones having $N$ tasks, $k$ XOR connectors (= propositions in CSTN) and a variable number of AND connectors. The probability for parallel branches $P_A$ was fixed to 0.2 as well as the probability for alternative branches $P_C$. The following table summarizes the main characteristics of all sub-benchmarks: \begin{center} \begin{tabular}{rrrrr} \hline \textbf{benchmark}: & \textbf{size10} & \textbf{size20} & \textbf{size30} & \textbf{size40}\\ \hline \#tasks: & 10 & 20 & 30 & 40 \\ $k$=\#XOR: & 3 & 5 & 7 & 9\\% & \rule{0in}{0.2in} \#CSTN-nodes: & 45-59 &79-95& 123-135&159-175\\ \hline \end{tabular} \end{center} For each sub-benchmark, there are at least 60 dynamically consistent CSTNs and 20 non-dynamically consistent CSTNs. Since the original ATAPIS toolset allows one to fix only the probability of AND\slash XOR connectors, it was necessary to run the toolset a huge number of times for obtaining the instances with the above characteristics. \smallskip Different workflow graphs with the same number of tasks may translate into CSTNs of different sizes due to different numbers of AND connectors in the workflows. This fact represented the main weakness of this benchmark. For example, even if for $N=10$ and $k=3$ there are 60 DC instances, such instances are CSTN instances with different order (=\#nodes). Few of them have the same order and this fact represents a limitation when an evaluation of DC execution time with respect of the CSTN order is required. \section{CSTNBenchmark2018} The structure of this benchmark is equals to the CSTNBenchmark2016 benchmark one: four sub-benchmarks with two sets for each. The main difference is in the number of instances and in their structures. After an important modification of ATAPI Toolset source code, it was possible to give as input also the number of XOR\slash AND connectors that a random workflow instance must have. Therefore, it was possible to build sets of more uniform instances where the randomness could decide how to mix components and constraints but not their quantities. It is possible to show that the relation between workflow component quantities and CSTN order is $5+2N+6k+4j$, where $N$ is the number of tasks, $k$ the number of XOR connectors, and $j$ the number of AND connectors. Therefore, for each possible planned combinatios of \#task-\#XOR-\#AND, it was possible to generate randomly 50 DC and 50 NOT DC instances. The following table summarizes the characteristics of each sub-benchmark. \begin{center} \begin{tabular}{@{} l >{\RaggedLeft\arraybackslash}p{1.4cm} >{\RaggedLeft\arraybackslash}p{1.5cm} >{\RaggedLeft\arraybackslash}p{1.5cm} >{\RaggedLeft\arraybackslash}p{1.3cm} c >{\RaggedLeft\arraybackslash}p{1.2cm} @{}} \hline \textbf{Group} &\textbf{Bench mark} & \textbf{instance indexes} & \textbf{\# activities} & \textbf{\#XOR} & \textbf{\#AND} & \textbf{CSTN order}\\ \hline Size010-3 & B10-3-0 & 000-049 & 10 & 3 & 0 & 43\\ & B10-3-1 & 050-099 & 10 & 3 & 1 & 47\\ & B10-3-2 & 100-149 & 10 & 3 & 2 & 51\\ & B10-3-3 & 150-199 & 10 & 3 & 3 & 55\\ & B10-3-4 & 200-249 & 10 & 3 & 4 & 59\\ \hline Size020-5 & B20-5-0 & 000-029 & 20 & 5 & 0 & 75\\ & B20-5-1 & 030-059 & 20 & 5 & 1 & 79 \\ & B20-5-2 & 060-099 & 20 & 5 & 2 & 83\\ & B20-5-3 & 090-119 & 20 & 5 & 3 & 87\\ & B20-5-4 & 120-149 & 20 & 5 & 4 & 91\\ \hline Size030-7 & B30-7-0 & 000-029 & 30 & 7 & 0 & 107\\ & B30-7-1 & 030-059 & 30 & 7 & 1 & 111\\ & B30-7-2 & 060-089 & 30 & 7 & 2 & 115\\ & B30-7-3 & 090-119 & 30 & 7 & 3 & 119\\ & B30-7-4 & 120-149 & 30 & 7 & 4 & 123\\ \hline Size040-9 & B40-9-0 & 000-029 & 40 & 9 & 0 & 139\\ & B40-9-1 & 030-059 & 40 & 9 & 1 & 143\\ & B40-9-2 & 060-089 & 40 & 9 & 2 & 147\\ & B40-9-3 & 090-119 & 40 & 9 & 3 & 151\\ & B40-9-4 & 120-149 & 40 & 9 & 4 & 155\\ \hline \end{tabular} \end{center} The total number of CSTN instances is $2000$, $1000$ DC and $1000$ not DC, divided in 4 main group, in turn divided in other 4 groups having 50 DC and NOT DC instances. \subsection{Experimental Evaluation} Currently, there are 10 different DC checking algorithms for CSTN: \begin{enumerate} \item \textbf{Std}: it checks the DC property considering the standard semantics~\cite{HunsbergerP16Icaps}. \item \textbf{Std-woNL}: it checks the DC property considering the standard semantics on equivalent CSTN where there is no node labels~\cite{CairoEtalTime2017}. \item \boldmath{$\epsilon$}: it checks the DC property considering the $\epsilon$ semantics~\cite{HunsbergerP16Icaps}. %4HT non converte epsilon in mathbf! \item \textbf{$\epsilon$-woNL}: it checks the DC property considering the $\epsilon$ semantics on equivalent CSTN where there is no node labels~\cite{CairoEtalTime2017}. \item \textbf{$\epsilon$-3R}: it checks the DC property considering the $\epsilon$ semantics and using only rules \LP, $\mathup{qR}_0$, and $\mathup{qR}_3^*$. \item \textbf{$\epsilon$-3R-woNL}: it checks the DC property considering the $\epsilon$ semantics on equivalent CSTN where there is no node labels and using only rules \LP, $\mathup{qR}_0$, and $\mathup{qR}_3^*$. \item \textbf{IR}: it checks the DC property considering the instantaneous reaction semantics~\cite{HunsbergerP16Icaps}. \item \textbf{IR-woNL}: it checks the DC property considering the instantaneous reaction semantics on equivalent CSTN where there is no node labels~\cite{CairoEtalTime2017}. \item \textbf{IR-3R}: it checks the DC property considering the instantaneous reaction semantics and using only rules \LP, $\mathup{qR}_0$, and $\mathup{qR}_3^*$. \item \textbf{IR-3R-woNL}: it checks the DC property considering the instantaneous reaction semantics on equivalent CSTN where there is no node labels and using only rules $\LP$, $\mathup{qR}_0$, and $\mathup{qR}_3^*$. \end{enumerate} In the following we propose two diagrams that show the comparation of such algorithm versions in the CSTNBenchmark2018 benchmark. All versions of DC checking algorithm were developted in Java~8 and run on an Oracle JVM~8 in a Linux machine with an AMD Opteron 4334 CPU (12 cores) and 64GB of RAM. The execution times were collected by a Java program (\texttt{Checker}, proposed in our package) that allows one to determine the average execution time---and its standard deviation---of one DC checking algorithm applied to a set of CSTN instances. Moreover, \texttt{Checker} allows one to require to the operating system to allocate one or more CPU cores for executing the algorithm in sequential/parallel way on files without the reschedule of threads in different cores during the execution. We experienced that even if AMD Opteron 4334 has 12 cores, the best performances were obtained only when all checks are made by only \textbf{one} core. We believe that the memory-accesses by cores represent a bottleneck that limits the overall performance. Therefore, all the data presented in this section were obtained using only one core (parameter \texttt{-nCPUs 1}). The parameters for the Oracle Java Virtual Machine~1.8.0\_144 were: \texttt{-d64}, \texttt{-Xmx6g}, \texttt{-Xms6g}, \texttt{-XX:NewSize=3g}, \texttt{-XX:MaxNewSize=3g}, \texttt{-XX:+UseG1GC}, \texttt{-Xnoclassgc}, and \texttt{-XX:+AggressiveOpts}. The first diagram shows the average execution times with respect to the order of CSTN instances of eight versions of DC checking algorithm when instances are dynamic consistent. Each drawn value is the sample average $\bar{X}_{50}$ of execution times obtained considering the fifty instances of the relative benchmark. In details, $\bar{X}_{50}=\frac{\sum_{i=1}^{50} X_i}{50}$ where $X_i$ is the average execution time obtained executing 3 times the algorithm on instance having index $i$\footnote{The determination of all values required to execute the DC checking for 24 000 times, 83.18 hours.}. The error bar of each drawn value represents $2.010$ times the standard error of the mean, $\frac{S_{50}}{\sqrt{50}}$, where $S_{50}$ is the corrected sample standard deviation, $S_{50}= \sqrt{\frac{\sum_{i=1}^{50} (X_i-\bar{X}_{50})^2}{49}}$. Value $2.010$ is the Student's $t$ distribution value with 49 degrees of freedom. Therefore, the error bar represents a 95\% confidence interval for the average execution time of the algorithm on instances having the main characteristics of the considered benchmark. \pgfplotstableset{format=inline,col sep=semicolon,row sep=newline} %SIZE 10 \pgfplotstableread{ n; x; p; y; yerr 50; 43; 3; 1.124200E-01; 5.713686E-02 50; 47; 3; 1.120467E-01; 5.062574E-02 50; 51; 3; 1.180600E-01; 5.454756E-02 50; 55; 3; 1.376933E-01; 6.484060E-02 50; 59; 3; 1.277800E-01; 5.789010E-02 }\bTenStd \pgfplotstableread{ n; x; p; y; yerr 50; 43; 3; 1.397467E-01; 6.040789E-02 50; 47; 3; 1.487267E-01; 5.977291E-02 50; 51; 3; 1.601800E-01; 7.687193E-02 50; 55; 3; 1.882600E-01; 8.866013E-02 50; 59; 3; 1.696533E-01; 7.361236E-02 }\bTenStdwoNL \pgfplotstableread{ n; x; p; y; yerr 50; 43; 3; 1.074267E-01; 5.202442E-02 50; 47; 3; 1.150000E-01; 5.021884E-02 50; 51; 3; 1.200667E-01; 5.375914E-02 50; 55; 3; 1.384533E-01; 6.349152E-02 50; 59; 3; 1.297133E-01; 5.802044E-02 }\bTenEpsilon \pgfplotstableread{ n; x; c; p; y; yerr 50; 43; 0; 3; 1.868600E-01; 8.270263E-02 50; 47; 0; 3; 2.074800E-01; 8.594314E-02 50; 51; 0; 3; 2.234000E-01; 1.049916E-01 50; 55; 0; 3; 2.578600E-01; 1.194129E-01 50; 59; 0; 3; 2.379900E-01; 1.053748E-01 }\bTenEpsilonwoNL \pgfplotstableread{ n; x; p; y; yerr 50; 43; 3; 9.370000E-02; 4.496409E-02 50; 47; 3; 9.783333E-02; 3.991904E-02 50; 51; 3; 1.033733E-01; 3.983581E-02 50; 55; 3; 1.192000E-01; 4.667876E-02 50; 59; 3; 1.150867E-01; 4.530045E-02 }\bTenEpsilonR \pgfplotstableread{ n; x; p; y; yerr 50; 43; 3; 9.626667E-02; 4.129107E-02 50; 47; 3; 1.037067E-01; 3.787601E-02 50; 51; 3; 1.108400E-01; 3.813904E-02 50; 55; 3; 1.313533E-01; 5.073882E-02 50; 59; 3; 1.216933E-01; 4.285523E-02 }\bTenEpsilonRwoNL \pgfplotstableread{ n; x; c; p; y; yerr 50; 43; 0; 3; 1.741900E-01; 7.213210E-02 50; 47; 0; 3; 1.867500E-01; 7.249576E-02 50; 51; 0; 3; 2.023600E-01; 7.169920E-02 50; 55; 0; 3; 2.229600E-01; 8.372653E-02 50; 59; 0; 3; 2.084600E-01; 7.691865E-02 }\bTenEpsilonIR \pgfplotstableread{ n; x; p; y; yerr 50; 43; 3; 1.114133E-01; 5.501270E-02 50; 47; 3; 1.130600E-01; 5.138979E-02 50; 51; 3; 1.198600E-01; 5.478745E-02 50; 55; 3; 1.424333E-01; 6.745746E-02 50; 59; 3; 1.292333E-01; 5.912381E-02 }\bTenIR \pgfplotstableread{ n; x; c; p; y; yerr 50; 43; 0; 3; 1.492800E-01; 6.792449E-02 50; 47; 0; 3; 1.566200E-01; 6.337639E-02 50; 51; 0; 3; 1.685500E-01; 7.764619E-02 50; 55; 0; 3; 2.281600E-01; 1.102486E-01 50; 59; 0; 3; 2.328100E-01; 1.048633E-01 }\bTenIRwoNL \pgfplotstableread{ n; x; p; y; yerr 50; 43; 3; 8.801333E-02; 4.042433E-02 50; 47; 3; 9.436667E-02; 3.876467E-02 50; 51; 3; 1.003867E-01; 3.832640E-02 50; 55; 3; 1.162000E-01; 4.661727E-02 50; 59; 3; 1.106867E-01; 4.380556E-02 }\bTenIRR \pgfplotstableread{ n; x; p; y; yerr 50; 43; 3; 9.614000E-02; 4.046992E-02 50; 47; 3; 1.043933E-01; 3.837774E-02 50; 51; 3; 1.112867E-01; 3.848185E-02 50; 55; 3; 1.273800E-01; 4.540870E-02 50; 59; 3; 1.224800E-01; 4.328072E-02 }\bTenIRRwoNL %SIZE 20 \pgfplotstableread{ n; x; p; y; yerr 50; 75; 5; 1.413333E+00; 8.411374E-01 50; 79; 5; 1.598393E+00; 1.402712E+00 50; 83; 5; 1.757740E+00; 1.289269E+00 50; 87; 5; 1.039673E+00; 1.159078E+00 50; 91; 5; 9.129533E-01; 9.073689E-01 }\bTwentyStd \pgfplotstableread{ n; x; p; y; yerr 50; 75; 5; 2.018707E+00; 1.322616E+00 50; 79; 5; 2.203353E+00; 1.709251E+00 50; 83; 5; 2.571533E+00; 1.940135E+00 50; 87; 5; 1.667473E+00; 1.934453E+00 50; 91; 5; 1.381620E+00; 1.287241E+00 }\bTwentyStdwoNL \pgfplotstableread{ n; x; p; y; yerr 50; 75; 5; 1.451487E+00; 8.832201E-01 50; 79; 5; 1.625280E+00; 1.397331E+00 50; 83; 5; 1.786013E+00; 1.313082E+00 50; 87; 5; 1.051793E+00; 1.154293E+00 50; 91; 5; 9.285000E-01; 9.154440E-01 }\bTwentyEpsilon \pgfplotstableread{ n; x; c; p; y; yerr 50; 75; 0; 5; 1.918490E+00; 1.265360E+00 50; 79; 0; 5; 2.020470E+00; 1.487202E+00 50; 83; 0; 5; 2.495190E+00; 2.041843E+00 50; 87; 0; 5; 1.588200E+00; 1.744819E+00 50; 91; 0; 5; 1.345650E+00; 1.200835E+00 }\bTwentyEpsilonwoNL \pgfplotstableread{ n; x; p; y; yerr 50; 75; 5; 8.018067E-01; 4.034952E-01 50; 79; 5; 8.699267E-01; 6.410694E-01 50; 83; 5; 9.091200E-01; 5.692082E-01 50; 87; 5; 6.029467E-01; 5.860499E-01 50; 91; 5; 5.281267E-01; 4.115798E-01 }\bTwentyEpsilonR \pgfplotstableread{ n; x; p; y; yerr 50; 75; 5; 9.893867E-01; 5.159875E-01 50; 79; 5; 1.150893E+00; 8.835910E-01 50; 83; 5; 1.161607E+00; 7.508684E-01 50; 87; 5; 8.013067E-01; 7.760730E-01 50; 91; 5; 6.882867E-01; 5.129977E-01 }\bTwentyEpsilonRwoNL \pgfplotstableread{ n; x; c; p; y; yerr 50; 75; 0; 5; 1.079770E+00; 5.002895E-01 50; 79; 0; 5; 1.160990E+00; 7.433829E-01 50; 83; 0; 5; 1.240610E+00; 7.005113E-01 50; 87; 0; 5; 8.614400E-01; 6.997012E-01 50; 91; 0; 5; 7.865400E-01; 5.281109E-01 }\bTwentyEpsilonIR \pgfplotstableread{ n; x; p; y; yerr 50; 75; 5; 1.433127E+00; 8.668855E-01 50; 79; 5; 1.629400E+00; 1.453930E+00 50; 83; 5; 1.790907E+00; 1.326592E+00 50; 87; 5; 1.056240E+00; 1.188285E+00 50; 91; 5; 9.265533E-01; 9.388889E-01 }\bTwentyIR \pgfplotstableread{ n; x; c; p; y; yerr 50; 75; 0; 5; 2.005210E+00; 1.280479E+00 50; 79; 0; 5; 2.253500E+00; 1.703853E+00 50; 83; 0; 5; 2.578050E+00; 1.904996E+00 50; 87; 0; 5; 1.682320E+00; 1.890390E+00 50; 91; 0; 5; 1.409870E+00; 1.274060E+00 }\bTwentyIRwoNL \pgfplotstableread{ n; x; p; y; yerr 50; 75; 5; 9.533933E-01; 5.076181E-01 50; 79; 5; 1.059867E+00; 8.374357E-01 50; 83; 5; 1.089220E+00; 7.181152E-01 50; 87; 5; 7.114467E-01; 7.460642E-01 50; 91; 5; 6.131467E-01; 5.080560E-01 }\bTwentyIRR \pgfplotstableread{ n; x; p; y; yerr 50; 75; 5; 1.066987E+00; 5.684580E-01 50; 79; 5; 1.241673E+00; 9.735599E-01 50; 83; 5; 1.262707E+00; 8.452710E-01 50; 87; 5; 8.607667E-01; 8.465077E-01 50; 91; 5; 7.395000E-01; 5.594223E-01 }\bTwentyIRRwoNL %SIZE 30 \pgfplotstableread{ n; x; p; y; yerr 50; 107; 7; 7.671387E+00; 5.963476E+00 50; 111; 7; 8.080887E+00; 7.502360E+00 50; 115; 7; 7.243620E+00; 6.132803E+00 50; 119; 7; 3.235573E+00; 5.632874E+00 50; 123; 7; 5.185487E+00; 5.668531E+00 }\bThirtyStd \pgfplotstableread{ n; x; p; y; yerr 50; 107; 7; 1.740918E+01; 3.642311E+01 50; 111; 7; 1.772535E+01; 2.587496E+01 50; 115; 7; 1.214562E+01; 1.046847E+01 50; 119; 7; 7.269287E+00; 1.454207E+01 50; 123; 7; 9.755660E+00; 1.043466E+01 }\bThirtyStdwoNL \pgfplotstableread{ n; x; p; y; yerr 50; 107; 7; 7.444427E+00; 5.785186E+00 50; 111; 7; 7.911907E+00; 7.473737E+00 50; 115; 7; 7.032473E+00; 5.834342E+00 50; 119; 7; 3.167547E+00; 5.447382E+00 50; 123; 7; 5.025353E+00; 5.342786E+00 }\bThirtyEpsilon \pgfplotstableread{ n; x; c; p; y; yerr 50; 107; 0; 7; 1.280334E+01; 1.576678E+01 50; 111; 0; 7; 1.423207E+01; 1.682508E+01 50; 115; 0; 7; 1.168123E+01; 1.171378E+01 50; 119; 0; 7; 6.591010E+00; 1.267446E+01 50; 123; 0; 7; 8.977450E+00; 9.563257E+00 }\bThirtyEpsilonwoNL \pgfplotstableread{ n; x; p; y; yerr 50; 107; 7; 5.297453E+00; 4.216731E+00 50; 111; 7; 6.062687E+00; 4.772459E+00 50; 115; 7; 5.024380E+00; 3.834357E+00 50; 119; 7; 2.093107E+00; 2.678792E+00 50; 123; 7; 3.390513E+00; 3.142762E+00 }\bThirtyEpsilonR \pgfplotstableread{ n; x; p; y; yerr 50; 107; 7; 5.020647E+00; 3.875314E+00 50; 111; 7; 5.866660E+00; 4.639125E+00 50; 115; 7; 4.679667E+00; 3.302802E+00 50; 119; 7; 2.129467E+00; 2.455840E+00 50; 123; 7; 3.205167E+00; 2.678448E+00 }\bThirtyEpsilonRwoNL \pgfplotstableread{ n; x; c; p; y; yerr 50; 107; 0; 7; 6.444790E+00; 5.214478E+00 50; 111; 0; 7; 7.510170E+00; 6.072543E+00 50; 115; 0; 7; 5.806000E+00; 4.064851E+00 50; 119; 0; 7; 2.647520E+00; 3.116512E+00 50; 123; 0; 7; 3.859950E+00; 3.124102E+00 }\bThirtyEpsilonIR \pgfplotstableread{ n; x; p; y; yerr 50; 107; 7; 9.234420E+00; 7.491244E+00 50; 111; 7; 9.945200E+00; 9.167898E+00 50; 115; 7; 8.809913E+00; 7.814152E+00 50; 119; 7; 4.195653E+00; 8.163998E+00 50; 123; 7; 6.620613E+00; 7.415235E+00 }\bThirtyIR \pgfplotstableread{ n; x; c; p; y; yerr 50; 107; 0; 7; 2.468744E+01; 5.531632E+01 50; 111; 0; 7; 2.522661E+01; 3.843078E+01 50; 115; 0; 7; 1.670373E+01; 1.530173E+01 50; 119; 0; 7; 1.012404E+01; 2.160875E+01 50; 123; 0; 7; 1.389182E+01; 1.528601E+01 }\bThirtyIRwoNL \pgfplotstableread{ n; x; p; y; yerr 50; 107; 7; 4.172833E+00; 3.045361E+00 50; 111; 7; 4.594927E+00; 3.382615E+00 50; 115; 7; 3.960000E+00; 2.776745E+00 50; 119; 7; 1.674760E+00; 1.906630E+00 50; 123; 7; 2.650873E+00; 2.289961E+00 }\bThirtyIRR \pgfplotstableread{ n; x; p; y; yerr 50; 107; 7; 7.348393E+00; 6.647504E+00 50; 111; 7; 8.828140E+00; 8.008093E+00 50; 115; 7; 6.581820E+00; 5.273288E+00 50; 119; 7; 2.984467E+00; 4.086251E+00 50; 123; 7; 4.623720E+00; 4.277523E+00 }\bThirtyIRRwoNL %SIZE 40 \pgfplotstableread{ n; x; p; y; yerr 50; 139; 9; 6.142759E+01; 1.362770E+02 50; 143; 9; 4.733783E+01; 4.821572E+01 50; 147; 9; 7.683246E+01; 1.506763E+02 50; 151; 9; 1.703771E+01; 2.463194E+01 50; 155; 9; 2.072059E+01; 2.368368E+01 }\bFortyStd \pgfplotstableread{ n; x; p; y; yerr 50; 139; 9; 2.004595E+02; 3.650069E+02 50; 143; 9; 2.481500E+02; 4.573231E+02 50; 147; 9; 2.248740E+02; 4.097517E+02 50; 151; 9; 9.757314E+01; 2.428014E+02 50; 155; 9; 9.038653E+01; 1.261328E+02 }\bFortyStdwoNL \pgfplotstableread{ n; x; p; y; yerr 50; 139; 9; 4.657009E+01; 5.771702E+01 50; 143; 9; 4.918434E+01; 5.886433E+01 50; 147; 9; 6.990227E+01; 1.075633E+02 50; 151; 9; 1.760875E+01; 2.523416E+01 50; 155; 9; 2.157204E+01; 2.466318E+01 }\bFortyEpsilon \pgfplotstableread{ n; x; c; p; y; yerr 50; 139; 0; 9; 1.220220E+02; 1.661958E+02 50; 143; 0; 9; 1.575103E+02; 2.268653E+02 50; 147; 0; 9; 1.797279E+02; 3.331094E+02 50; 151; 0; 9; 7.759049E+01; 1.736233E+02 50; 155; 0; 9; 7.606051E+01; 1.035707E+02 }\bFortyEpsilonwoNL \pgfplotstableread{ n; x; p; y; yerr 50; 139; 9; 3.362095E+01; 3.746203E+01 50; 143; 9; 3.544370E+01; 2.869841E+01 50; 147; 9; 5.095237E+01; 7.348899E+01 50; 151; 9; 1.512881E+01; 2.214412E+01 50; 155; 9; 1.764607E+01; 2.156705E+01 }\bFortyEpsilonR \pgfplotstableread{ n; x; p; y; yerr 50; 139; 9; 5.052773E+01; 5.679916E+01 50; 143; 9; 5.723898E+01; 6.959646E+01 50; 147; 9; 7.639311E+01; 1.401546E+02 50; 151; 9; 2.452874E+01; 3.806911E+01 50; 155; 9; 3.055789E+01; 3.996289E+01 }\bFortyEpsilonRwoNL \pgfplotstableread{ n; x; c; p; y; yerr 50; 139; 0; 9; 4.068032E+01; 3.949055E+01 50; 143; 0; 9; 4.053959E+01; 3.073787E+01 50; 147; 0; 9; 6.031022E+01; 1.011979E+02 50; 151; 0; 9; 1.818904E+01; 2.629523E+01 50; 155; 0; 9; 2.236237E+01; 2.778149E+01 }\bFortyEpsilonIR \pgfplotstableread{ n; x; p; y; yerr 50; 139; 9; 7.219806E+01; 1.642881E+02 50; 143; 9; 5.450244E+01; 5.595485E+01 50; 147; 9; 8.840485E+01; 1.714954E+02 50; 151; 9; 1.999837E+01; 3.042801E+01 50; 155; 9; 2.405199E+01; 2.810105E+01 }\bFortyIR \pgfplotstableread{ n; x; c; p; y; yerr 50; 139; 0; 9; 2.725532E+02; 4.719433E+02 50; 143; 0; 9; 3.213533E+02; 5.200259E+02 50; 147; 0; 9; 2.929922E+02; 4.476115E+02 50; 151; 0; 9; 1.456916E+02; 3.931881E+02 50; 155; 0; 9; 1.359826E+02; 1.846573E+02 }\bFortyIRwoNL \pgfplotstableread{ n; x; p; y; yerr 50; 139; 9; 3.431129E+01; 3.877769E+01 50; 143; 9; 3.668491E+01; 3.031365E+01 50; 147; 9; 5.212619E+01; 7.556105E+01 50; 151; 9; 1.540287E+01; 2.255488E+01 50; 155; 9; 1.788527E+01; 2.154799E+01 }\bFortyIRR \pgfplotstableread{ n; x; p; y; yerr 50; 139; 9; 3.318351E+01; 3.169798E+01 50; 143; 9; 3.380343E+01; 2.513424E+01 50; 147; 9; 5.090781E+01; 9.835386E+01 50; 151; 9; 1.504721E+01; 2.059331E+01 50; 155; 9; 1.913810E+01; 2.449817E+01 }\bFortyIRRwoNL \newcommand{\yerrstd}{2.010*\thisrow{yerr}/(\thisrow{n}^.5)} \begin{center} % \captionsetup{justification=justified} % \subfloat[Benchmark $N=10,|\calp|=3$.\label{SubFig:N10}]{ % \begin{subfigure}[b]{.45\linewidth}\centering% \ 44 \leq n \leq 59, \ \pgfplotsset{every axis y label/.append style={inner sep=1pt,outer sep=1pt}} \noindent \begin{tikzpicture} %% %%This diagram requires pgfplots version 1.15 to be compiled without errors. %% \begin{axis}[ normalsize, title=\textbf{Consistent Instances}, % title style={at={(0.5,-.2)}}, % height=8 cm, % width=.48\textwidth, % X xlabel={$n$}, xlabel style={at={(ticklabel cs:1)}, anchor=south west}, minor x tick num=1, xmajorgrids=true, % Y ylabel={execution time}, y unit=seconds, % minor y tick num=1,%not applied for ymode=log yminorgrids=true, ymajorgrids=true, ymode=log, log basis y=10, log ticks with fixed point, % ytick=\empty, % extra y ticks={2,5,10, 20, 30, 60, 120}, % extra y tick labels={30s, 1, 5, 10, 20, 30}, % % ylabel shift=-5pt, % LEGEND cycle multi list={colorbrewer}, legend style={at={(1.05,1)},anchor=north west},%legend pos=north west, legend columns=1, % legend entries={ {Std}, {Std-woNL}, {$\epsilon$}, {$\epsilon$-woNL}, {$\epsilon$-woNL-3R}, {IR}, {IR-woNL}, {IR-woNL-3R}, } ] % % % SIZE 10 \draw[<->] (axis cs:43,.07) -- (axis cs:59,.07) node[timeLabel,below,pos=.5] {Size010-3}; \addlegendentry{Std}; \addplot[Std,error bars/.cd, y dir=both, y explicit]%STD table [x=x, y=y,y error expr=\yerrstd] {\bTenStd}; \addlegendentry{Std-woNL}; \addplot[StdwoNL,error bars/.cd, y dir=both, y explicit]%STD woNL table [x=x, y=y,y error expr=\yerrstd] {\bTenStdwoNL}; \addlegendentry{\textepsilon}; %\textepsilon is necessary for SVG format!!! \addplot[Epsilon,error bars/.cd, y dir=both, y explicit]%epsilon table [x=x, y=y,y error expr=\yerrstd] {\bTenEpsilon}; \addlegendentry{\textepsilon-woNL}; %\textepsilon is necessary for SVG format!!! \addplot[EpsilonwoNL,error bars/.cd, y dir=both, y explicit]%epsilon table [x=x, y=y,y error expr=\yerrstd] {\bTenEpsilonwoNL}; \addlegendentry{\textepsilon-3R};%\textepsilon is necessary for SVG format!!! \addplot[Epsilon3R,error bars/.cd, y dir=both, y explicit]%epsilon 3R table [x=x, y=y,y error expr=\yerrstd] {\bTenEpsilonR}; \addlegendentry{\textepsilon-3R-woNL};%\textepsilon is necessary for SVG format!!! \addplot[Epsilon3RwoNL,error bars/.cd, y dir=both, y explicit]%epsilon woNL 3R table [x=x, y=y,y error expr=\yerrstd] {\bTenEpsilonRwoNL}; \addlegendentry{\textepsilon2IR-woNL};%\textepsilon is necessary for SVG format!!! \addplot[Epsilon2IR,error bars/.cd, y dir=both, y explicit] table [x=x, y=y,y error expr=\yerrstd] {\bTenEpsilonIR}; \addlegendentry{IR}; \addplot[IR,error bars/.cd, y dir=both, y explicit]%IR table [x=x, y=y,y error expr=\yerrstd] {\bTenIR}; \addlegendentry{IR-woNL}; \addplot[IRwoNL,error bars/.cd, y dir=both, y explicit]%IR table [x=x, y=y,y error expr=\yerrstd] {\bTenIRwoNL}; \addlegendentry{IR-3R}; \addplot[IR3R,error bars/.cd, y dir=both, y explicit]%IR table [x=x, y=y,y error expr=\yerrstd] {\bTenIRR}; \addlegendentry{IR-3R-woNL}; \addplot[IR3RwoNL,error bars/.cd, y dir=both, y explicit]%IR table [x=x, y=y,y error expr=\yerrstd] {\bTenIRRwoNL}; % % % SIZE 20 \draw[<->] (75,.3) -- (91,.3) node[timeLabel,below,pos=.5] {Size020-5}; % \addlegendentry{Std}; \addplot[Std,error bars/.cd, y dir=both, y explicit]%STD table [x=x, y=y,y error expr=\yerrstd] {\bTwentyStd}; \addplot[StdwoNL,error bars/.cd, y dir=both, y explicit]%STD woNL table [x=x, y=y,y error expr=\yerrstd] {\bTwentyStdwoNL}; \addplot[Epsilon,error bars/.cd, y dir=both, y explicit]%epsilon table [x=x, y=y,y error expr=\yerrstd] {\bTwentyEpsilon}; \addplot[EpsilonwoNL,error bars/.cd, y dir=both, y explicit]%epsilon table [x=x, y=y,y error expr=\yerrstd] {\bTwentyEpsilonwoNL}; \addplot[Epsilon3R,error bars/.cd, y dir=both, y explicit]%epsilon 3R table [x=x, y=y,y error expr=\yerrstd] {\bTwentyEpsilonR}; \addplot[Epsilon3RwoNL,error bars/.cd, y dir=both, y explicit]%epsilon 3R woNL table [x=x, y=y,y error expr=\yerrstd] {\bTwentyEpsilonRwoNL}; \addplot[Epsilon2IR,error bars/.cd, y dir=both, y explicit] table [x=x, y=y,y error expr=\yerrstd] {\bTwentyEpsilonIR}; \addplot[IR,error bars/.cd, y dir=both, y explicit]%IR table [x=x, y=y,y error expr=\yerrstd] {\bTwentyIR}; \addplot[IRwoNL,error bars/.cd, y dir=both, y explicit]%IR table [x=x, y=y,y error expr=\yerrstd] {\bTwentyIRwoNL}; \addplot[IR3R,error bars/.cd, y dir=both, y explicit]%IR 3R table [x=x, y=y,y error expr=\yerrstd] {\bTwentyIRR}; \addplot[IR3RwoNL,error bars/.cd, y dir=both, y explicit]%IR 3R woNL table [x=x, y=y,y error expr=\yerrstd] {\bTwentyIRRwoNL}; % % % SIZE 30 \draw[<->] (107,1) -- (123,1) node[timeLabel,below,pos=.5] {Size030-7}; % \addlegendentry{Std}; \addplot[Std,error bars/.cd, y dir=both, y explicit]%STD table [x=x, y=y,y error expr=\yerrstd] {\bThirtyStd}; % \addlegendentry{Std-woNL}; \addplot[StdwoNL,error bars/.cd, y dir=both, y explicit]%STD woNL table [x=x, y=y,y error expr=\yerrstd] {\bThirtyStdwoNL}; \addplot[Epsilon,error bars/.cd, y dir=both, y explicit]%epsilon table [x=x, y=y,y error expr=\yerrstd] {\bThirtyEpsilon}; \addplot[EpsilonwoNL,error bars/.cd, y dir=both, y explicit]%epsilon table [x=x, y=y,y error expr=\yerrstd] {\bThirtyEpsilonwoNL}; \addplot[Epsilon3R,error bars/.cd, y dir=both, y explicit]%epsilon 3R table [x=x, y=y,y error expr=\yerrstd] {\bThirtyEpsilonR}; \addplot[Epsilon3RwoNL,error bars/.cd, y dir=both, y explicit]%epsilon 3R woNL table [x=x, y=y,y error expr=\yerrstd] {\bThirtyEpsilonRwoNL}; \addplot[Epsilon2IR,error bars/.cd, y dir=both, y explicit] table [x=x, y=y,y error expr=\yerrstd] {\bThirtyEpsilonIR}; \addplot[IR,error bars/.cd, y dir=both, y explicit]%IR table [x=x, y=y,y error expr=\yerrstd] {\bThirtyIR}; \addplot[IRwoNL,error bars/.cd, y dir=both, y explicit]%IRwoNL table [x=x, y=y,y error expr=\yerrstd] {\bThirtyIRwoNL}; \addplot[IR3R,error bars/.cd, y dir=both, y explicit]%IR 3R table [x=x, y=y,y error expr=\yerrstd] {\bThirtyIRR}; \addplot[IR3RwoNL,error bars/.cd, y dir=both, y explicit]%IR 3R woNL table [x=x, y=y,y error expr=\yerrstd] {\bThirtyIRRwoNL}; % % % SIZE 40 \draw[<->] (axis cs:139,8) -- (axis cs:155,8) node[timeLabel,below,pos=.5] {Size040-9}; % \addlegendentry{Std}; \addplot[Std,error bars/.cd, y dir=both, y explicit]%STD table [x=x, y=y,y error expr=\yerrstd] {\bFortyStd}; % \addlegendentry{Std-woNL}; \addplot[StdwoNL,error bars/.cd, y dir=both, y explicit]%STD woNL table [x=x, y=y,y error expr=\yerrstd] {\bFortyStdwoNL}; \addplot[Epsilon,error bars/.cd, y dir=both, y explicit]%epsilon table [x=x, y=y,y error expr=\yerrstd] {\bFortyEpsilon}; \addplot[EpsilonwoNL,error bars/.cd, y dir=both, y explicit]%epsilon woNL table [x=x, y=y,y error expr=\yerrstd] {\bFortyEpsilonwoNL}; \addplot[Epsilon3R,error bars/.cd, y dir=both, y explicit]%epsilon 3R table [x=x, y=y,y error expr=\yerrstd] {\bFortyEpsilonR}; \addplot[Epsilon3RwoNL,error bars/.cd, y dir=both, y explicit]%epsilon 3R woNL table [x=x, y=y,y error expr=\yerrstd] {\bFortyEpsilonRwoNL}; \addplot[Epsilon2IR,error bars/.cd, y dir=both, y explicit] table [x=x, y=y,y error expr=\yerrstd] {\bFortyEpsilonIR}; \addplot[IR,error bars/.cd, y dir=both, y explicit]%IR table [x=x, y=y,y error expr=\yerrstd] {\bFortyIR}; \addplot[IRwoNL,error bars/.cd, y dir=both, y explicit]%IRwoNL table [x=x, y=y,y error expr=\yerrstd] {\bFortyIRwoNL}; \addplot[IR3R,error bars/.cd, y dir=both, y explicit]%IR 3R table [x=x, y=y,y error expr=\yerrstd] {\bFortyIRR}; \addplot[IR3RwoNL,error bars/.cd, y dir=both, y explicit]%IR 3R woNL table [x=x, y=y,y error expr=\yerrstd] {\bFortyIRRwoNL}; % \node[draw,rounded corners,timeLabel,anchor=west,text width=2.5cm,font=\tiny] (l) at (120, 1) {Circled values are lower bound because they contain timeout values.}; \end{axis} \end{tikzpicture} \end{center} Even if the diagram is quite crowded, it is possible to see (and data confirm) that the DC checking algorithm has the worst performance when it has to apply IR semantics without node labels. There is no a unique algorithm version that shows the best performance in all benchmarks. \textbf{IR-3R} version has the best performance in benchmarks of group Size010-3 and Size030-7. In group Size020-5, the version \textbf{\textepsilon-3R} showed the best performance in all benchmarks, while \textbf{IR-3R-woNL} showed the best performance in group Size040-9. We noted that the experimental data contain outliers, instances for which the execution time is quite far from the average execution time. Outliers represent hard instances for the DC checking problem (the problem was shown to be PSPACE-complete). The following figures show the distribution of execution time of \textbf{IR-3R} in terms of quartiles in the groups Size030-7 and Size040-9. Each box has the lower edge equal to the first quartile ($Q_1$) while the upper edge equal to the third one ($Q_3$). The edge inside each box represents the median of the sample. Horizontal edges outside a box represent the \textit{whiskers}. The lower whisker value is the smallest data value which is larger than $Q_1-1.5\cdot \mathrm{IQR}$, where IQR is the \textit{inter–quartile–range}, i.e., $Q_3-Q_1$. The upper whisker is the largest data value which is smaller than $Q_3+1.5\cdot \mathrm{IQR}$. Diamonds above the upper whisker represent the data value outliers. The diamond in the highest position in each set of data represents the worst case value of the benchmark. Diamond inside a box represents the average value of the benchmark. \smallskip \begin{center} \noindent \begin{tikzpicture} \begin{axis}[ title=\textbf{Execution time distribution of \textbf{IR-3R} in Size030 group}, boxplot/draw direction=y, xlabel={$n$}, xlabel style={at={(ticklabel cs:1)}, anchor=south west}, xtick={1,2,3,4,5}, xticklabels={107, 111, 115, 119, 123}, % xmajorgrids=true, ylabel={execution time}, y unit=seconds, % axis y line=left, enlarge y limits, ymajorgrids, boxplot/average=auto, ] \addplot[IR3R,boxplot] %107 nodes table[y index=0,col sep=semicolon] { 7.293333E-01; 1.803667E+00; 4.273333E-01; 1.174667E+01; 6.610000E+00; 4.046667E+00; 2.408000E+00; 6.130667E+00; 1.573667E+00; 2.533667E+00; 6.060000E+00; 2.018333E+00; 9.996333E+00; 6.995667E+00; 4.759667E+00; 6.573333E-01; 1.026400E+01; 5.606333E+00; 6.054000E+00; 2.207333E+00; 7.184667E+00; 1.584333E+00; 1.968000E+00; 6.302333E+00; 1.781333E+00; 1.190333E+00; 5.756667E-01; 2.570000E+00; 1.387000E+00; 4.557667E+00; 6.806333E+00; 6.181667E+00; 2.811667E+00; 2.534333E+00; 2.712667E+00; 2.352000E+00; 1.369267E+01; 4.095000E+00; 8.037667E+00; 1.849000E+00; 1.912000E+00; 3.720000E-01; 5.425667E+00; 6.644000E+00; 5.061667E+00; 2.096667E+00; 4.061000E+00; 2.591333E+00; 2.480333E+00; 5.194000E+00; }; \addplot[IR3R,boxplot] %111nodes table[y index=0,col sep=semicolon] { 3.246333E+00; 5.488000E+00; 2.615333E+00; 2.706667E-01; 8.901333E+00; 3.147000E+00; 8.933333E-01; 4.926667E-01; 6.328667E+00; 3.139667E+00; 8.266333E+00; 3.860333E+00; 2.029667E+00; 2.072667E+00; 6.213667E+00; 9.746333E+00; 1.408333E+00; 1.232100E+01; 3.484667E+00; 3.196667E+00; 1.899667E+00; 4.118333E+00; 6.441000E+00; 1.717333E+00; 8.196000E+00; 4.816000E+00; 6.377000E+00; 2.749333E+00; 8.790333E+00; 2.425333E+00; 2.490000E-01; 4.320667E+00; 2.484667E+00; 1.883667E+00; 5.089667E+00; 2.982333E+00; 2.291333E+00; 7.812667E+00; 4.650000E-01; 6.430000E-01; 1.038467E+01; 3.865667E+00; 6.206333E+00; 9.195667E+00; 5.479333E+00; 7.439000E+00; 1.599567E+01; 2.942000E+00; 3.018667E+00; 2.344333E+00; 4.440000E-01; }; \addplot[IR3R,boxplot] %115nodes table[y index=0,col sep=semicolon] { 4.440000E-01; 6.321667E+00; 6.693333E-01; 3.063000E+00; 7.705333E+00; 4.644333E+00; 2.148000E+00; 1.026067E+01; 1.748667E+00; 6.101667E+00; 1.707667E+00; 2.043000E+00; 5.160667E+00; 1.977000E+00; 4.723333E-01; 7.562333E+00; 9.509000E+00; 1.483333E+00; 1.547000E+00; 4.160000E-01; 4.828333E+00; 5.975667E+00; 3.262000E+00; 9.321333E+00; 4.416667E-01; 4.216000E+00; 3.941333E+00; 3.431000E+00; 2.775333E+00; 3.801333E+00; 6.180000E+00; 6.133000E+00; 3.686333E+00; 1.551667E+00; 1.245200E+01; 5.445667E+00; 5.440333E+00; 1.028667E+00; 1.431667E+00; 3.218667E+00; 2.253333E+00; 5.110333E+00; 1.368000E+00; 3.987000E+00; 1.805333E+00; 4.773000E+00; 3.324000E+00; 6.127667E+00; 4.738667E+00; 9.656667E-01; }; \addplot[IR3R,boxplot] %119nodes table[y index=0,col sep=semicolon] { 4.820000E-01; 1.610333E+00; 1.362333E+00; 1.555333E+00; 4.772333E+00; 1.906000E+00; 7.320000E-01; 2.972000E+00; 9.240000E-01; 1.125833E+01; 5.038667E+00; 4.126667E-01; 4.893333E-01; 1.833000E+00; 4.823333E-01; 1.784667E+00; 3.643333E-01; 3.716667E+00; 1.016667E+00; 6.626667E-01; 4.407000E+00; 3.250000E-01; 3.403333E-01; 1.364333E+00; 6.493333E-01; 4.686667E-01; 3.856667E-01; 2.071333E+00; 4.462667E+00; 1.915667E+00; 3.040000E-01; 5.880000E-01; 1.377667E+00; 1.590333E+00; 2.137000E+00; 3.973333E-01; 2.900000E-01; 3.659667E+00; 3.840000E-01; 4.806667E-01; 2.194667E+00; 3.190000E-01; 2.803333E-01; 3.230000E-01; 1.756000E+00; 2.940000E+00; 2.592000E+00; 3.436667E-01; 1.546667E+00; 4.683333E-01; }; \addplot[IR3R,boxplot] %123nodes table[y index=0,col sep=semicolon] { 4.405000E+00; 1.932333E+00; 9.230000E-01; 1.273333E+00; 5.588000E+00; 1.951000E+00; 2.466000E+00; 3.930000E-01; 2.352333E+00; 5.543333E-01; 5.805333E+00; 3.060000E-01; 2.370333E+00; 2.941667E+00; 6.317667E+00; 3.983333E-01; 3.231000E+00; 2.309667E+00; 8.127333E+00; 3.500000E-01; 2.603333E+00; 7.273333E-01; 2.835333E+00; 5.963333E+00; 4.117333E+00; 9.960000E-01; 2.747333E+00; 2.494000E+00; 3.556667E-01; 1.791333E+00; 6.502667E+00; 2.471000E+00; 4.223333E-01; 1.248000E+00; 4.300333E+00; 4.563333E-01; 4.683333E-01; 6.973333E-01; 5.823333E-01; 3.583333E+00; 5.936667E-01; 2.028333E+00; 1.033867E+01; 1.607667E+00; 6.380000E+00; 4.806333E+00; 2.486333E+00; 3.345333E+00; 3.316667E-01; 1.267000E+00; }; \end{axis} \end{tikzpicture} \end{center} \begin{center}\noindent \begin{tikzpicture} \begin{axis}[ title=\textbf{Execution time distribution of \textbf{IR-3R} in Size040 group}, boxplot/draw direction=y, xlabel={$n$}, xlabel style={at={(ticklabel cs:1)}, anchor=south west}, xtick={1,2,3,4,5}, xticklabels={139, 143, 147, 151, 155}, % xmajorgrids=true, ylabel={execution time}, y unit=seconds, % axis y line=left, enlarge y limits, ymajorgrids, boxplot/average=auto, ] \addplot[IR3R,boxplot] %139nodes table[y index=0,col sep=semicolon] { 1.248267E+01; 2.877433E+01; 5.991400E+01; 1.112667E+01; 3.070033E+01; 3.564200E+01; 1.052333E+01; 3.515100E+01; 2.148333E+00; 2.376843E+02; 1.536333E+01; 2.709933E+01; 1.890333E+00; 2.110867E+01; 1.285600E+01; 3.156767E+01; 3.356567E+01; 4.349333E+00; 3.101500E+01; 5.951300E+01; 3.342633E+01; 1.503700E+01; 2.266167E+01; 5.136000E+01; 1.817967E+01; 2.313033E+01; 4.760433E+01; 5.752500E+01; 3.562900E+01; 2.575767E+01; 1.921633E+01; 2.619667E+00; 1.431900E+01; 2.256400E+01; 3.818167E+01; 2.068667E+00; 5.609633E+01; 3.363500E+01; 5.351000E+01; 3.820567E+01; 1.088400E+01; 1.162167E+01; 3.191333E+00; 1.947367E+01; 6.224667E+00; 2.672733E+01; 1.393383E+02; 1.078830E+02; 3.071300E+01; 4.630500E+01; }; \addplot[IR3R,boxplot] %143 nodes table[y index=0,col sep=semicolon] { 1.372567E+01; 3.850733E+01; 6.603767E+01; 2.250800E+01; 4.205700E+01; 1.123683E+02; 3.741133E+01; 1.989600E+01; 9.140500E+01; 9.238000E+00; 1.173357E+02; 1.475033E+01; 6.256867E+01; 6.602767E+01; 2.540800E+01; 6.112767E+01; 5.881733E+01; 2.875800E+01; 4.151000E+00; 2.888600E+01; 9.838000E+00; 2.647233E+01; 1.048740E+02; 5.198400E+01; 2.674000E+00; 6.245567E+01; 3.551867E+01; 1.237700E+01; 1.221100E+01; 3.324800E+01; 5.123467E+01; 2.444967E+01; 1.243533E+01; 2.190067E+01; 5.096300E+01; 8.213000E+00; 2.079233E+01; 5.292433E+01; 1.649867E+01; 2.352833E+01; 6.928333E+00; 1.756367E+01; 2.284567E+01; 2.378733E+01; 1.509500E+01; 1.196430E+02; 1.855033E+01; 1.036500E+01; 3.436367E+01; 9.526000E+00; }; \addplot[IR3R,boxplot] %147 nodes table[y index=0,col sep=semicolon] { 3.855467E+01; 4.831733E+01; 1.541100E+01; 1.288133E+02; 2.983933E+01; 6.970800E+01; 1.430100E+01; 4.779300E+01; 1.933500E+01; 7.062667E+00; 4.294533E+01; 2.018100E+01; 5.604567E+01; 3.826467E+01; 1.653600E+01; 6.118467E+01; 6.317800E+01; 2.545000E+00; 7.737667E+01; 9.037900E+01; 2.974967E+01; 2.719400E+01; 7.615100E+01; 2.111667E+01; 8.211100E+01; 2.554967E+01; 2.720333E+00; 9.999333E+00; 2.931700E+01; 9.665767E+01; 4.587333E+01; 5.010167E+01; 3.703033E+01; 6.056433E+01; 6.042867E+01; 3.197000E+01; 2.500100E+01; 1.547367E+01; 2.985900E+01; 1.373233E+01; 2.212867E+01; 8.853267E+01; 1.395600E+01; 9.059767E+01; 3.655500E+01; 7.436267E+01; 2.155500E+01; 2.644533E+01; 3.585633E+01; 5.379480E+02; }; \addplot[IR3R,boxplot] %151 nodes table[y index=0,col sep=semicolon] { 2.008667E+00; 4.672800E+01; 4.186667E+00; 5.147000E+00; 6.089333E+00; 3.052767E+01; 1.026667E+00; 7.283333E-01; 3.243733E+01; 6.180000E-01; 1.664333E+01; 1.022333E+00; 1.809833E+01; 9.251333E+00; 2.017000E+00; 5.686667E-01; 2.436233E+01; 6.563333E-01; 2.951900E+01; 1.217667E+00; 2.418233E+01; 9.256667E-01; 2.187000E+00; 4.674033E+01; 2.265667E+00; 5.714333E+00; 1.237333E+00; 5.754667E+00; 1.001833E+01; 4.028667E+00; 5.079400E+01; 8.883000E+00; 6.666667E-01; 5.832667E+00; 5.962667E+00; 5.396000E+00; 6.420000E-01; 6.288000E+00; 4.506633E+01; 3.049500E+01; 6.140000E-01; 1.492100E+01; 2.410000E+00; 2.252333E+00; 4.233133E+01; 5.578833E+01; 4.029000E+00; 1.264397E+02; 2.233167E+01; 3.091333E+00; }; \addplot[IR3R,boxplot] %155 nodes table[y index=0,col sep=semicolon] { 1.670333E+00; 5.086333E+00; 2.512000E+00; 4.374000E+01; 6.876000E+00; 6.085667E+00; 6.656000E+00; 3.849333E+00; 9.285000E+00; 4.033667E+01; 2.435333E+00; 6.809133E+01; 4.709300E+01; 6.324000E+00; 5.842933E+01; 4.977333E+00; 2.929133E+01; 6.017000E+00; 7.815667E+00; 2.435733E+01; 3.971067E+01; 5.373333E-01; 5.633333E+00; 7.786667E-01; 9.890000E-01; 1.116733E+01; 2.287033E+01; 6.501333E+00; 2.358000E+00; 6.556667E-01; 3.252300E+01; 1.334467E+01; 7.715667E+00; 2.292033E+01; 2.113367E+01; 2.448200E+01; 1.167763E+02; 4.863333E-01; 2.051667E+00; 2.777800E+01; 7.366667E-01; 1.417167E+01; 6.223000E+00; 2.369400E+01; 1.278600E+01; 1.539733E+01; 3.533767E+01; 2.869967E+01; 2.157667E+00; 1.371733E+01; }; \end{axis} \end{tikzpicture} \end{center} The previous two diagrams show clearly that there are few instances that bias the value of sample average in a relevant way. \medskip The following diagram shows the average execution times with respect to the order of CSTN of some versions of the DC checking algorithm when instances are not consistent. \begin{center} \noindent \begin{tikzpicture} %% %%This diagram requires pgfplots version 1.15 to be compiled without errors. %% \begin{axis}[ normalsize, title=\textbf{Not Consistent Instances}, % title style={at={(0.5,-.2)}}, % height=8 cm, % width=.48\textwidth, % X xlabel={$n$}, xlabel style={at={(ticklabel cs:.999)}, anchor=south west}, minor x tick num=1, xmajorgrids=true, % Y ylabel={execution time}, y unit=seconds, % minor y tick num=1,%not applied for ymode=log yminorgrids=true, ymajorgrids=true, ymode=log, log basis y=10, log ticks with fixed point, % ytick=\empty, % extra y ticks={2,5,10, 20, 30, 60, 120}, % extra y tick labels={30s, 1, 5, 10, 20, 30}, % % ylabel shift=-5pt, % LEGEND legend style={at={(1.05,1)},anchor=north west},%legend pos=north west, legend columns=1, ] % SIZE 10 \draw[<->] (axis cs:43,.008) -- (axis cs:59,.008) node[timeLabel,below,pos=.5] {Size010-3}; \addlegendentry{Std}; \addplot[Std,error bars/.cd, y dir=both, y explicit]%STD table [col sep=semicolon,x=x, y=y, y error expr=\yerrstd] { n; x; p; y; yerr 50; 43; 3; 2.199333E-02; 3.185508E-02 50; 47; 3; 1.817333E-02; 2.821285E-02 50; 51; 3; 3.372000E-02; 4.707024E-02 50; 55; 3; 3.584667E-02; 3.816424E-02 50; 59; 3; 2.762000E-02; 2.634732E-02 }; \addlegendentry{Std-woNL}; \addplot[StdwoNL,error bars/.cd, y dir=both, y explicit]%STD woNL table [col sep=semicolon,x=x, y=y, y error expr=\yerrstd] { n; x; p; y; yerr 50; 43; 3; 2.445333E-02; 3.990492E-02 50; 47; 3; 2.446000E-02; 4.475491E-02 50; 51; 3; 4.493333E-02; 6.913561E-02 50; 55; 3; 4.587333E-02; 5.101962E-02 50; 59; 3; 3.426000E-02; 3.390331E-02 }; \addlegendentry{\textepsilon}; %\textepsilon is necessary for SVG format!!! \addplot[Epsilon,error bars/.cd, y dir=both, y explicit]%epsilon table [col sep=semicolon,x=x, y=y, y error expr=\yerrstd] { n; x; p; y; yerr 50; 43; 3; 2.186000E-02; 3.407482E-02 50; 47; 3; 1.975333E-02; 3.218546E-02 50; 51; 3; 3.446667E-02; 4.923736E-02 50; 55; 3; 3.612000E-02; 3.947104E-02 50; 59; 3; 2.760667E-02; 2.642799E-02 }; \addlegendentry{IR}; \addplot[IR,error bars/.cd, y dir=both, y explicit]%ir table [col sep=semicolon,x=x, y=y, y error expr=\yerrstd] { n; x; p; y; yerr 50; 43; 3; 2.232000E-02; 3.345949E-02 50; 47; 3; 1.980667E-02; 3.107194E-02 50; 51; 3; 3.554667E-02; 5.048638E-02 50; 55; 3; 3.606667E-02; 3.939888E-02 50; 59; 3; 2.746000E-02; 2.666070E-02 }; \addlegendentry{IR-3R}; \addplot[IR3R,error bars/.cd, y dir=both, y explicit]%IR 3R table [col sep=semicolon,x=x, y=y, y error expr=\yerrstd] { n; x; p; y; yerr 50; 43; 3; 1.914000E-02; 2.880335E-02 50; 47; 3; 1.630667E-02; 2.480928E-02 50; 51; 3; 4.217333E-02; 1.019952E-01 50; 55; 3; 3.255333E-02; 3.371513E-02 50; 59; 3; 2.510667E-02; 2.260731E-02 }; % SIZE 20 \draw[<->] (75,.03) -- (91,.03) node[timeLabel,below,pos=.5] {Size020-5}; % \addlegendentry{Std}; \addplot[Std,error bars/.cd, y dir=both, y explicit]%STD table [col sep=semicolon,x=x, y=y, y error expr=\yerrstd] { n; x; p; y; yerr 50; 75; 5; 1.626667E-01; 2.508645E-01 50; 79; 5; 1.619933E-01; 2.802782E-01 50; 83; 5; 1.551200E-01; 2.498845E-01 50; 87; 5; 8.805333E-02; 1.303739E-01 50; 91; 5; 1.359133E-01; 2.240360E-01 }; % \addlegendentry{Std-woNL}; \addplot[StdwoNL,error bars/.cd, y dir=both, y explicit]%STD woNL table [col sep=semicolon,x=x, y=y, y error expr=\yerrstd] { n; x; p; y; yerr 50; 75; 5; 1.992000E-01; 3.231331E-01 50; 79; 5; 2.182333E-01; 3.890817E-01 50; 83; 5; 2.083333E-01; 3.536913E-01 50; 87; 5; 1.225067E-01; 2.000610E-01 50; 91; 5; 2.290400E-01; 4.821580E-01 }; \addplot[Epsilon,error bars/.cd, y dir=both, y explicit]%epsilon table [col sep=semicolon,x=x, y=y, y error expr=\yerrstd] { n; x; p; y; yerr 50; 75; 5; 1.342933E-01; 1.997754E-01 50; 79; 5; 1.312600E-01; 2.180705E-01 50; 83; 5; 1.296467E-01; 1.994134E-01 50; 87; 5; 7.693333E-02; 1.061648E-01 50; 91; 5; 1.201200E-01; 1.910037E-01 }; \addplot[IR,error bars/.cd, y dir=both, y explicit]%IR table [col sep=semicolon,x=x, y=y, y error expr=\yerrstd] { n; x; p; y; yerr 50; 75; 5; 1.609800E-01; 2.577505E-01 50; 79; 5; 1.567200E-01; 2.722886E-01 50; 83; 5; 1.500400E-01; 2.424916E-01 50; 87; 5; 8.552667E-02; 1.252870E-01 50; 91; 5; 1.363000E-01; 2.240533E-01 }; \addplot[IR3R,error bars/.cd, y dir=both, y explicit]%IR 3R table [col sep=semicolon,x=x, y=y, y error expr=\yerrstd] { n; x; p; y; yerr 50; 75; 5; 1.190133E-01; 1.756659E-01 50; 79; 5; 1.117533E-01; 1.746759E-01 50; 83; 5; 1.200467E-01; 1.769278E-01 50; 87; 5; 7.459333E-02; 1.037230E-01 50; 91; 5; 1.028133E-01; 1.404975E-01 }; % SIZE 30 \draw[<->] (107,.03) -- (123,.03) node[timeLabel,below,pos=.5] {Size030-7}; % \addlegendentry{Std}; \addplot[Std,error bars/.cd, y dir=both, y explicit]%STD table [col sep=semicolon,x=x, y=y, y error expr=\yerrstd] { n; x; p; y; yerr 50; 107; 7; 6.775800E-01; 1.538524E+00 50; 111; 7; 3.182800E-01; 6.240050E-01 50; 115; 7; 5.568267E-01; 1.302207E+00 50; 119; 7; 3.521000E-01; 6.923321E-01 50; 123; 7; 1.141467E-01; 2.562440E-01 }; % \addlegendentry{Std-woNL}; \addplot[StdwoNL,error bars/.cd, y dir=both, y explicit]%STD woNL table [col sep=semicolon,x=x, y=y, y error expr=\yerrstd] { n; x; p; y; yerr 50; 107; 7; 1.058000E+00; 2.442640E+00 50; 111; 7; 4.601733E-01; 9.485014E-01 50; 115; 7; 1.314133E+00; 3.714816E+00 50; 119; 7; 7.090467E-01; 1.649638E+00 50; 123; 7; 1.709133E-01; 4.427992E-01 }; \addplot[Epsilon,error bars/.cd, y dir=both, y explicit]%epsilon table [col sep=semicolon,x=x, y=y, y error expr=\yerrstd] { n; x; p; y; yerr 50; 107; 7; 5.844933E-01; 1.262175E+00 50; 111; 7; 2.924733E-01; 5.598914E-01 50; 115; 7; 5.133200E-01; 1.185395E+00 50; 119; 7; 3.229267E-01; 6.018227E-01 50; 123; 7; 1.139600E-01; 2.472006E-01 }; \addplot[IR,error bars/.cd, y dir=both, y explicit]%IR table [col sep=semicolon,x=x, y=y, y error expr=\yerrstd] { n; x; p; y; yerr 50; 107; 7; 6.205333E-01; 1.382333E+00 50; 111; 7; 2.987667E-01; 5.806298E-01 50; 115; 7; 5.248667E-01; 1.221795E+00 50; 119; 7; 3.325533E-01; 6.380090E-01 50; 123; 7; 1.116800E-01; 2.356484E-01 }; \addplot[IR3R,error bars/.cd, y dir=both, y explicit]%IR 3R table [col sep=semicolon,x=x, y=y, y error expr=\yerrstd] { n; x; p; y; yerr 50; 107; 7; 5.090933E-01; 1.090549E+00 50; 111; 7; 2.828200E-01; 5.462717E-01 50; 115; 7; 3.900400E-01; 8.674814E-01 50; 119; 7; 2.775067E-01; 4.926636E-01 50; 123; 7; 1.014133E-01; 2.096448E-01 }; % SIZE 40 \draw[<->] (axis cs:139,0.03) -- (axis cs:155,0.03) node[timeLabel,below,pos=.5] {Size040-9}; % \draw[red] (167, 1.01E+03) circle (3pt); \addplot[Std,error bars/.cd, y dir=both, y explicit]%STD table [col sep=semicolon,x=x, y=y, y error expr=\yerrstd] { n; x; p; y; yerr 50; 139; 9; 1.908620E+00; 3.987439E+00 50; 143; 9; 2.684753E+00; 7.660035E+00 50; 147; 9; 1.692413E+00; 3.354450E+00 50; 151; 9; 1.645480E+00; 6.233754E+00 50; 155; 9; 1.647600E+00; 3.684100E+00 }; % \addlegendentry{Std-woNL}; \addplot[StdwoNL,error bars/.cd, y dir=both, y explicit]%STD woNL table [col sep=semicolon,x=x, y=y, y error expr=\yerrstd] { n; x; p; y; yerr 50; 139; 9; 4.245527E+00; 1.000110E+01 50; 143; 9; 6.369140E+00; 1.846379E+01 50; 147; 9; 3.578527E+00; 7.470487E+00 50; 151; 9; 7.736733E+00; 3.650712E+01 50; 155; 9; 4.794280E+00; 1.365770E+01 }; \addplot[Epsilon,error bars/.cd, y dir=both, y explicit]%epsilon table [col sep=semicolon,x=x, y=y, y error expr=\yerrstd] { n; x; p; y; yerr 50; 139; 9; 2.023193E+00; 4.228155E+00 50; 143; 9; 2.955173E+00; 8.690866E+00 50; 147; 9; 1.827193E+00; 3.669760E+00 50; 151; 9; 1.962647E+00; 7.795193E+00 50; 155; 9; 1.766853E+00; 4.054424E+00 }; \addplot[IR,error bars/.cd, y dir=both, y explicit]%IR table [col sep=semicolon,x=x, y=y, y error expr=\yerrstd] { n; x; p; y; yerr 50; 139; 9; 2.102240E+00; 4.414102E+00 50; 143; 9; 3.187507E+00; 9.285305E+00 50; 147; 9; 1.896727E+00; 3.813155E+00 50; 151; 9; 1.995840E+00; 7.938650E+00 50; 155; 9; 1.929500E+00; 4.411231E+00 }; \addplot[IR3R,error bars/.cd, y dir=both, y explicit]%IR 3R table [col sep=semicolon,x=x, y=y, y error expr=\yerrstd] { n; x; p; y; yerr 50; 139; 9; 1.570753E+00; 3.129554E+00 50; 143; 9; 2.383960E+00; 7.271879E+00 50; 147; 9; 1.547587E+00; 2.992325E+00 50; 151; 9; 1.279873E+00; 4.574241E+00 50; 155; 9; 1.347760E+00; 2.812735E+00 }; \end{axis} \end{tikzpicture} \end{center} Again, even if the diagram is quite crowded, it is evident that \textrm{Std-woNL} version of the DC checking algorithm shows the worst performance while \textrm{IR-3R} version requires the minimun execution time. The most important fact about this results is that, in general, checking NON DC instances requires less than an order of magnitude of execution time required for checking DC instances. \section{CSTNUBenchmark2018} %### The structure of this benchmark is equal to the CSTNBenchmark2018 even if the size of benchhmarks is smaller. Due to the internal building function of ATAPIS Toolset, the relation between workflow component quantities and CSTN order is $5+2N+6k+6j$, where $N$ is the number of tasks, $k$ the number of XOR connectors, and $j$ the number of AND connectors. The following table summurizes the characteristics of each sub-benchmark. \begin{center} \begin{tabular}{@{} l >{\RaggedLeft\arraybackslash}p{1.4cm} >{\RaggedLeft\arraybackslash}p{1.5cm} >{\RaggedLeft\arraybackslash}p{1.5cm} >{\RaggedLeft\arraybackslash}p{1.3cm} c >{\RaggedLeft\arraybackslash}p{1.2cm} @{}} \hline \textbf{Group} &\textbf{Bench mark} & \textbf{instance indexes} & \textbf{\# activities} & \textbf{\#XOR} & \textbf{\#AND} & \textbf{CSTNU order}\\ \hline Size010-3 & B10-3-0 & 000-049 & 10 & 3 & 0 & 43\\ & B10-3-1 & 050-099 & 10 & 3 & 1 & 49\\ & B10-3-2 & 100-149 & 10 & 3 & 2 & 55\\ & B10-3-3 & 150-199 & 10 & 3 & 3 & 61\\ & B10-3-4 & 200-249 & 10 & 3 & 4 & 67\\ \hline Size010-4 & B10-4-0 & 000-049 & 10 & 4 & 0 & 49\\ & B10-4-1 & 050-099 & 10 & 4 & 1 & 55\\ & B10-4-2 & 100-149 & 10 & 4 & 2 & 61\\ & B10-4-3 & 150-199 & 10 & 4 & 3 & 67\\ & B10-4-4 & 200-249 & 10 & 4 & 4 & 73\\ \hline Size010-5 & B10-5-0 & 000-049 & 10 & 5 & 0 & 55\\ & B10-5-1 & 050-099 & 10 & 5 & 1 & 62\\ & B10-5-2 & 100-149 & 10 & 5 & 2 & 67\\ & B10-5-3 & 150-199 & 10 & 5 & 3 & 73\\ & B10-5-4 & 200-249 & 10 & 5 & 4 & 79\\ % \hline % Size015-3 & B15-3-0 & 000-049 & 15 & 3 & 0 & 53\\ % & B15-3-1 & 050-099 & 15 & 3 & 1 & 59\\ % & B15-3-2 & 100-149 & 15 & 3 & 2 & 65\\ % & B15-3-3 & 150-199 & 15 & 3 & 3 & 71\\ % & B15-3-4 & 200-249 & 15 & 3 & 4 & 77\\ % \hline % Size015-4 & B15-4-0 & 000-049 & 15 & 4 & 0 & 59\\ % & B15-4-1 & 050-099 & 15 & 4 & 1 & 65\\ % & B15-4-2 & 100-149 & 15 & 4 & 2 & 71\\ % & B15-4-3 & 150-199 & 15 & 4 & 3 & 77\\ % & B15-4-4 & 200-249 & 15 & 4 & 4 & 83\\ % \hline % Size015-5 & B15-5-0 & 000-049 & 15 & 5 & 0 & 65\\ % & B15-5-1 & 050-099 & 15 & 5 & 1 & 71\\ % & B15-5-2 & 100-149 & 15 & 5 & 2 & 77\\ % & B15-5-3 & 150-199 & 15 & 5 & 3 & 83\\ % & B15-5-4 & 200-249 & 15 & 5 & 4 & 89\\ % \hline % Da sistemare!Size020-3 & B20-3-0 & 000-029 & 20 & 3 & 0 & 63\\ % & B20-3-1 & 030-059 & 20 & 3 & 1 & 69\\ % & B20-3-2 & 060-099 & 20 & 3 & 2 & 75\\ % & B20-3-3 & 090-119 & 20 & 3 & 3 & 81\\ % & B20-3-4 & 120-149 & 20 & 3 & 4 & 87\\ % \hline % Size020-4 & B20-4-0 & 000-029 & 20 & 4 & 0 & 69\\ % & B20-4-1 & 030-059 & 20 & 4 & 1 & 75\\ % & B20-4-2 & 060-099 & 20 & 4 & 2 & 81\\ % & B20-4-3 & 090-119 & 20 & 4 & 3 & 87\\ % & B20-4-4 & 120-149 & 20 & 4 & 4 & 93\\ % \hline % Size020-5 & B20-5-0 & 000-029 & 20 & 5 & 0 & 75\\ % & B20-5-1 & 030-059 & 20 & 5 & 1 & 81\\ % & B20-5-2 & 060-099 & 20 & 5 & 2 & 87\\ % & B20-5-3 & 090-119 & 20 & 5 & 3 & 93\\ % & B20-5-4 & 120-149 & 20 & 5 & 4 & 99\\ % \hline \end{tabular} \end{center} %### The total number of CSTNU instances is $1500$, $750$ DC and $750$ not DC, divided in 3 main group---Size010-3, Size010-4, and Size010-5---in turn divided in other 5 groups having 50 DC instances eanch and in other 5 groups having 50 NOT DC instances each. \subsection{Experimental Evaluation} There are three implementations of CSTNU DC checking algorithm: \begin{enumerate} \item \textbf{STD}: it implements the CSTNU DC checking rules assuming instantaneous reaction in a streamlined CSTNU. The CSTNU DC checking rules are zqR0, zqR3, zlabeledLetterRemovalRule, labeledLetterRemovalRule, labeledPropagationqLP, and labeledCrossLowerCaseRule. %The second one, called \textbf{Potential}, determines the CSTNU DC status checking if CSTNU graph allows the determination of all shortest paths to single destination (node Z) assuming instantaneous reaction. %Such distances, that represent the earlier execution times, are calculated using the Bellman-Ford algorithm on the reversed graph and using the CSTNU propagation rules as rules for updating potentials. \item \textbf{STD OnlyToZ}: it is similar to STD version but it limits the propagation to edges heading to node Z. Therefore, it applies rules zqR0, zqR3, zlabeledLetterRemovalRule, zlabeledPropagationqLP, and zlabeledCrossLowerCaseRule. \item \textbf{CSTNU2CSTN}: it determines the CSTNU DC status transforming the given CSTNU into an equivalent CSTN and checking the DC of this last one. \end{enumerate} In the following we propose some diagrams that show the execution times of all versions in the CSTNUBenchmark2018 benchmark. The implementations were developed in Java~8 and run on an Oracle JVM~8 in a Linux machine with an Intel(R) Xeon(R) CPU E5-2637 v4 \@ 3.50GHz and 503GB of RAM. The execution times were collected by a Java program (\texttt{Checker}, proposed in our package) that allows one to determine the average execution time---and its standard deviation---of a DC checking algorithm applied to a set of instances. The parameters for the Oracle Java Virtual Machine~1.8.0\_144 were: \texttt{-d64}, \texttt{-Xmx6g}, \texttt{-Xms6g}, \texttt{-XX:NewSize=3g}, \texttt{-XX:MaxNewSize=3g}, \texttt{-XX:+UseG1GC}, \texttt{-Xnoclassgc}, and \texttt{-XX:+AggressiveOpts}. All average execution times were determined considering only DC instances in benchmarks of groups Size010-3, Size010-4, and Size010-5. Each drawn value is the sample average $\bar{X}_{50}$ of execution times obtained considering fifty instances of the relative benchmark. In details, $\bar{X}_{50}=\frac{\sum_{i=1}^{50} X_i}{50}$ where $X_i$ is the average execution time obtained executing 3 times the algorithm on instance having index $i$\footnote{The determination of all values required to execute the DC checking for 24 000 times, 83.18 hours.}. The error bar of each drawn value represents $2.010$ times the standard error of the mean, $\frac{S_{50}}{\sqrt{50}}$, where $S_{50}$ is the corrected sample standard deviation, $S_{50}= \sqrt{\frac{\sum_{i=1}^{50} (X_i-\bar{X}_{50})^2}{49}}$. Value $2.010$ is the Student's $t$ distribution value with 49 degrees of freedom. Therefore, the error bar represents a 95\% confidence interval for the average execution time of the algorithm on instances of the considered benchmark. In more details, Figure 4.1 shows the performances of the three implementations in benchmarks of group Size010-3. Each printed value corresponds to the average value determined considering the corresponding benchmark B10-3-*. For \textbf{STD} and \textbf{STD OnlyToZ} run time out (45 minutes) in some cases. The average execution time was determined considering also such instances and, therefore, it represents a lower bound to the real average. All three implementation require, in average, a smaller execution time as the order of instances increases. This is due to the fact the bigger instances are obtained increasing the number of parallel connectors in the generated workflows (the number of contingent links and the number of observation node are fixed). Increasing the number of parallel connectors, there are more parallel branches and, therefore, more contingent links must be put in the same scenario. This makes a network easier to be checked. From the experimental results, it emerges that \textbf{CSTNU2CSTN} has the best performance and the worst performance for all the implementations is in the sub benchmark B10-3-0 where all generated workflows have no parallel branches. \begin{center} % \captionsetup{justification=justified} % \subfloat[Benchmark $N=10,|\calp|=3$.\label{SubFig:N10}]{ % \begin{subfigure}[b]{.45\linewidth}\centering% \ 44 \leq n \leq 59, \ \pgfplotsset{every axis y label/.append style={inner sep=1pt,outer sep=1pt}} \noindent \begin{tikzpicture} %% %%This diagram requires pgfplots version 1.15 to be compiled without errors. %% \begin{axis}[ normalsize, title=\textbf{Figure 4.1: Controllable Instances in group Size010}, % title style={at={(0.5,-.2)}}, % height=8 cm, % width=.48\textwidth, % X xlabel={$n$}, xlabel style={at={(ticklabel cs:1)}, anchor=south west}, minor x tick num=1, xmajorgrids=true, % Y ylabel={execution time}, y unit=seconds, % minor y tick num=1,%not applied for ymode=log yminorgrids=true, ymajorgrids=true, ymode=log, log basis y=10, log ticks with fixed point, % ytick=\empty, % extra y ticks={2,5,10, 20, 30, 60, 120}, % extra y tick labels={30s, 1, 5, 10, 20, 30}, % % ylabel shift=-5pt, % LEGEND cycle multi list={colorbrewer}, legend style={at={(1.05,1)},anchor=north west},%legend pos=north west, legend columns=1, % legend entries={ {Std}, {Std-woNL}, {$\epsilon$}, {$\epsilon$-woNL}, {$\epsilon$-woNL-3R}, {IR}, {IR-woNL}, {IR-woNL-3R}, } ] % % % SIZE 10 % \draw[<->] (axis cs:43,.07) -- (axis cs:67,.07) node[timeLabel,below,pos=.5] {Size010-3}; \addlegendentry{STD}; \addplot[Std0,error bars/.cd, y dir=both, y explicit]%Size010-3 STD table [x=x, y=y,y error expr=\yerrstd] {%node002 n; x; c; p; y; yerr %SIZE-010-3 50; 43; 10; 3; 5.091416E+01; 1.477377E+02 49; 49; 10; 3; 1.028798E+01; 2.548048E+01 50; 55; 10; 3; 6.264240E+00; 3.214802E+01 49; 61; 10; 3; 2.737714E+00; 7.646775E+00 49; 67; 10; 3; 1.646306E+00; 6.390962E+00 %SIZE-010-4 50; 49; 10; 4; 1.391567E+02; 3.915289E+02 49; 55; 10; 4; 3.902378E+01; 1.259716E+02 50; 61; 10; 4; 1.333530E+01; 3.379352E+01 50; 67; 10; 4; 1.107070E+01; 2.777601E+01 47; 73; 10; 4; 3.184213E+00; 4.656809E+00 %SIZE010-05 50; 55; 10; 5; 6.246685E+02; 7.922738E+02 50; 61; 10; 5; 2.658576E+02; 6.151018E+02 49; 67; 10; 5; 3.293194E+01; 7.112472E+01 50; 73; 10; 5; 1.321738E+01; 2.093700E+01 50; 79; 10; 5; 4.922566E+01; 1.189767E+02 }; \addlegendentry{STD OnlyToZ}; \addplot[StdZ0,error bars/.cd, y dir=both, y explicit]%Size010-3 OnlyToZ table [x=x, y=y,y error expr=\yerrstd] { %node002 n; x; c; p; y; yerr 50; 43; 10; 3; 7.666668E+01; 2.181891E+02 49; 49; 10; 3; 1.270212E+01; 2.481399E+01 50; 55; 10; 3; 9.625600E+00; 5.091370E+01 49; 61; 10; 3; 4.788449E+00; 1.405251E+01 49; 67; 10; 3; 2.361837E+00; 9.502906E+00 %SIZE010-04 50; 49; 10; 4; 1.371552E+02; 2.918778E+02 49; 55; 10; 4; 7.933171E+01; 2.686141E+02 50; 61; 10; 4; 3.640496E+01; 1.411500E+02 50; 67; 10; 4; 1.917958E+01; 4.769079E+01 47; 73; 10; 4; 6.050894E+00; 1.217311E+01 %SIZE010-05 50; 55; 10; 5; 8.790104E+02; 1.002148E+03 50; 61; 10; 5; 4.308473E+02; 8.250476E+02 49; 67; 10; 5; 5.759996E+01; 1.232275E+02 50; 73; 10; 5; 2.551258E+01; 4.774629E+01 50; 79; 10; 5; 9.923642E+01; 2.530102E+02 }; \addlegendentry{CSTNU2CSTN}; \addplot[2cstn0,error bars/.cd, y dir=both, y explicit]%CSTNU2CSTN 10-3 OnlyToZ table [x=x, y=y,y error expr=\yerrstd] { %node002 n; x; c; p; y; yerr 50; 43; 10; 3; 4.831026E+01; 1.478218E+02 49; 49; 10; 3; 1.024759E+01; 2.400713E+01 50; 55; 10; 3; 5.273360E+00; 2.097316E+01 49; 61; 10; 3; 2.480449E+00; 6.957257E+00 49; 67; 10; 3; 1.555061E+00; 5.933459E+00 %SIZE010-04 50; 49; 10; 4; 5.668464E+01; 1.107508E+02 49; 55; 10; 4; 2.581890E+01; 8.016640E+01 50; 61; 10; 4; 1.467316E+01; 6.338712E+01 50; 67; 10; 4; 8.529620E+00; 2.409720E+01 47; 73; 10; 4; 2.607234E+00; 5.219721E+00 %Size010-05 50; 55; 10; 5; 4.628197E+02; 7.060206E+02 50; 61; 10; 5; 2.359923E+02; 6.008369E+02 49; 67; 10; 5; 2.227896E+01; 4.697067E+01 50; 73; 10; 5; 1.039476E+01; 1.820456E+01 50; 79; 10; 5; 3.761364E+01; 8.064855E+01 }; % \addlegendentry{Size010-4 STD}; % \addplot[Std1,error bars/.cd, y dir=both, y explicit]%Size010-3 STD % table [x=x, y=y,y error expr=\yerrstd] {%node002 % n; x; c; p; y; yerr % 50; 49; 10; 4; 1.864265E+02; 4.145086E+02 % }; % \addlegendentry{Size010-4 STD OnlyToZ}; % \addplot[StdZ1,error bars/.cd, y dir=both, y explicit]%Size010-3 OnlyToZ % table [x=x, y=y,y error expr=\yerrstd] { %node002 % n; x; c; p; y; yerr % 50; 49; 10; 4; 3.020879E+02; 5.662495E+02 % }; % \addlegendentry{Size010-5 STD}; % \addplot[Std2,error bars/.cd, y dir=both, y explicit]%STD % table [x=x, y=y,y error expr=\yerrstd] { % n; x; c; p; y; yerr % 33; 55; 10; 5; 8.054692E+02; 9.704145E+02 % }; % % \addlegendentry{Size010-5 STD OnlyToZ}; % \addplot[StdZ2,error bars/.cd, y dir=both, y explicit]%CSTNU2CSTN 10-5 % table [x=x, y=y,y error expr=\yerrstd] { % n; x; c; p; y; yerr % 37; 55; 10; 5; 1.082941E+03; 1.061775E+03 % }; \node[pin={[font=\tiny,text width=1.2cm,pin edge={<-,shorten <=1pt,black}]above:Benchmark Size010-3},ellipse,fit={(43,7) (43,110)},draw] {}; \node[pin={[font=\tiny,text width=1.2cm,pin edge={<-,shorten <=1pt,black}, pin distance=2cm]-85:Benchmark Size010-4},ellipse,fit={(49,37) (49,250)},draw] {}; \node[pin={[font=\tiny,text width=1.2cm,pin edge={<-,shorten <=1pt,black}, pin distance=2cm]10:Benchmark Size010-5},ellipse,fit={(55,250) (55,1100)},draw] {}; \end{axis} \end{tikzpicture} \end{center} % For group Size010-4 and Size010-5, it results that the worst berformances are related to first sub benchmark of each group, i.e., to the benchmark built by generating workflows without parallel branches. Figure 4.2 reports the performances of the three implementations showing only the average execution time in the first sub benchmark of each group, Size010-3, Size010-4, and Size010-5. Again, it is clear that the \textbf{CSTNU2CSTN} has the best performance. \begin{center} % \captionsetup{justification=justified} % \subfloat[Benchmark $N=10,|\calp|=3$.\label{SubFig:N10}]{ % \begin{subfigure}[b]{.45\linewidth}\centering% \ 44 \leq n \leq 59, \ \pgfplotsset{every axis y label/.append style={inner sep=1pt,outer sep=1pt}} \noindent \begin{tikzpicture} %% %%This diagram requires pgfplots version 1.15 to be compiled without errors. %% \begin{axis}[ normalsize, title=\textbf{Figure 4.2: Worst Controllable Instances in group Size010}, % title style={at={(0.5,-.2)}}, % height=8 cm, % width=.48\textwidth, % X xlabel={$n$}, xlabel style={at={(ticklabel cs:1)}, anchor=south west}, minor x tick num=1, xmajorgrids=true, % Y ylabel={execution time}, y unit=seconds, % minor y tick num=1,%not applied for ymode=log yminorgrids=true, ymajorgrids=true, ymode=log, log basis y=10, log ticks with fixed point, % ytick=\empty, % extra y ticks={2,5,10, 20, 30, 60, 120}, % extra y tick labels={30s, 1, 5, 10, 20, 30}, % % ylabel shift=-5pt, % LEGEND cycle multi list={colorbrewer}, legend style={at={(1.05,1)},anchor=north west},%legend pos=north west, legend columns=1, % legend entries={ {Std}, {Std-woNL}, {$\epsilon$}, {$\epsilon$-woNL}, {$\epsilon$-woNL-3R}, {IR}, {IR-woNL}, {IR-woNL-3R}, } ] % % % SIZE 10 \addlegendentry{STD}; \addplot[Std0,error bars/.cd, y dir=both, y explicit]%Size010-3 OnlyToZ table [x=x, y=y,y error expr=\yerrstd] { %node002 n; x; c; p; y; yerr 50; 43; 10; 3; 5.091416E+01; 1.477377E+02 50; 49; 10; 4; 1.391567E+02; 3.915289E+02 50; 55; 10; 5; 6.371271E+02; 8.129238E+02 }; \addlegendentry{STD OnlyToZ}; \addplot[StdZ0,error bars/.cd, y dir=both, y explicit]%Size010-3 OnlyToZ table [x=x, y=y,y error expr=\yerrstd] { %node002 n; x; c; p; y; yerr 50; 43; 10; 3; 7.666668E+01; 2.181891E+02 50; 49; 10; 4; 1.371552E+02; 2.918778E+02 50; 55; 10; 5; 8.834172E+02; 1.024095E+03 }; % \addlegendentry{Size010-3 Potential}; % \addplot[potential0,error bars/.cd, y dir=both, y explicit]%Potential 10-3 % table [x=x, y=y,y error expr=\yerrstd] { %node002 % n; x; c; p; y; yerr % 50; 43; 10; 3; 3.648460E+00; 8.659445E+00 % 50; 49; 10; 3; 3.270730E+01; 2.242015E+02 % 50; 55; 10; 3; 6.127200E-01; 1.876553E+00 % 50; 61; 10; 3; 2.747120E+00; 1.628720E+01 % 50; 67; 10; 3; 2.623000E-01; 5.877230E-01 % }; \addlegendentry{CSTNU2CSTN}; \addplot[2cstn0,error bars/.cd, y dir=both, y explicit]%CSTNU2CSTN table [x=x, y=y,y error expr=\yerrstd] { %node002 n; x; c; p; y; yerr 50; 43; 10; 3; 4.831026E+01; 1.478218E+02 50; 49; 10; 4; 5.668464E+01; 1.107508E+02 50; 55; 10; 5; 4.634009E+02; 7.083617E+02 }; \node[font=\tiny,text width=1.5cm,anchor=center,align=center] at (44,20) {Worst case in Size010-3}; \node[font=\tiny,text width=1.5cm,anchor=center,align=center] at (49,20) {Worst case in Size010-4}; \node[font=\tiny,text width=1.5cm,anchor=center,align=center] at (54.5,20) {Worst case in Size010-5}; \end{axis} \end{tikzpicture} \end{center} % \begin{center} % % \captionsetup{justification=justified} % % \subfloat[Benchmark $N=10,|\calp|=3$.\label{SubFig:N10}]{ % % \begin{subfigure}[b]{.45\linewidth}\centering% \ 44 \leq n \leq 59, \ % \pgfplotsset{every axis y label/.append style={inner sep=1pt,outer sep=1pt}} % \noindent % \begin{tikzpicture} % %% % %%This diagram requires pgfplots version 1.15 to be compiled without errors. % %% % \begin{axis}[ % normalsize, % title={\textbf{Controllable Instances in group Size15}}, % % title style={at={(0.5,-.2)}}, % % height=8 cm, % % width=.48\textwidth, % % X % xlabel={$n$}, % xlabel style={at={(ticklabel cs:1)}, anchor=south west}, % minor x tick num=1, % xmajorgrids=true, % % Y % ylabel={execution time}, % y unit=seconds, % % minor y tick num=1,%not applied for ymode=log % yminorgrids=true, % ymajorgrids=true, % ymode=log, % log basis y=10, % log ticks with fixed point, % % ytick=\empty, % % extra y ticks={2,5,10, 20, 30, 60, 120}, % % extra y tick labels={30s, 1, 5, 10, 20, 30}, % % % ylabel shift=-5pt, % % LEGEND % cycle multi list={colorbrewer}, % legend style={at={(1.05,1)},anchor=north west},%legend pos=north west, % legend columns=1, % % legend entries={ {Std}, {Std-woNL}, {$\epsilon$}, {$\epsilon$-woNL}, {$\epsilon$-woNL-3R}, {IR}, {IR-woNL}, {IR-woNL-3R}, } % ] % % % % % \addlegendentry{Size015-3 STD}; % \addplot[Std,error bars/.cd, y dir=both, y explicit]%STD % table [x=x, y=y,y error expr=\yerrstd] { % n; x; c; p; y; yerr % 50; 53; 15; 3; 9.541316E+01; 3.121200E+02 % 50; 59; 15; 3; 1.445414E+02; 5.061762E+02 % 50; 65; 15; 3; 7.332089E+01; 2.438410E+02 % 50; 71; 15; 3; 3.562093E+01; 8.930203E+01 % 50; 77; 15; 3; 6.931913E+01; 2.517395E+02 % }; % % \addlegendentry{Size015-3 Potential}; % \addplot[potential0,error bars/.cd, y dir=both, y explicit]%Potential 10-3 % table [x=x, y=y,y error expr=\yerrstd] { % n; x; c; p; y; yerr % 50; 53; 15; 3; 3.158905E+02; 6.719661E+02 % 50; 59; 15; 3; 1.469918E+02; 4.307002E+02 % 50; 65; 15; 3; 1.084414E+02; 3.882850E+02 % 50; 71; 15; 3; 3.287673E+01; 9.127215E+01 % 50; 77; 15; 3; 7.844415E+01; 2.200928E+02 % }; % \addlegendentry{Size015-3 CSTNU2CSTN}; % \addplot[2cstn0,error bars/.cd, y dir=both, y explicit]%CSTNU2CSTN 10-3 % table [x=x, y=y,y error expr=\yerrstd] { % n; x; c; p; y; yerr % 50; 53; 15; 3; 3.158905E+02; 6.719661E+02 % }; % % % % \addlegendentry{Size015-4}; % \addplot[Std1,error bars/.cd, y dir=both, y explicit]%STD % table [x=x, y=y,y error expr=\yerrstd] { % n; x; c; p; y; yerr % 50; 59; 15; 4; 1.691083E+02; 4.565417E+02 % 50; 65; 15; 4; 1.203675E+02; 2.649183E+02 % 50; 71; 15; 4; 1.608776E+02; 3.729274E+02 % 50; 77; 15; 4; 2.164700E+02; 5.266331E+02 % 50; 83; 15; 4; 1.436906E+02; 3.220673E+02 % }; % \end{axis} % \end{tikzpicture} % \end{center} % % % Figure 4.3 show the analysis results obtained when instances are non-DC. The two algorithms have a worse performance checking non-DC instances than the one checking DC ones. In average, each algorithm require an average execution time that, at most, can be 8 times greater than the average execution time required for checking positive instances having the same order. \begin{center} \noindent \begin{tikzpicture} %% %%This diagram requires pgfplots version 1.15 to be compiled without errors. %% \begin{axis}[ normalsize, title=\textbf{Figure 4.3: Not Controllable Instances in group Size010}, % title style={at={(0.5,-.2)}}, % height=8 cm, % width=.48\textwidth, % X xlabel={$n$}, xlabel style={at={(ticklabel cs:.999)}, anchor=south west}, minor x tick num=1, xmajorgrids=true, % Y ylabel={execution time}, y unit=seconds, % minor y tick num=1,%not applied for ymode=log yminorgrids=true, ymajorgrids=true, ymode=log, log basis y=10, log ticks with fixed point, % ytick=\empty, % extra y ticks={2,5,10, 20, 30, 60, 120}, % extra y tick labels={30s, 1, 5, 10, 20, 30}, % % ylabel shift=-5pt, % LEGEND legend style={at={(1.05,1)},anchor=north west},%legend pos=north west, legend columns=1, ] % SIZE 10 % \draw[<->] (axis cs:43,.008) -- (axis cs:59,.008) node[timeLabel,below,pos=.5] {Size010-3}; \addlegendentry{STD}; \addplot[Std0,error bars/.cd, y dir=both, y explicit]%STD table [col sep=semicolon,x=x, y=y, y error expr=\yerrstd] { n; x; c; p; y; yerr %Size010-03 50; 43; 10; 3; 4.256485E+02; 8.588555E+02 50; 49; 10; 3; 2.613895E+02; 5.987760E+02 50; 55; 10; 3; 1.468550E+02; 4.520767E+02 50; 61; 10; 3; 4.630302E+01; 1.691983E+02 50; 67; 10; 3; 1.064088E+01; 3.172038E+01 %Size010-04 50; 49; 10; 4; 7.621999E+02; 1.101346E+03 50; 55; 10; 4; 3.749540E+02; 8.568626E+02 50; 61; 10; 4; 3.406854E+02; 7.608045E+02 50; 67; 10; 4; 2.254463E+02; 6.646293E+02 50; 73; 10; 4; 8.765700E+01; 3.979186E+02 %Size010-05 50; 55; 10; 5; 9.49E+02; 1222.457576 50; 61; 10; 5; 3.33E+02; 808.9411783 50; 67; 10; 5; 3.11E+02; 822.2362662 50; 73; 10; 5; 2.08E+02; 586.8996856 50; 79; 10; 5; 1.21E+02; 422.6696821 }; \addlegendentry{STD OnlyToZ}; \addplot[StdZ0,error bars/.cd, y dir=both, y explicit]%STD table [col sep=semicolon,x=x, y=y, y error expr=\yerrstd] { n; x; c; p; y; yerr %Size010-03 50; 43; 10; 3; 5.358319E+02; 9.031363E+02 50; 49; 10; 3; 3.662944E+02; 8.004453E+02 50; 55; 10; 3; 1.766566E+02; 3.758049E+02 50; 61; 10; 3; 6.735452E+01; 1.763967E+02 50; 67; 10; 3; 3.508462E+01; 7.441798E+01 %Size010-04 50; 49; 10; 4; 9.121307E+02; 1.108513E+03 50; 55; 10; 4; 6.239223E+02; 1.043266E+03 50; 61; 10; 4; 5.929469E+02; 1.007233E+03 50; 67; 10; 4; 2.403665E+02; 5.926639E+02 50; 73; 10; 4; 1.301206E+02; 4.493994E+02 %Size010-05 50; 55; 10; 5; 1.80E+03; 1168.994104 50; 61; 10; 5; 7.20E+02; 1060.850157 50; 67; 10; 5; 7.25E+02; 1011.134065 50; 73; 10; 5; 7.07E+02; 950.6432731 50; 79; 10; 5; 4.52E+02; 863.1289979 }; % \addlegendentry{Size010-3 Potential}; % \addplot[potential0,error bars/.cd, y dir=both, y explicit]%Potential 10-3 % table [x=x, y=y,y error expr=\yerrstd] { % n; x; c; p; y; yerr % 50; 43; 10; 3; 4.896198E+01; 1.995357E+02 % 50; 49; 10; 3; 8.994330E+00; 2.057961E+01 % 50; 55; 10; 3; 1.362156E+01; 3.466637E+01 % 50; 61; 10; 3; 6.689118E+01; 1.953571E+02 % 50; 67; 10; 3; 1.240734E+01; 2.257379E+01 % }; \addlegendentry{CSTNU2CSTN}; \addplot[2cstn0,error bars/.cd, y dir=both, y explicit] table [col sep=semicolon,x=x, y=y,y error expr=\yerrstd] { n; x; c; p; y; yerr %CSTNU2CSTN Size010-03 50; 43; 10; 3; 3.797506E+02; 7.053545E+02 50; 49; 10; 3; 1.773728E+02; 4.611039E+02 50; 55; 10; 3; 7.742012E+01; 1.888194E+02 50; 61; 10; 3; 2.814666E+01; 5.513399E+01 50; 67; 10; 3; 5.867960E+00; 1.071975E+01 %CSTNU2CSTN Size010-04 50; 49; 10; 4; 4.784408E+02; 8.127599E+02 50; 55; 10; 4; 3.315259E+02; 7.741366E+02 50; 61; 10; 4; 1.889356E+02; 5.096884E+02 50; 67; 10; 4; 1.398007E+02; 4.593781E+02 50; 73; 10; 4; 5.516912E+01; 3.207802E+02 %Size010-05 50; 55; 10; 5; 1.29E+03; 1203.4543 50; 61; 10; 5; 3.49E+02; 748.1571753 50; 67; 10; 5; 4.21E+02; 850.9954841 50; 73; 10; 5; 3.27E+02; 611.1874584 50; 79; 10; 5; 3.95E+02; 753.1862965 }; \end{axis} \end{tikzpicture} \end{center} % \begin{center} % \noindent % \begin{tikzpicture} % %% % %%This diagram requires pgfplots version 1.15 to be compiled without errors. % %% % \begin{axis}[ % normalsize, % title=\textbf{Not Controllable Instances in group Size15}, % % title style={at={(0.5,-.2)}}, % % height=8 cm, % % width=.48\textwidth, % % X % xlabel={$n$}, % xlabel style={at={(ticklabel cs:.999)}, anchor=south west}, % minor x tick num=1, % xmajorgrids=true, % % Y % ylabel={execution time}, % y unit=seconds, % % minor y tick num=1,%not applied for ymode=log % yminorgrids=true, % ymajorgrids=true, % ymode=log, % log basis y=10, % log ticks with fixed point, % % ytick=\empty, % % extra y ticks={2,5,10, 20, 30, 60, 120}, % % extra y tick labels={30s, 1, 5, 10, 20, 30}, % % % ylabel shift=-5pt, % % LEGEND % legend style={at={(1.05,1)},anchor=north west},%legend pos=north west, % legend columns=1, % ] % % SIZE 10 % % \draw[<->] (axis cs:43,.008) -- (axis cs:59,.008) node[timeLabel,below,pos=.5] {Size010-3}; % \addlegendentry{Size015-3 STD}; % \addplot[Std3,error bars/.cd, y dir=both, y explicit]%STD % table [x=x, y=y,y error expr=\yerrstd] { % n; x; c; p; y; yerr % 50; 53; 15; 3; 2.541546E+02; 5.793220E+02 % % 50; 59; 15; 3; 3.303530E+02; 6.155183E+02 % % 50; 65; 15; 3; 1.163996E+02; 2.998146E+02 % % 50; 71; 15; 3; 1.593655E+02; 3.833600E+02 % % 50; 77; 15; 3; 2.094012E+02; 5.084725E+02 % }; % % \addlegendentry{Size015-3 Potential}; % \addplot[potential0,error bars/.cd, y dir=both, y explicit]%Potential 10-3 % table [x=x, y=y,y error expr=\yerrstd] { % n; x; c; p; y; yerr % 50; 53; 15; 3; 3.158905E+02; 6.719661E+02 % }; % \addlegendentry{Size015-3 CSTNU2CSTN}; % \addplot[2cstn0,error bars/.cd, y dir=both, y explicit]%CSTNU2CSTN 10-3 % table [x=x, y=y,y error expr=\yerrstd] { % n; x; c; p; y; yerr % 50; 53; 15; 3; 3.158905E+02; 6.719661E+02 % }; % % % % \addlegendentry{Size015-4}; % \addplot[Std4,error bars/.cd, y dir=both, y explicit]%STD % table [x=x, y=y,y error expr=\yerrstd] { % n; x; c; p; y; yerr % 50; 59; 15; 4; 3.418624E+02; 6.694700E+02 % % 50; 65; 15; 4; 3.240789E+02; 6.449419E+02 % % 50; 71; 15; 4; 3.199653E+02; 5.615545E+02 % % 50; 77; 15; 4; 2.176583E+02; 5.162483E+02 % % 50; 83; 15; 4; 1.219303E+02; 3.738415E+02 % }; % % \end{axis} % \end{tikzpicture} % \end{center} %%% OLD MATERIAL % \subsubsection{Evaluation of minimal A-Labeled value representation impact on algorithm performance} % % Following figures (4.4--4.7) depict results obtained considering a variant, ``w/o a-label opt.'', where a-labeled values of each edge are not minimized considering p-labeled values of the same edge. % Removing such optimization can lead to a situation in which an edge can have labeled value like $(-3, \diamond, \neg p), (-3, A, \neg p)$ where $(-3, A, \neg p)$ % is redundant. The reason for considering such variant is to evaluate if the costly minimization phase is still worthy. % % % \begin{center} % % \captionsetup{justification=justified} % % \subfloat[Benchmark $N=10,|\calp|=3$.\label{SubFig:N10}]{ % % \begin{subfigure}[b]{.45\linewidth}\centering% \ 44 \leq n \leq 59, \ % \noindent % \begin{tikzpicture} % %% % %%This diagram requires pgfplots version 1.15 to be compiled without errors. % %% % \begin{axis}[ % normalsize, % title=\textbf{Fig. 4.4: DC Inst. in Size010-03 and Size010-05}, % % title style={at={(0.5,-.2)}}, % % height=8 cm, % % width=.48\textwidth, % % X % xlabel={$n$}, % xlabel style={at={(ticklabel cs:1)}, anchor=south west}, % minor x tick num=1, % xmajorgrids=true, % % Y % ylabel={execution time}, % y unit=seconds, % % minor y tick num=1,%not applied for ymode=log % yminorgrids=true, % ymajorgrids=true, % ymode=log, % log basis y=10, % log ticks with fixed point, % % ytick=\empty, % % extra y ticks={2,5,10, 20, 30, 60, 120}, % % extra y tick labels={30s, 1, 5, 10, 20, 30}, % % % ylabel shift=-5pt, % % LEGEND % cycle multi list={colorbrewer}, % % legend style={at={(1.05,1)},anchor=north west},%legend pos=north west, % legend style={at={(0,-0.1)},anchor=north west},% % legend columns=1, % % legend entries={ {Std}, {Std-woNL}, {$\epsilon$}, {$\epsilon$-woNL}, {$\epsilon$-woNL-3R}, {IR}, {IR-woNL}, {IR-woNL-3R}, } % ] % % % % \addlegendentry{STD light a-label opt.}; % % \addplot[Std0,error bars/.cd, y dir=both, y explicit]%Size010-3 STD % % table [x=x, y=y,y error expr=\yerrstd] {%node006 % % n; x; c; p; y; yerr; nOps; % % %SIZE-010-3; % % 50; 43; 10; 3; 2.48E+01; 5.20E+01; 213840; % % 49; 49; 10; 3; 1.43E+01; 2.88E+01; 223974; % % 50; 55; 10; 3; 1.72E+01; 7.67E+01; 242642; % % 49; 61; 10; 3; 8.18E+00; 2.02E+01; 272071; % % 49; 67; 10; 3; 3.20E+00; 7.34E+00; 304432; % % }; % % % \addlegendentry{STD w/o a-label opt.}; % \addplot[Std1,error bars/.cd, y dir=both, y explicit]%Size010-3 STD % table [x=x, y=y,y error expr=\yerrstd] {%node006 % n; x; c; p; y; yerr; nOps; % %SIZE-010-3; % 50; 43; 10; 3; 1.916198E+01; 4.145642E+01; 223983 % 49; 49; 10; 3; 8.770939E+00; 1.730089E+01; 213850 % 50; 55; 10; 3; 1.117996E+01; 5.075795E+01; 242689 % 49; 61; 10; 3; 5.266592E+00; 1.354998E+01; 272120 % 49; 67; 10; 3; 2.005694E+00; 4.873908E+00; 304475 % }; % % % \addlegendentry{STD w/o letter-removal-r}; % % \addplot[Std2,error bars/.cd, y dir=both, y explicit]%Size010-3 STD % % table [x=x, y=y,y error expr=\yerrstd] {%node006 % % n; x; c; p; y; yerr; nOps; std; % % %SIZE-010-3; % % 50; 43; 10; 3; 3.899400E-01; 4.780883E-01; 3.337720E+03; 1.435028E+03; % % 49; 49; 10; 3; 3.062245E-01; 3.585885E-01; 3.741102E+03; 1.744453E+03; % % 50; 55; 10; 3; 3.555000E-01; 9.022984E-01; 4.149800E+03; 2.153299E+03; % % 49; 61; 10; 3; 4.498776E-01; 8.284288E-01; 4.756531E+03; 1.989293E+03; % % 49; 67; 10; 3; 3.336939E-01; 4.420301E-01; 5.550061E+03; 2.203945E+03; % % % % %size-010-5 % % 50; 55; 10; 5; 1.147154E+01; 1.948295E+01; 1.140524E+04; 5.595864E+03; % % 50; 61; 10; 5; 1.412568E+01; 4.244275E+01; 9.815160E+03; 7.182044E+03; % % 50; 67; 10; 5; 3.877800E+00; 1.576359E+01; 9.088260E+03; 5.267112E+03; % % 50; 73; 10; 5; 2.535760E+00; 5.588070E+00; 1.161108E+04; 4.407245E+03; % % 50; 79; 10; 5; 2.694336E+01; 9.508171E+01; 1.863238E+04; 8.585601E+03; % % % % }; % % % \addlegendentry{STD w/o a-label opt.-letter-removal-r}; % % \addplot[Std3,error bars/.cd, y dir=both, y explicit]%Size010-3 STD % % table [x=x, y=y,y error expr=\yerrstd] {%node006 % % n; x; c; p; y; yerr; nOps; std; % % %SIZE-010-3; % % 50; 43; 10; 3; 5.609200E-01; 6.539173E-01; 4.026920E+03; 1.642145E+03; % % 49; 49; 10; 3; 4.523061E-01; 5.747738E-01; 4.517776E+03; 2.180593E+03; % % 50; 55; 10; 3; 5.915200E-01; 1.729118E+00; 5.135220E+03; 2.660779E+03; % % 49; 61; 10; 3; 7.129592E-01; 1.552925E+00; 5.769041E+03; 2.408445E+03; % % 49; 67; 10; 3; 4.480204E-01; 5.934154E-01; 6.821816E+03; 2.566443E+03; % % % % %size-010-5 % % 50; 55; 10; 5; 2.084010E+01; 3.212112E+01; 1.362498E+04; 6.334823E+03; % % 50; 61; 10; 5; 2.290670E+01; 6.764999E+01; 1.183792E+04; 7.905222E+03; % % 49; 67; 10; 5; 1.654753E+01; 8.005081E+01; 1.186071E+04; 7.267109E+03; % % 50; 73; 10; 5; 9.605600E+00; 2.395515E+01; 1.486712E+04; 6.083820E+03; % % 50; 79; 10; 5; 6.510896E+01; 1.082803E+02; 2.384148E+04; 1.029529E+04; % % }; % % % \addlegendentry{STD w/o p-label-base}; % % \addplot[StdwoNL,error bars/.cd, y dir=both, y explicit] % % table [x=x, y=y,y error expr=\yerrstd] {%node006 % % n; x; c; p; y; yerr; nOps; std; % % %size-010-5 % % 50; 55; 10; 5; 6.541660E+00; 9.932361E+00; 1.092216E+04; 5.059915E+03; % % 50; 61; 10; 5; 1.199744E+01; 3.842548E+01; 9.515380E+03; 7.379989E+03; % % 50; 67; 10; 5; 3.042740E+00; 1.511443E+01; 8.626480E+03; 4.908484E+03; % % 50; 73; 10; 5; 2.134160E+00; 5.102885E+00; 1.106282E+04; 4.278080E+03; % % 50; 79; 10; 5; 1.157566E+01; 2.208122E+01; 1.828084E+04; 8.108684E+03; % % }; % \end{axis} % \end{tikzpicture} % % \end{center} % % % % % \begin{center} % % \captionsetup{justification=justified} % % \subfloat[Benchmark $N=10,|\calp|=3$.\label{SubFig:N10}]{ % % \begin{subfigure}[b]{.45\linewidth}\centering% \ 44 \leq n \leq 59, \ % \noindent % \begin{tikzpicture} % %% % %%This diagram requires pgfplots version 1.15 to be compiled without errors. % %% % \begin{axis}[ % normalsize, % title=\textbf{Fig. 4.5: DC Inst. in Size010-03 and Size010-05. Rules limited to Z}, % % title style={at={(0.5,-.2)}}, % % height=8 cm, % % width=.48\textwidth, % % X % xlabel={$n$}, % xlabel style={at={(ticklabel cs:1)}, anchor=south west}, % minor x tick num=1, % xmajorgrids=true, % % Y % ylabel={execution time}, % y unit=seconds, % % minor y tick num=1,%not applied for ymode=log % yminorgrids=true, % ymajorgrids=true, % ymode=log, % log basis y=10, % log ticks with fixed point, % % ytick=\empty, % % extra y ticks={2,5,10, 20, 30, 60, 120}, % % extra y tick labels={30s, 1, 5, 10, 20, 30}, % % % ylabel shift=-5pt, % % LEGEND % cycle multi list={colorbrewer}, % % legend style={at={(1.05,1)},anchor=north west},%legend pos=north west, % legend style={at={(0,-0.1)},anchor=north west},% % legend columns=1, % % legend entries={ {Std}, {Std-woNL}, {$\epsilon$}, {$\epsilon$-woNL}, {$\epsilon$-woNL-3R}, {IR}, {IR-woNL}, {IR-woNL-3R}, } % ] % % % \addlegendentry{STD OnlyToZ w/o letter-removal-r}; % % \addplot[StdZ2,error bars/.cd, y dir=both, y explicit]%Size010-3 STD % % table [x=x, y=y,y error expr=\yerrstd] {%node006 % % n; x; c; p; y; yerr; nOps; std; % % %SIZE-010-3; % % 50; 43; 10; 3; 6.470400E-01; 1.456664E+00; 5.326300E+03; 3.047105E+03; % % 49; 49; 10; 3; 3.882449E-01; 5.971687E-01; 5.742020E+03; 3.529194E+03; % % 50; 55; 10; 3; 1.004600E+00; 5.451161E+00; 6.208000E+03; 4.838224E+03; % % 49; 61; 10; 3; 8.789388E-01; 2.742300E+00; 7.459980E+03; 5.067422E+03; % % 49; 67; 10; 3; 4.306939E-01; 1.275221E+00; 7.893041E+03; 5.388349E+03; % % % % %SIZE-010-5; % % 50; 55; 10; 5; 1.276970E+02; 3.192985E+02; 2.818870E+04; 2.149276E+04; % % 50; 61; 10; 5; 9.354020E+01; 2.982816E+02; 2.522546E+04; 2.632054E+04; % % 50; 67; 10; 5; 1.773228E+01; 9.691834E+01; 1.894456E+04; 1.422680E+04; % % 50; 73; 10; 5; 1.023182E+01; 2.745863E+01; 2.322108E+04; 1.424620E+04; % % 50; 79; 10; 5; 6.762616E+01; 1.217596E+02; 3.368754E+04; 2.154432E+04; % % }; % % \addlegendentry{STD OnlyToZ w/o a-label opt.-letter-removal-r}; % \addplot[StdZ3,error bars/.cd, y dir=both, y explicit]%Size010-3 STD % table [x=x, y=y,y error expr=\yerrstd] {%node006 % n; x; c; p; y; yerr; nOps;std; % %SIZE-010-3; % 50; 43; 10; 3; 7.585800E-01; 1.307429E+00; 6.195040E+03; 3.402032E+03; % 49; 49; 10; 3; 6.595306E-01; 1.156672E+00; 6.945286E+03; 4.268554E+03; % 50; 55; 10; 3; 1.506940E+00; 7.819847E+00; 7.861320E+03; 6.004733E+03; % 49; 61; 10; 3; 1.430367E+00; 4.411142E+00; 9.208714E+03; 5.856690E+03; % 49; 67; 10; 3; 8.194694E-01; 2.755844E+00; 1.022059E+04; 6.519020E+03; % % %SIZE-010-5; % 50; 55; 10; 5; 145.8690204; 411.7787935; 33463.46939; 26424.14079; % 50; 61; 10; 5; 1.12E+02; 3.61E+02; 3.10E+04; 3.15E+04; % 50; 67; 10; 5; 5.97E+01; 3.47E+02; 2.51E+04; 1.96E+04; % 50; 73; 10; 5; 3.06E+01; 8.46E+01; 3.15E+04; 1.87E+04; % 50; 79; 10; 5; 234.86924; 466.7942976; 50432.92; 24005.00051; % }; % % \addlegendentry{STD w/o p-label-base}; % \addplot[StdwoNL,error bars/.cd, y dir=both, y explicit] % table [x=x, y=y,y error expr=\yerrstd] {%node006 % n; x; c; p; y; yerr; nOps; std; % %size-010-5 % 50; 55; 10; 5; 1.286192E+02; 3.926269E+02; 2.750380E+04; 1.589236E+04; % 50; 61; 10; 5; 1.158108E+02; 4.098735E+02; 2.439563E+04; 2.373891E+04; % 50; 67; 10; 5; 3.499096E+01; 2.018052E+02; 1.987524E+04; 1.557262E+04; % 50; 73; 10; 5; 1.51E+01; 4.27E+01; 2.42E+04; 1.533519E+04; % 50; 79; 10; 5; 7.47E+01; 1.37E+02; 3.470182E+04; 2.310063E+04; % }; % % \end{axis} % \end{tikzpicture} % % \end{center} % % % In the following figures the same diagrams considering NOT DC instances. % % % % \begin{center} % % \captionsetup{justification=justified} % % \subfloat[Benchmark $N=10,|\calp|=3$.\label{SubFig:N10}]{ % % \begin{subfigure}[b]{.45\linewidth}\centering% \ 44 \leq n \leq 59, \ % \noindent % \begin{tikzpicture} % %% % %%This diagram requires pgfplots version 1.15 to be compiled without errors. % %% % \begin{axis}[ % normalsize, % title=\textbf{Fig. 4.6: NOT DC Inst. in Size010-03 and Size010-05}, % % title style={at={(0.5,-.2)}}, % % height=8 cm, % % width=.48\textwidth, % % X % xlabel={$n$}, % xlabel style={at={(ticklabel cs:1)}, anchor=south west}, % minor x tick num=1, % xmajorgrids=true, % % Y % ylabel={execution time}, % y unit=seconds, % % minor y tick num=1,%not applied for ymode=log % yminorgrids=true, % ymajorgrids=true, % ymode=log, % log basis y=10, % log ticks with fixed point, % % ytick=\empty, % % extra y ticks={2,5,10, 20, 30, 60, 120}, % % extra y tick labels={30s, 1, 5, 10, 20, 30}, % % % ylabel shift=-5pt, % % LEGEND % cycle multi list={colorbrewer}, % % legend style={at={(1.05,1)},anchor=north west},%legend pos=north west, % legend style={at={(0,-0.1)},anchor=north west},% % legend columns=1, % % legend entries={ {Std}, {Std-woNL}, {$\epsilon$}, {$\epsilon$-woNL}, {$\epsilon$-woNL-3R}, {IR}, {IR-woNL}, {IR-woNL-3R}, } % ] % % % % \addlegendentry{STD light a-label opt.}; % % \addplot[Std0,error bars/.cd, y dir=both, y explicit]%Size010-3 STD % % table [x=x, y=y,y error expr=\yerrstd] {%node006 % % n; x; c; p; y; yerr; nOps; % % %SIZE-010-3; % % 50; 43; 10; 3; 3.30E+02; 7.69E+02; 1538720; % % % 49; 49; 10; 3; 1.43E+01; 2.88E+01; 223974; % % % 50; 55; 10; 3; 1.72E+01; 7.67E+01; 242642; % % % 49; 61; 10; 3; 8.18E+00; 2.02E+01; 272071; % % % 49; 67; 10; 3; 3.20E+00; 7.34E+00; 304432; % % }; % % % % \addlegendentry{STD w/o a-label opt.}; % % \addplot[Std1,error bars/.cd, y dir=both, y explicit]%Size010-3 STD % % table [x=x, y=y,y error expr=\yerrstd] {%node006 % % n; x; c; p; y; yerr; nOps; % % %SIZE-010-3; % % 50; 43; 10; 3; 1.60E+02; 0.00E+00; 207134; % % % 49; 49; 10; 3; 8.770939E+00; 1.730089E+01; 213850 % % % 50; 55; 10; 3; 1.117996E+01; 5.075795E+01; 242689 % % % 49; 61; 10; 3; 5.266592E+00; 1.354998E+01; 272120 % % % 49; 67; 10; 3; 2.005694E+00; 4.873908E+00; 304475 % % }; % % % \addlegendentry{STD w/o letter-removal-r}; % \addplot[Std2,error bars/.cd, y dir=both, y explicit]%Size010-3 STD % table [x=x, y=y,y error expr=\yerrstd] {%node006 % n; x; c; p; y; yerr; nOps; % %SIZE-010-3; % 50; 43; 10; 3; 88.52036; 342.0747973; 101778.64; 224844.779 % 50; 49; 10; 3; 58.03436735; 135.6675729; 118504.0204; 193930.0294 % 17; 55; 10; 3; 55.97038; 177.1779804; 132699.96; 328593.0325 % 50; 61; 10; 3; 7.522934E+01; 3.827925E+02; 7.413339E+04; 1.352802E+05; % 50; 67; 10; 3; 6.018940E+00; 1.592172E+01; 4.735268E+04; 1.420222E+05; % % 50; 55; 10; 5; 5.00E+02; 964.1613414; 293550.0714; 524746.1255; % 50; 61; 10; 5; 375.2071875; 777.9078929; 1.68E+05; 2.71E+05; % 50; 67; 10; 5; 167.2156842; 609.3824462; 84909.65789; 232996.3801; % 50; 73; 10; 5; 7.65E+01; 3.84E+02; 5.99E+04; 1.70E+05; % 50; 79; 10; 5; 6.81E+02; 1.04E+03; 2.10E+05; 2.49E+05; % }; % % \addlegendentry{STD w/o a-label opt.-letter-removal-r}; % \addplot[Std3,error bars/.cd, y dir=both, y explicit]%Size010-3 STD % table [x=x, y=y,y error expr=\yerrstd] {%node006 % n; x; c; p; y; yerr; nOps; % %SIZE-010-3; % 50; 43; 10; 3; 8.35E+01; 247.4205725; 83843.32653; 167830.201; % 50; 49; 10; 3; 8.47E+01; 186.2774733; 127675.7959; 210586.5892; % 17; 55; 10; 3; 7.13E+01; 230.2188316; 141051.94; 349729.9506; % 49; 61; 10; 3; 1.51E+02; 560.6839588; 129338.8261; 210508.9321; % 50; 67; 10; 3; 9.273800E+00; 2.753624E+01; 5.970334E+04; 1.891425E+05; % % % 50; 55; 10; 5; 513.1247857; 866.0351086; 295423.7857; 586094.8678; % 50; 61; 10; 5; 288.398; 626.3187866; 195840.25; 324054.2803; % 50; 67; 10; 5; 178.7309737; 612.9117846; 81959; 195296.9015; % 50; 73; 10; 5; 1.08E+02; 4.05E+02; 7.55E+04; 2.17E+05; % 50; 79; 10; 5; 891.8465; 1154.085596; 158089.875; 168451.1131; % }; % % \addlegendentry{STD w/o p-label-base}; % \addplot[StdwoNL,error bars/.cd, y dir=both, y explicit] % table [x=x, y=y,y error expr=\yerrstd] {%node006 % n; x; c; p; y; yerr; nOps; std; % %size-010-5 % 50; 55; 10; 5; 3.59E+02; 677.744292; 264119.8421; 459544.0322 % 50; 61; 10; 5; 338.6514; 779.0905888; 190790.3; 310180.7265 % 50; 67; 10; 5; 165.6265946; 616.9809386; 95938.81081; 242195.7114 % 50; 73; 10; 5; 9.11E+01; 3.90E+02; 6.03E+04; 1.69E+05 % 50; 79; 10; 5; 1058.404167; 1337.668995; 143769.6667; 154622.7019 % }; % \end{axis} % \end{tikzpicture} % % \end{center} % % % \begin{center} % % \captionsetup{justification=justified} % % \subfloat[Benchmark $N=10,|\calp|=3$.\label{SubFig:N10}]{ % % \begin{subfigure}[b]{.45\linewidth}\centering% \ 44 \leq n \leq 59, \ % \noindent % \begin{tikzpicture} % %% % %%This diagram requires pgfplots version 1.15 to be compiled without errors. % %% % \begin{axis}[ % normalsize, % title=\textbf{Fig. 4.7: NOT DC Inst. in Size010-030. Rules limited to Z}, % % title style={at={(0.5,-.2)}}, % % height=8 cm, % % width=.48\textwidth, % % X % xlabel={$n$}, % xlabel style={at={(ticklabel cs:1)}, anchor=south west}, % minor x tick num=1, % xmajorgrids=true, % % Y % ylabel={execution time}, % y unit=seconds, % % minor y tick num=1,%not applied for ymode=log % yminorgrids=true, % ymajorgrids=true, % ymode=log, % log basis y=10, % log ticks with fixed point, % % ytick=\empty, % % extra y ticks={2,5,10, 20, 30, 60, 120}, % % extra y tick labels={30s, 1, 5, 10, 20, 30}, % % % ylabel shift=-5pt, % % LEGEND % cycle multi list={colorbrewer}, % %legend style={at={(1.05,1)},anchor=north west},% % legend style={at={(0,-0.1)},anchor=north west},% % %legend pos=north west, % legend columns=1, % % legend entries={ {Std}, {Std-woNL}, {$\epsilon$}, {$\epsilon$-woNL}, {$\epsilon$-woNL-3R}, {IR}, {IR-woNL}, {IR-woNL-3R}, } % ] % % \addlegendentry{STD OnlyToZ light a-label opt.}; % % \addplot[StdZ0,error bars/.cd, y dir=both, y explicit]%Size010-3 STD % % table [x=x, y=y,y error expr=\yerrstd] {%node006 % % n; x; c; p; y; yerr; nOps; % % %SIZE-010-3; % % 50; 43; 10; 3; 4.14E+02; 7.56E+02; 2442878; % % % 49; 49; 10; 3; 2.82E+01; 6.73E+01; 302208; % % % 50; 55; 10; 3; 1.55E+01; 5.29E+01; 297711; % % % 49; 61; 10; 3; 1.51E+01; 4.78E+01; 327854; % % % 49; 67; 10; 3; 8.83E+00; 3.41E+01; 358541; % % }; % % % % \addlegendentry{STD OnlyToZ w/o a-label opt.}; % % \addplot[StdZ1,error bars/.cd, y dir=both, y explicit]%Size010-3 STD % % table [x=x, y=y,y error expr=\yerrstd] {%node006 % % n; x; c; p; y; yerr; nOps; % % %SIZE-010-3; % % 50; 43; 10; 3; 1.60E+02; 0.00E+00; 207134; % % % 49; 49; 10; 3; 2.67E+01; 6.36E+01; 302305; % % % 50; 55; 10; 3; 1.42E+01; 4.75E+01; 297791; % % % 49; 61; 10; 3; 1.73E+01; 5.54E+01; 328041; % % % 49; 67; 10; 3; 1.24E+01; 4.68E+01; 358673; % % }; % % \addlegendentry{STD OnlyToZ w/o letter-removal-r}; % \addplot[StdZ2,error bars/.cd, y dir=both, y explicit]%Size010-3 STD % table [x=x, y=y,y error expr=\yerrstd] {%node006 % n; x; c; p; y; yerr; nOps; % %SIZE-010-3; % 50; 43; 10; 3; 4.63E+01; 121.1687354; 178987.7; 181155.0701; % 50; 49; 10; 3; 48.75778; 107.3505806; 215987.44; 257175.8799 % 50; 55; 10; 3; 6.62E+01; 1.27E+02; 2.59E+05; 2.32E+05; % 49; 61; 10; 3; 3.23E+01; 5.07E+01; 2.45E+05; 2.69E+05; % 50; 67; 10; 3; 1.98E+01; 4.68E+01; 1.99E+05; 2.42E+05; % % %size-010-5 % 50; 55; 10; 5; 488.4619091; 794.3867206; 433590.4545; 474053.5424; % 50; 61; 10; 5; 480.437; 818.0485925; 439500.2727; 361160.6475; % 50; 67; 10; 5; 470.5034667; 928.5929751; 334180.2; 266737.1632; % 50; 73; 10; 5; 292.7726111; 582.8637782; 407643.4444; 368017.6181; % 50; 79; 10; 5; 929.6742857; 1223.073645; 479577.5714; 365013.4629; % }; % % \addlegendentry{STD OnlyToZ w/o a-label opt.-letter-removal-r}; % \addplot[StdZ3,error bars/.cd, y dir=both, y explicit]%Size010-3 STD % table [x=x, y=y,y error expr=\yerrstd] {%node006 % n; x; c; p; y; yerr; nOps; % %SIZE-010-3; % 50; 43; 10; 3; 64.57412; 149.1432402; 1.86E+05; 1.87E+05; % 50; 49; 10; 3; 56.1679; 121.4643148; 229549.88; 270384.4382; % 17; 55; 10; 3; 94.08052; 323.9388165; 261286.76; 285800.512; % 49; 61; 10; 3; 38.02109091; 52.49975934; 284833.8182; 234472.6103; % 50; 67; 10; 3; 3.904436E+01; 9.560137E+01; 2.558433E+05; 2.908157E+05; % % %size-010-5 % 50; 55; 10; 5; 535.0941818; 834.5746036; 445205.6364; 530455.0656; % 50; 61; 10; 5; 532.4925455; 803.17267; 491887.4545; 377206.5342; % 50; 67; 10; 5; 511.7268571; 942.8938049; 356099.7857; 289839.0517; % 50; 73; 10; 5; 439.2133571; 720.2405288; 480202.3571; 310459.7036; % 50; 79; 10; 5; 945.368; 1049.302399; 426008.2; 2.39E+05; % }; % % \addlegendentry{STD OnlyToZ w/o p-label-base}; % \addplot[StdwoNL,error bars/.cd, y dir=both, y explicit] % table [x=x, y=y,y error expr=\yerrstd] {%node006 % n; x; c; p; y; yerr; nOps; std; % %size-010-5 % 50; 55; 10; 5; 438.3146364; 787.9520731; 431746.9091; 482024.6808 % 50; 61; 10; 5; 498.4434545; 819.6178682; 459864.1818; 364590.6011 % 50; 67; 10; 5; 455.0144667; 927.024248; 305956.8; 282541.554 % 50; 73; 10; 5; 369.0093571; 715.3563501; 376438.4286; 285500.794 % 50; 79; 10; 5; 1150.342333; 1238.703133; 373491.5; 284189.7285 % }; % \end{axis} % \end{tikzpicture} % % \end{center} % % The figures confirm that labeled letter removal rule is time expensive and, considering also that it is not necessary, its removal improves the performance. % On the other hand, removing a-label optimization or p-label base optimization does not bring a significant improvement. Thereofore, in all the algorithms such % optimization still remain. \bibliographystyle{ieeetr_doi} \bibliography{bibliography} \end{document}