java -Xss1g -Xmx4000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerCHC.xml --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -s ../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf -i /storage/chc-comp/vmt-chc-benchmarks/ctigar/dillig05.c.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 05:14:23,016 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 05:14:23,018 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 05:14:23,033 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 05:14:23,033 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 05:14:23,034 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 05:14:23,035 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 05:14:23,038 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 05:14:23,041 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 05:14:23,042 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 05:14:23,043 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 05:14:23,043 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 05:14:23,044 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 05:14:23,058 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 05:14:23,058 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 05:14:23,059 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 05:14:23,061 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 05:14:23,062 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 05:14:23,064 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 05:14:23,065 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 05:14:23,066 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 05:14:23,071 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 05:14:23,071 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 05:14:23,071 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 05:14:23,075 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 05:14:23,076 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 05:14:23,077 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 05:14:23,078 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 05:14:23,085 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 05:14:23,085 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 05:14:23,086 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 05:14:23,086 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 05:14:23,086 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 05:14:23,087 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 05:14:23,088 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 05:14:23,088 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-22 05:14:23,111 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 05:14:23,111 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 05:14:23,111 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 05:14:23,111 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 05:14:23,112 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 05:14:23,113 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 05:14:23,113 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 05:14:23,113 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 05:14:23,113 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 05:14:23,113 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 05:14:23,114 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 05:14:23,114 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 05:14:23,114 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 05:14:23,114 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 05:14:23,114 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 05:14:23,115 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 05:14:23,115 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 05:14:23,120 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 05:14:23,120 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 05:14:23,162 INFO ]: Repository-Root is: /tmp [2018-06-22 05:14:23,184 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 05:14:23,190 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 05:14:23,192 INFO ]: Initializing SmtParser... [2018-06-22 05:14:23,192 INFO ]: SmtParser initialized [2018-06-22 05:14:23,194 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/dillig05.c.smt2 [2018-06-22 05:14:23,195 INFO ]: Parsing .smt2 file as a set of Horn Clauses No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2018-06-22 05:14:23,541 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/dillig05.c.smt2 unknown [2018-06-22 05:14:23,839 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/dillig05.c.smt2 [2018-06-22 05:14:23,843 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 05:14:23,848 INFO ]: Walking toolchain with 4 elements. [2018-06-22 05:14:23,849 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 05:14:23,849 INFO ]: Initializing ChcToBoogie... [2018-06-22 05:14:23,849 INFO ]: ChcToBoogie initialized [2018-06-22 05:14:23,852 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 05:14:23" (1/1) ... [2018-06-22 05:14:23,916 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:14:23 Unit [2018-06-22 05:14:23,916 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 05:14:23,920 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 05:14:23,921 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 05:14:23,921 INFO ]: Boogie Preprocessor initialized [2018-06-22 05:14:23,943 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:14:23" (1/1) ... [2018-06-22 05:14:23,943 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:14:23" (1/1) ... [2018-06-22 05:14:23,951 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:14:23" (1/1) ... [2018-06-22 05:14:23,951 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:14:23" (1/1) ... [2018-06-22 05:14:23,966 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:14:23" (1/1) ... [2018-06-22 05:14:23,968 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:14:23" (1/1) ... [2018-06-22 05:14:23,969 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:14:23" (1/1) ... [2018-06-22 05:14:23,971 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 05:14:23,972 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 05:14:23,972 INFO ]: Initializing RCFGBuilder... [2018-06-22 05:14:23,972 INFO ]: RCFGBuilder initialized [2018-06-22 05:14:23,973 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:14:23" (1/1) ... No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2018-06-22 05:14:23,985 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-22 05:14:23,985 INFO ]: Found specification of procedure gotoProc [2018-06-22 05:14:23,985 INFO ]: Found implementation of procedure gotoProc [2018-06-22 05:14:23,985 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 05:14:23,985 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 05:14:23,985 INFO ]: Found implementation of procedure Ultimate.START Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 05:14:24,186 INFO ]: Using library mode [2018-06-22 05:14:24,187 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 05:14:24 BoogieIcfgContainer [2018-06-22 05:14:24,187 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 05:14:24,188 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 05:14:24,188 INFO ]: Initializing TraceAbstraction... [2018-06-22 05:14:24,192 INFO ]: TraceAbstraction initialized [2018-06-22 05:14:24,192 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 05:14:23" (1/3) ... [2018-06-22 05:14:24,193 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@50070674 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 05:14:24, skipping insertion in model container [2018-06-22 05:14:24,193 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:14:23" (2/3) ... [2018-06-22 05:14:24,193 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@50070674 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 05:14:24, skipping insertion in model container [2018-06-22 05:14:24,193 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 05:14:24" (3/3) ... [2018-06-22 05:14:24,195 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 05:14:24,203 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 05:14:24,210 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 05:14:24,248 INFO ]: Using default assertion order modulation [2018-06-22 05:14:24,248 INFO ]: Interprodecural is true [2018-06-22 05:14:24,248 INFO ]: Hoare is false [2018-06-22 05:14:24,248 INFO ]: Compute interpolants for FPandBP [2018-06-22 05:14:24,248 INFO ]: Backedges is TWOTRACK [2018-06-22 05:14:24,249 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 05:14:24,249 INFO ]: Difference is false [2018-06-22 05:14:24,249 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 05:14:24,249 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 05:14:24,262 INFO ]: Start isEmpty. Operand 10 states. [2018-06-22 05:14:24,272 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-22 05:14:24,272 INFO ]: Found error trace [2018-06-22 05:14:24,273 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:14:24,273 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:14:24,279 INFO ]: Analyzing trace with hash 1285054476, now seen corresponding path program 1 times [2018-06-22 05:14:24,281 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:14:24,281 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:14:24,315 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:14:24,315 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 05:14:24,315 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:14:24,360 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:14:24,452 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:14:24,454 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 05:14:24,454 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-22 05:14:24,455 INFO ]: Interpolant automaton has 3 states [2018-06-22 05:14:24,466 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-22 05:14:24,467 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-22 05:14:24,469 INFO ]: Start difference. First operand 10 states. Second operand 3 states. [2018-06-22 05:14:24,543 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 05:14:24,543 INFO ]: Finished difference Result 9 states and 9 transitions. [2018-06-22 05:14:24,543 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-22 05:14:24,545 INFO ]: Start accepts. Automaton has 3 states. Word has length 7 [2018-06-22 05:14:24,545 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 05:14:24,559 INFO ]: With dead ends: 9 [2018-06-22 05:14:24,559 INFO ]: Without dead ends: 9 [2018-06-22 05:14:24,562 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-22 05:14:24,592 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-22 05:14:24,626 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-22 05:14:24,627 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-22 05:14:24,628 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 9 transitions. [2018-06-22 05:14:24,629 INFO ]: Start accepts. Automaton has 9 states and 9 transitions. Word has length 7 [2018-06-22 05:14:24,629 INFO ]: Finished accepts. word is rejected. [2018-06-22 05:14:24,629 INFO ]: Abstraction has 9 states and 9 transitions. [2018-06-22 05:14:24,629 INFO ]: Interpolant automaton has 3 states. [2018-06-22 05:14:24,630 INFO ]: Start isEmpty. Operand 9 states and 9 transitions. [2018-06-22 05:14:24,630 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-22 05:14:24,630 INFO ]: Found error trace [2018-06-22 05:14:24,630 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:14:24,630 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:14:24,630 INFO ]: Analyzing trace with hash 1180100628, now seen corresponding path program 1 times [2018-06-22 05:14:24,630 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:14:24,630 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:14:24,635 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:14:24,635 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 05:14:24,635 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:14:24,669 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:14:24,764 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:14:24,764 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 05:14:24,764 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 05:14:24,773 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 05:14:24,828 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:14:24,841 INFO ]: Computing forward predicates... [2018-06-22 05:14:25,099 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:14:25,133 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 05:14:25,133 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 5 [2018-06-22 05:14:25,134 INFO ]: Interpolant automaton has 5 states [2018-06-22 05:14:25,134 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-22 05:14:25,134 INFO ]: CoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-22 05:14:25,134 INFO ]: Start difference. First operand 9 states and 9 transitions. Second operand 5 states. [2018-06-22 05:14:25,302 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 05:14:25,303 INFO ]: Finished difference Result 11 states and 11 transitions. [2018-06-22 05:14:25,303 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-22 05:14:25,304 INFO ]: Start accepts. Automaton has 5 states. Word has length 8 [2018-06-22 05:14:25,304 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 05:14:25,304 INFO ]: With dead ends: 11 [2018-06-22 05:14:25,304 INFO ]: Without dead ends: 11 [2018-06-22 05:14:25,305 INFO ]: 0 DeclaredPredicates, 12 GetRequests, 7 SyntacticMatches, 1 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=14, Invalid=16, Unknown=0, NotChecked=0, Total=30 [2018-06-22 05:14:25,305 INFO ]: Start minimizeSevpa. Operand 11 states. [2018-06-22 05:14:25,306 INFO ]: Finished minimizeSevpa. Reduced states from 11 to 11. [2018-06-22 05:14:25,307 INFO ]: Start removeUnreachable. Operand 11 states. [2018-06-22 05:14:25,307 INFO ]: Finished removeUnreachable. Reduced from 11 states to 11 states and 11 transitions. [2018-06-22 05:14:25,307 INFO ]: Start accepts. Automaton has 11 states and 11 transitions. Word has length 8 [2018-06-22 05:14:25,307 INFO ]: Finished accepts. word is rejected. [2018-06-22 05:14:25,307 INFO ]: Abstraction has 11 states and 11 transitions. [2018-06-22 05:14:25,307 INFO ]: Interpolant automaton has 5 states. [2018-06-22 05:14:25,307 INFO ]: Start isEmpty. Operand 11 states and 11 transitions. [2018-06-22 05:14:25,308 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-22 05:14:25,308 INFO ]: Found error trace [2018-06-22 05:14:25,308 INFO ]: trace histogram [3, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:14:25,308 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:14:25,308 INFO ]: Analyzing trace with hash 145098516, now seen corresponding path program 2 times [2018-06-22 05:14:25,308 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:14:25,308 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:14:25,309 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:14:25,309 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 05:14:25,309 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:14:25,454 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:14:25,723 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:14:25,723 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 05:14:25,723 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 05:14:25,731 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 05:14:25,832 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 05:14:25,832 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:14:25,836 INFO ]: Computing forward predicates... [2018-06-22 05:14:26,785 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 05:14:27,799 WARN ]: Spent 169.00 ms on a formula simplification. DAG size of input: 28 DAG size of output: 11 [2018-06-22 05:14:27,907 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:14:27,928 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 05:14:27,928 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 8 [2018-06-22 05:14:27,928 INFO ]: Interpolant automaton has 8 states [2018-06-22 05:14:27,929 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-22 05:14:27,929 INFO ]: CoverageRelationStatistics Valid=19, Invalid=37, Unknown=0, NotChecked=0, Total=56 [2018-06-22 05:14:27,929 INFO ]: Start difference. First operand 11 states and 11 transitions. Second operand 8 states. [2018-06-22 05:14:28,270 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 05:14:28,270 INFO ]: Finished difference Result 12 states and 12 transitions. [2018-06-22 05:14:28,270 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 05:14:28,270 INFO ]: Start accepts. Automaton has 8 states. Word has length 10 [2018-06-22 05:14:28,271 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 05:14:28,271 INFO ]: With dead ends: 12 [2018-06-22 05:14:28,271 INFO ]: Without dead ends: 12 [2018-06-22 05:14:28,271 INFO ]: 0 DeclaredPredicates, 19 GetRequests, 7 SyntacticMatches, 2 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=49, Invalid=83, Unknown=0, NotChecked=0, Total=132 [2018-06-22 05:14:28,271 INFO ]: Start minimizeSevpa. Operand 12 states. [2018-06-22 05:14:28,272 INFO ]: Finished minimizeSevpa. Reduced states from 12 to 12. [2018-06-22 05:14:28,272 INFO ]: Start removeUnreachable. Operand 12 states. [2018-06-22 05:14:28,273 INFO ]: Finished removeUnreachable. Reduced from 12 states to 12 states and 12 transitions. [2018-06-22 05:14:28,273 INFO ]: Start accepts. Automaton has 12 states and 12 transitions. Word has length 10 [2018-06-22 05:14:28,273 INFO ]: Finished accepts. word is rejected. [2018-06-22 05:14:28,273 INFO ]: Abstraction has 12 states and 12 transitions. [2018-06-22 05:14:28,273 INFO ]: Interpolant automaton has 8 states. [2018-06-22 05:14:28,273 INFO ]: Start isEmpty. Operand 12 states and 12 transitions. [2018-06-22 05:14:28,273 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-22 05:14:28,273 INFO ]: Found error trace [2018-06-22 05:14:28,273 INFO ]: trace histogram [4, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:14:28,274 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:14:28,274 INFO ]: Analyzing trace with hash 201204236, now seen corresponding path program 3 times [2018-06-22 05:14:28,274 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:14:28,274 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:14:28,275 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:14:28,275 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 05:14:28,275 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:14:28,326 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:14:28,527 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:14:28,527 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 05:14:28,527 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 05:14:28,541 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 05:14:28,614 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-06-22 05:14:28,614 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:14:28,618 INFO ]: Computing forward predicates... [2018-06-22 05:14:32,343 WARN ]: Spent 279.00 ms on a formula simplification. DAG size of input: 22 DAG size of output: 11 [2018-06-22 05:14:32,823 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:14:32,857 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 05:14:32,857 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 9 [2018-06-22 05:14:32,857 INFO ]: Interpolant automaton has 9 states [2018-06-22 05:14:32,858 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-22 05:14:32,858 INFO ]: CoverageRelationStatistics Valid=22, Invalid=50, Unknown=0, NotChecked=0, Total=72 [2018-06-22 05:14:32,858 INFO ]: Start difference. First operand 12 states and 12 transitions. Second operand 9 states. [2018-06-22 05:14:33,334 WARN ]: Spent 184.00 ms on a formula simplification. DAG size of input: 18 DAG size of output: 17 [2018-06-22 05:14:33,482 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 05:14:33,483 INFO ]: Finished difference Result 13 states and 13 transitions. [2018-06-22 05:14:33,483 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-22 05:14:33,483 INFO ]: Start accepts. Automaton has 9 states. Word has length 11 [2018-06-22 05:14:33,483 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 05:14:33,483 INFO ]: With dead ends: 13 [2018-06-22 05:14:33,483 INFO ]: Without dead ends: 13 [2018-06-22 05:14:33,484 INFO ]: 0 DeclaredPredicates, 22 GetRequests, 7 SyntacticMatches, 3 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 27 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=65, Invalid=117, Unknown=0, NotChecked=0, Total=182 [2018-06-22 05:14:33,484 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-22 05:14:33,485 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-22 05:14:33,486 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-22 05:14:33,488 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 13 transitions. [2018-06-22 05:14:33,488 INFO ]: Start accepts. Automaton has 13 states and 13 transitions. Word has length 11 [2018-06-22 05:14:33,488 INFO ]: Finished accepts. word is rejected. [2018-06-22 05:14:33,488 INFO ]: Abstraction has 13 states and 13 transitions. [2018-06-22 05:14:33,488 INFO ]: Interpolant automaton has 9 states. [2018-06-22 05:14:33,488 INFO ]: Start isEmpty. Operand 13 states and 13 transitions. [2018-06-22 05:14:33,488 INFO ]: Finished isEmpty. Found accepting run of length 13 [2018-06-22 05:14:33,488 INFO ]: Found error trace [2018-06-22 05:14:33,488 INFO ]: trace histogram [5, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:14:33,488 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:14:33,488 INFO ]: Analyzing trace with hash 1940481556, now seen corresponding path program 4 times [2018-06-22 05:14:33,488 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:14:33,488 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:14:33,489 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:14:33,489 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 05:14:33,489 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:14:33,536 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:14:33,741 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:14:33,741 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 05:14:33,741 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 05:14:33,747 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 05:14:33,805 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 05:14:33,805 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:14:33,809 INFO ]: Computing forward predicates... [2018-06-22 05:14:35,736 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:14:35,757 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 05:14:35,757 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 10 [2018-06-22 05:14:35,757 INFO ]: Interpolant automaton has 10 states [2018-06-22 05:14:35,757 INFO ]: Constructing interpolant automaton starting with 10 interpolants. [2018-06-22 05:14:35,757 INFO ]: CoverageRelationStatistics Valid=30, Invalid=60, Unknown=0, NotChecked=0, Total=90 [2018-06-22 05:14:35,758 INFO ]: Start difference. First operand 13 states and 13 transitions. Second operand 10 states. [2018-06-22 05:14:36,054 WARN ]: Spent 119.00 ms on a formula simplification that was a NOOP. DAG size: 14 [2018-06-22 05:14:36,099 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 05:14:36,099 INFO ]: Finished difference Result 14 states and 14 transitions. [2018-06-22 05:14:36,099 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-22 05:14:36,099 INFO ]: Start accepts. Automaton has 10 states. Word has length 12 [2018-06-22 05:14:36,099 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 05:14:36,100 INFO ]: With dead ends: 14 [2018-06-22 05:14:36,100 INFO ]: Without dead ends: 14 [2018-06-22 05:14:36,100 INFO ]: 0 DeclaredPredicates, 25 GetRequests, 7 SyntacticMatches, 4 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 53 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=92, Invalid=148, Unknown=0, NotChecked=0, Total=240 [2018-06-22 05:14:36,100 INFO ]: Start minimizeSevpa. Operand 14 states. [2018-06-22 05:14:36,101 INFO ]: Finished minimizeSevpa. Reduced states from 14 to 14. [2018-06-22 05:14:36,101 INFO ]: Start removeUnreachable. Operand 14 states. [2018-06-22 05:14:36,102 INFO ]: Finished removeUnreachable. Reduced from 14 states to 14 states and 14 transitions. [2018-06-22 05:14:36,102 INFO ]: Start accepts. Automaton has 14 states and 14 transitions. Word has length 12 [2018-06-22 05:14:36,102 INFO ]: Finished accepts. word is rejected. [2018-06-22 05:14:36,102 INFO ]: Abstraction has 14 states and 14 transitions. [2018-06-22 05:14:36,102 INFO ]: Interpolant automaton has 10 states. [2018-06-22 05:14:36,102 INFO ]: Start isEmpty. Operand 14 states and 14 transitions. [2018-06-22 05:14:36,102 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 05:14:36,102 INFO ]: Found error trace [2018-06-22 05:14:36,103 INFO ]: trace histogram [6, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:14:36,103 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:14:36,103 INFO ]: Analyzing trace with hash 23503628, now seen corresponding path program 5 times [2018-06-22 05:14:36,103 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:14:36,103 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:14:36,104 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:14:36,104 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 05:14:36,104 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:14:36,170 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:14:36,353 INFO ]: Checked inductivity of 21 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:14:36,354 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 05:14:36,354 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 05:14:36,360 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 05:14:36,441 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) [2018-06-22 05:14:36,441 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:14:36,446 INFO ]: Computing forward predicates... [2018-06-22 05:14:37,637 INFO ]: Checked inductivity of 21 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:14:37,658 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 05:14:37,658 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 12 [2018-06-22 05:14:37,658 INFO ]: Interpolant automaton has 12 states [2018-06-22 05:14:37,659 INFO ]: Constructing interpolant automaton starting with 12 interpolants. [2018-06-22 05:14:37,659 INFO ]: CoverageRelationStatistics Valid=38, Invalid=94, Unknown=0, NotChecked=0, Total=132 [2018-06-22 05:14:37,659 INFO ]: Start difference. First operand 14 states and 14 transitions. Second operand 12 states. [2018-06-22 05:14:38,021 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 05:14:38,021 INFO ]: Finished difference Result 16 states and 16 transitions. [2018-06-22 05:14:38,021 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-22 05:14:38,021 INFO ]: Start accepts. Automaton has 12 states. Word has length 13 [2018-06-22 05:14:38,021 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 05:14:38,021 INFO ]: With dead ends: 16 [2018-06-22 05:14:38,021 INFO ]: Without dead ends: 16 [2018-06-22 05:14:38,022 INFO ]: 0 DeclaredPredicates, 29 GetRequests, 7 SyntacticMatches, 4 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 63 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=130, Invalid=250, Unknown=0, NotChecked=0, Total=380 [2018-06-22 05:14:38,022 INFO ]: Start minimizeSevpa. Operand 16 states. [2018-06-22 05:14:38,024 INFO ]: Finished minimizeSevpa. Reduced states from 16 to 16. [2018-06-22 05:14:38,025 INFO ]: Start removeUnreachable. Operand 16 states. [2018-06-22 05:14:38,025 INFO ]: Finished removeUnreachable. Reduced from 16 states to 16 states and 16 transitions. [2018-06-22 05:14:38,025 INFO ]: Start accepts. Automaton has 16 states and 16 transitions. Word has length 13 [2018-06-22 05:14:38,025 INFO ]: Finished accepts. word is rejected. [2018-06-22 05:14:38,025 INFO ]: Abstraction has 16 states and 16 transitions. [2018-06-22 05:14:38,025 INFO ]: Interpolant automaton has 12 states. [2018-06-22 05:14:38,025 INFO ]: Start isEmpty. Operand 16 states and 16 transitions. [2018-06-22 05:14:38,026 INFO ]: Finished isEmpty. Found accepting run of length 16 [2018-06-22 05:14:38,026 INFO ]: Found error trace [2018-06-22 05:14:38,026 INFO ]: trace histogram [8, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:14:38,026 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:14:38,026 INFO ]: Analyzing trace with hash 1051911180, now seen corresponding path program 6 times [2018-06-22 05:14:38,026 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:14:38,026 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:14:38,027 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:14:38,027 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 05:14:38,027 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:14:38,147 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:14:38,803 WARN ]: Spent 397.00 ms on a formula simplification. DAG size of input: 8 DAG size of output: 7 [2018-06-22 05:14:39,251 WARN ]: Spent 372.00 ms on a formula simplification that was a NOOP. DAG size: 10 [2018-06-22 05:14:39,529 WARN ]: Spent 102.00 ms on a formula simplification that was a NOOP. DAG size: 13 [2018-06-22 05:14:39,540 INFO ]: Checked inductivity of 36 backedges. 0 proven. 36 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:14:39,540 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 05:14:39,540 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 05:14:39,554 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-22 05:14:39,623 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 5 check-sat command(s) [2018-06-22 05:14:39,623 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:14:39,628 INFO ]: Computing forward predicates... [2018-06-22 05:14:43,995 INFO ]: Checked inductivity of 36 backedges. 0 proven. 36 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:14:44,016 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 05:14:44,016 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11] total 14 [2018-06-22 05:14:44,016 INFO ]: Interpolant automaton has 14 states [2018-06-22 05:14:44,017 INFO ]: Constructing interpolant automaton starting with 14 interpolants. [2018-06-22 05:14:44,017 INFO ]: CoverageRelationStatistics Valid=53, Invalid=129, Unknown=0, NotChecked=0, Total=182 [2018-06-22 05:14:44,017 INFO ]: Start difference. First operand 16 states and 16 transitions. Second operand 14 states. [2018-06-22 05:14:44,448 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 05:14:44,448 INFO ]: Finished difference Result 18 states and 18 transitions. [2018-06-22 05:14:44,448 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-06-22 05:14:44,448 INFO ]: Start accepts. Automaton has 14 states. Word has length 15 [2018-06-22 05:14:44,449 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 05:14:44,449 INFO ]: With dead ends: 18 [2018-06-22 05:14:44,449 INFO ]: Without dead ends: 18 [2018-06-22 05:14:44,450 INFO ]: 0 DeclaredPredicates, 34 GetRequests, 7 SyntacticMatches, 6 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 123 ImplicationChecksByTransitivity, 1.8s TimeCoverageRelationStatistics Valid=173, Invalid=333, Unknown=0, NotChecked=0, Total=506 [2018-06-22 05:14:44,450 INFO ]: Start minimizeSevpa. Operand 18 states. [2018-06-22 05:14:44,451 INFO ]: Finished minimizeSevpa. Reduced states from 18 to 18. [2018-06-22 05:14:44,452 INFO ]: Start removeUnreachable. Operand 18 states. [2018-06-22 05:14:44,452 INFO ]: Finished removeUnreachable. Reduced from 18 states to 18 states and 18 transitions. [2018-06-22 05:14:44,452 INFO ]: Start accepts. Automaton has 18 states and 18 transitions. Word has length 15 [2018-06-22 05:14:44,452 INFO ]: Finished accepts. word is rejected. [2018-06-22 05:14:44,452 INFO ]: Abstraction has 18 states and 18 transitions. [2018-06-22 05:14:44,452 INFO ]: Interpolant automaton has 14 states. [2018-06-22 05:14:44,452 INFO ]: Start isEmpty. Operand 18 states and 18 transitions. [2018-06-22 05:14:44,453 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-22 05:14:44,453 INFO ]: Found error trace [2018-06-22 05:14:44,453 INFO ]: trace histogram [10, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:14:44,453 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:14:44,453 INFO ]: Analyzing trace with hash 1509090572, now seen corresponding path program 7 times [2018-06-22 05:14:44,453 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:14:44,453 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:14:44,453 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:14:44,454 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 05:14:44,454 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:14:44,641 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:14:44,930 WARN ]: Spent 101.00 ms on a formula simplification that was a NOOP. DAG size: 4 [2018-06-22 05:14:45,231 INFO ]: Checked inductivity of 55 backedges. 0 proven. 55 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:14:45,231 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 05:14:45,231 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 05:14:45,244 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 05:14:45,303 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:14:45,308 INFO ]: Computing forward predicates... [2018-06-22 05:14:47,022 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 05:14:47,080 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 05:14:54,177 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 05:14:56,824 WARN ]: Spent 120.00 ms on a formula simplification. DAG size of input: 73 DAG size of output: 20 [2018-06-22 05:14:57,060 INFO ]: Checked inductivity of 55 backedges. 0 proven. 55 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:14:57,081 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 05:14:57,081 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 18 [2018-06-22 05:14:57,082 INFO ]: Interpolant automaton has 18 states [2018-06-22 05:14:57,082 INFO ]: Constructing interpolant automaton starting with 18 interpolants. [2018-06-22 05:14:57,082 INFO ]: CoverageRelationStatistics Valid=76, Invalid=230, Unknown=0, NotChecked=0, Total=306 [2018-06-22 05:14:57,082 INFO ]: Start difference. First operand 18 states and 18 transitions. Second operand 18 states. [2018-06-22 05:14:57,238 WARN ]: Spent 100.00 ms on a formula simplification. DAG size of input: 41 DAG size of output: 34 [2018-06-22 05:14:57,467 WARN ]: Spent 198.00 ms on a formula simplification. DAG size of input: 37 DAG size of output: 35 [2018-06-22 05:14:57,812 WARN ]: Spent 105.00 ms on a formula simplification. DAG size of input: 31 DAG size of output: 30 [2018-06-22 05:14:58,092 WARN ]: Spent 180.00 ms on a formula simplification. DAG size of input: 23 DAG size of output: 23 [2018-06-22 05:14:58,232 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 05:14:58,232 INFO ]: Finished difference Result 19 states and 19 transitions. [2018-06-22 05:14:58,232 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-06-22 05:14:58,233 INFO ]: Start accepts. Automaton has 18 states. Word has length 17 [2018-06-22 05:14:58,233 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 05:14:58,233 INFO ]: With dead ends: 19 [2018-06-22 05:14:58,233 INFO ]: Without dead ends: 19 [2018-06-22 05:14:58,233 INFO ]: 0 DeclaredPredicates, 40 GetRequests, 7 SyntacticMatches, 6 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 163 ImplicationChecksByTransitivity, 2.0s TimeCoverageRelationStatistics Valid=265, Invalid=547, Unknown=0, NotChecked=0, Total=812 [2018-06-22 05:14:58,234 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-22 05:14:58,235 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-06-22 05:14:58,235 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-22 05:14:58,235 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 19 transitions. [2018-06-22 05:14:58,235 INFO ]: Start accepts. Automaton has 19 states and 19 transitions. Word has length 17 [2018-06-22 05:14:58,235 INFO ]: Finished accepts. word is rejected. [2018-06-22 05:14:58,235 INFO ]: Abstraction has 19 states and 19 transitions. [2018-06-22 05:14:58,235 INFO ]: Interpolant automaton has 18 states. [2018-06-22 05:14:58,235 INFO ]: Start isEmpty. Operand 19 states and 19 transitions. [2018-06-22 05:14:58,235 INFO ]: Finished isEmpty. Found accepting run of length 19 [2018-06-22 05:14:58,235 INFO ]: Found error trace [2018-06-22 05:14:58,235 INFO ]: trace histogram [11, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:14:58,235 INFO ]: === Iteration 9 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:14:58,236 INFO ]: Analyzing trace with hash -464714988, now seen corresponding path program 8 times [2018-06-22 05:14:58,236 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:14:58,236 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:14:58,237 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:14:58,237 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 05:14:58,237 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:14:58,352 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:14:59,049 WARN ]: Spent 399.00 ms on a formula simplification. DAG size of input: 8 DAG size of output: 6 [2018-06-22 05:14:59,344 WARN ]: Spent 218.00 ms on a formula simplification. DAG size of input: 17 DAG size of output: 17 [2018-06-22 05:14:59,588 INFO ]: Checked inductivity of 66 backedges. 0 proven. 66 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:14:59,588 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 05:14:59,588 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 05:14:59,594 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 05:14:59,672 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 05:14:59,672 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:14:59,679 INFO ]: Computing forward predicates... [2018-06-22 05:15:00,785 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 05:15:05,914 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 05:15:05,958 WARN ]: expecting exponential blowup for input size 7 [2018-06-22 05:15:21,105 WARN ]: expecting exponential blowup for input size 7 Received shutdown request... [2018-06-22 05:15:28,137 INFO ]: Timeout while computing interpolants [2018-06-22 05:15:28,338 WARN ]: Destroyed unattended storables created during the last iteration: 10 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 05:15:28,338 WARN ]: Verification canceled [2018-06-22 05:15:28,342 WARN ]: Timeout [2018-06-22 05:15:28,342 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 05:15:28 BoogieIcfgContainer [2018-06-22 05:15:28,342 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 05:15:28,343 INFO ]: Toolchain (without parser) took 64499.49 ms. Allocated memory was 304.6 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 257.2 MB in the beginning and 249.8 MB in the end (delta: 7.3 MB). Peak memory consumption was 1.2 GB. Max. memory is 3.6 GB. [2018-06-22 05:15:28,344 INFO ]: SmtParser took 0.12 ms. Allocated memory is still 304.6 MB. Free memory is still 269.2 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 05:15:28,344 INFO ]: ChcToBoogie took 70.96 ms. Allocated memory is still 304.6 MB. Free memory was 257.2 MB in the beginning and 255.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 05:15:28,345 INFO ]: Boogie Preprocessor took 50.71 ms. Allocated memory is still 304.6 MB. Free memory was 255.2 MB in the beginning and 253.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 05:15:28,345 INFO ]: RCFGBuilder took 214.91 ms. Allocated memory is still 304.6 MB. Free memory was 253.2 MB in the beginning and 245.2 MB in the end (delta: 8.0 MB). Peak memory consumption was 8.0 MB. Max. memory is 3.6 GB. [2018-06-22 05:15:28,348 INFO ]: TraceAbstraction took 64153.93 ms. Allocated memory was 304.6 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 245.2 MB in the beginning and 249.8 MB in the end (delta: -4.7 MB). Peak memory consumption was 1.2 GB. Max. memory is 3.6 GB. [2018-06-22 05:15:28,351 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.12 ms. Allocated memory is still 304.6 MB. Free memory is still 269.2 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 70.96 ms. Allocated memory is still 304.6 MB. Free memory was 257.2 MB in the beginning and 255.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 50.71 ms. Allocated memory is still 304.6 MB. Free memory was 255.2 MB in the beginning and 253.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 214.91 ms. Allocated memory is still 304.6 MB. Free memory was 253.2 MB in the beginning and 245.2 MB in the end (delta: 8.0 MB). Peak memory consumption was 8.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 64153.93 ms. Allocated memory was 304.6 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 245.2 MB in the beginning and 249.8 MB in the end (delta: -4.7 MB). Peak memory consumption was 1.2 GB. Max. memory is 3.6 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [UNKNOWN] : Timeout (TraceAbstraction) Unable to prove that assertion always holds (line 0). Cancelled while BasicCegarLoop was analyzing trace of length 19 with TraceHistMax 11, while TraceCheckSpWp was constructing forward predicates, while PredicateComparison was comparing new predicate (quantifier-free) to 18 known predicates. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 10 locations, 1 error locations. TIMEOUT Result, 64.1s OverallTime, 9 OverallIterations, 11 TraceHistogramMax, 3.5s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 56 SDtfs, 29 SDslu, 219 SDs, 0 SdLazy, 89 SolverSat, 57 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.4s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 184 GetRequests, 51 SyntacticMatches, 26 SemanticMatches, 107 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 445 ImplicationChecksByTransitivity, 7.5s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=19occurred in iteration=8, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s AbstIntTime, 0 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 0.0s AutomataMinimizationTime, 8 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.1s SsaConstructionTime, 1.0s SatisfiabilityAnalysisTime, 28.8s InterpolantComputationTime, 179 NumberOfCodeBlocks, 179 NumberOfCodeBlocksAsserted, 25 NumberOfCheckSat, 164 ConstructedInterpolants, 0 QuantifiedInterpolants, 13193 SizeOfPredicates, 28 NumberOfNonLiveVariables, 1513 ConjunctsInSsa, 370 ConjunctsInUnsatCore, 15 InterpolantComputations, 1 PerfectInterpolantSequences, 0/288 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, ReuseStatistics: No data available RESULT: Ultimate could not prove your program: Timeout Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/dillig05.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_05-15-28-364.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/dillig05.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_05-15-28-364.csv Completed graceful shutdown