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/hopv/lia/termination/McCarthy9103.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 01:57:16,517 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 01:57:16,519 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 01:57:16,531 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 01:57:16,532 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 01:57:16,533 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 01:57:16,537 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 01:57:16,540 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 01:57:16,541 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 01:57:16,544 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 01:57:16,545 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 01:57:16,545 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 01:57:16,546 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 01:57:16,551 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 01:57:16,552 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 01:57:16,552 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 01:57:16,565 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 01:57:16,567 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 01:57:16,569 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 01:57:16,570 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 01:57:16,571 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 01:57:16,577 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 01:57:16,578 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 01:57:16,578 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 01:57:16,579 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 01:57:16,580 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 01:57:16,584 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 01:57:16,585 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 01:57:16,586 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 01:57:16,586 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 01:57:16,587 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 01:57:16,590 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 01:57:16,590 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 01:57:16,591 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 01:57:16,591 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 01:57:16,592 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-22 01:57:16,605 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 01:57:16,605 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 01:57:16,606 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 01:57:16,606 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 01:57:16,607 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 01:57:16,607 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 01:57:16,607 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 01:57:16,608 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 01:57:16,608 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 01:57:16,608 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 01:57:16,608 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 01:57:16,609 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 01:57:16,609 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 01:57:16,609 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 01:57:16,609 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 01:57:16,609 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 01:57:16,610 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 01:57:16,611 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 01:57:16,611 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 01:57:16,658 INFO ]: Repository-Root is: /tmp [2018-06-22 01:57:16,681 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 01:57:16,688 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 01:57:16,690 INFO ]: Initializing SmtParser... [2018-06-22 01:57:16,690 INFO ]: SmtParser initialized [2018-06-22 01:57:16,691 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/hopv/lia/termination/McCarthy9103.smt2 [2018-06-22 01:57:16,693 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 01:57:16,794 INFO ]: Executing SMT file /storage/chc-comp/hopv/lia/termination/McCarthy9103.smt2 unknown [2018-06-22 01:57:17,160 INFO ]: Succesfully executed SMT file /storage/chc-comp/hopv/lia/termination/McCarthy9103.smt2 [2018-06-22 01:57:17,165 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 01:57:17,174 INFO ]: Walking toolchain with 4 elements. [2018-06-22 01:57:17,174 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 01:57:17,174 INFO ]: Initializing ChcToBoogie... [2018-06-22 01:57:17,174 INFO ]: ChcToBoogie initialized [2018-06-22 01:57:17,178 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 01:57:17" (1/1) ... [2018-06-22 01:57:17,253 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:57:17 Unit [2018-06-22 01:57:17,253 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 01:57:17,257 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 01:57:17,257 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 01:57:17,257 INFO ]: Boogie Preprocessor initialized [2018-06-22 01:57:17,277 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:57:17" (1/1) ... [2018-06-22 01:57:17,277 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:57:17" (1/1) ... [2018-06-22 01:57:17,284 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:57:17" (1/1) ... [2018-06-22 01:57:17,284 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:57:17" (1/1) ... [2018-06-22 01:57:17,292 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:57:17" (1/1) ... [2018-06-22 01:57:17,303 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:57:17" (1/1) ... [2018-06-22 01:57:17,306 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:57:17" (1/1) ... [2018-06-22 01:57:17,309 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 01:57:17,309 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 01:57:17,309 INFO ]: Initializing RCFGBuilder... [2018-06-22 01:57:17,309 INFO ]: RCFGBuilder initialized [2018-06-22 01:57:17,310 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:57:17" (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 01:57:17,334 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-22 01:57:17,334 INFO ]: Found specification of procedure gotoProc [2018-06-22 01:57:17,334 INFO ]: Found implementation of procedure gotoProc [2018-06-22 01:57:17,334 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 01:57:17,334 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 01:57:17,334 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 01:57:18,000 INFO ]: Using library mode [2018-06-22 01:57:18,002 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 01:57:18 BoogieIcfgContainer [2018-06-22 01:57:18,002 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 01:57:18,003 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 01:57:18,003 INFO ]: Initializing TraceAbstraction... [2018-06-22 01:57:18,010 INFO ]: TraceAbstraction initialized [2018-06-22 01:57:18,010 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 01:57:17" (1/3) ... [2018-06-22 01:57:18,011 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6209a3ce and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 01:57:18, skipping insertion in model container [2018-06-22 01:57:18,011 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:57:17" (2/3) ... [2018-06-22 01:57:18,011 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6209a3ce and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 01:57:18, skipping insertion in model container [2018-06-22 01:57:18,012 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 01:57:18" (3/3) ... [2018-06-22 01:57:18,013 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 01:57:18,023 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 01:57:18,033 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 01:57:18,088 INFO ]: Using default assertion order modulation [2018-06-22 01:57:18,089 INFO ]: Interprodecural is true [2018-06-22 01:57:18,089 INFO ]: Hoare is false [2018-06-22 01:57:18,089 INFO ]: Compute interpolants for FPandBP [2018-06-22 01:57:18,089 INFO ]: Backedges is TWOTRACK [2018-06-22 01:57:18,089 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 01:57:18,089 INFO ]: Difference is false [2018-06-22 01:57:18,089 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 01:57:18,089 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 01:57:18,109 INFO ]: Start isEmpty. Operand 47 states. [2018-06-22 01:57:18,123 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-22 01:57:18,123 INFO ]: Found error trace [2018-06-22 01:57:18,124 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:57:18,125 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:57:18,131 INFO ]: Analyzing trace with hash 1841999515, now seen corresponding path program 1 times [2018-06-22 01:57:18,133 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:57:18,134 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:57:18,179 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:57:18,179 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:57:18,179 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:57:18,231 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:57:18,358 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:57:18,360 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 01:57:18,360 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 01:57:18,363 INFO ]: Interpolant automaton has 4 states [2018-06-22 01:57:18,380 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 01:57:18,381 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 01:57:18,384 INFO ]: Start difference. First operand 47 states. Second operand 4 states. [2018-06-22 01:57:19,482 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:57:19,482 INFO ]: Finished difference Result 87 states and 139 transitions. [2018-06-22 01:57:19,485 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-22 01:57:19,486 INFO ]: Start accepts. Automaton has 4 states. Word has length 7 [2018-06-22 01:57:19,486 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:57:19,512 INFO ]: With dead ends: 87 [2018-06-22 01:57:19,512 INFO ]: Without dead ends: 69 [2018-06-22 01:57:19,519 INFO ]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-22 01:57:19,540 INFO ]: Start minimizeSevpa. Operand 69 states. [2018-06-22 01:57:19,592 INFO ]: Finished minimizeSevpa. Reduced states from 69 to 69. [2018-06-22 01:57:19,593 INFO ]: Start removeUnreachable. Operand 69 states. [2018-06-22 01:57:19,598 INFO ]: Finished removeUnreachable. Reduced from 69 states to 69 states and 107 transitions. [2018-06-22 01:57:19,603 INFO ]: Start accepts. Automaton has 69 states and 107 transitions. Word has length 7 [2018-06-22 01:57:19,603 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:57:19,603 INFO ]: Abstraction has 69 states and 107 transitions. [2018-06-22 01:57:19,603 INFO ]: Interpolant automaton has 4 states. [2018-06-22 01:57:19,603 INFO ]: Start isEmpty. Operand 69 states and 107 transitions. [2018-06-22 01:57:19,607 INFO ]: Finished isEmpty. Found accepting run of length 13 [2018-06-22 01:57:19,607 INFO ]: Found error trace [2018-06-22 01:57:19,607 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:57:19,607 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:57:19,607 INFO ]: Analyzing trace with hash 1798997052, now seen corresponding path program 1 times [2018-06-22 01:57:19,607 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:57:19,607 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:57:19,608 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:57:19,608 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:57:19,608 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:57:19,621 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:57:19,671 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:57:19,671 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 01:57:19,671 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 01:57:19,673 INFO ]: Interpolant automaton has 4 states [2018-06-22 01:57:19,673 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 01:57:19,673 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 01:57:19,673 INFO ]: Start difference. First operand 69 states and 107 transitions. Second operand 4 states. [2018-06-22 01:57:20,211 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:57:20,211 INFO ]: Finished difference Result 97 states and 151 transitions. [2018-06-22 01:57:20,212 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-22 01:57:20,212 INFO ]: Start accepts. Automaton has 4 states. Word has length 12 [2018-06-22 01:57:20,212 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:57:20,220 INFO ]: With dead ends: 97 [2018-06-22 01:57:20,220 INFO ]: Without dead ends: 97 [2018-06-22 01:57:20,221 INFO ]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-22 01:57:20,221 INFO ]: Start minimizeSevpa. Operand 97 states. [2018-06-22 01:57:20,234 INFO ]: Finished minimizeSevpa. Reduced states from 97 to 97. [2018-06-22 01:57:20,234 INFO ]: Start removeUnreachable. Operand 97 states. [2018-06-22 01:57:20,238 INFO ]: Finished removeUnreachable. Reduced from 97 states to 97 states and 151 transitions. [2018-06-22 01:57:20,238 INFO ]: Start accepts. Automaton has 97 states and 151 transitions. Word has length 12 [2018-06-22 01:57:20,238 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:57:20,238 INFO ]: Abstraction has 97 states and 151 transitions. [2018-06-22 01:57:20,238 INFO ]: Interpolant automaton has 4 states. [2018-06-22 01:57:20,238 INFO ]: Start isEmpty. Operand 97 states and 151 transitions. [2018-06-22 01:57:20,243 INFO ]: Finished isEmpty. Found accepting run of length 22 [2018-06-22 01:57:20,243 INFO ]: Found error trace [2018-06-22 01:57:20,243 INFO ]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:57:20,243 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:57:20,244 INFO ]: Analyzing trace with hash 2147095267, now seen corresponding path program 1 times [2018-06-22 01:57:20,244 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:57:20,244 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:57:20,245 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:57:20,245 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:57:20,245 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:57:20,253 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:57:20,295 INFO ]: Checked inductivity of 5 backedges. 3 proven. 1 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 01:57:20,295 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:57:20,296 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 01:57:20,310 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:57:20,346 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:57:20,353 INFO ]: Computing forward predicates... [2018-06-22 01:57:20,373 INFO ]: Checked inductivity of 5 backedges. 3 proven. 1 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 01:57:20,396 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:57:20,397 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 4 [2018-06-22 01:57:20,397 INFO ]: Interpolant automaton has 4 states [2018-06-22 01:57:20,397 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 01:57:20,397 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 01:57:20,397 INFO ]: Start difference. First operand 97 states and 151 transitions. Second operand 4 states. [2018-06-22 01:57:20,831 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:57:20,831 INFO ]: Finished difference Result 116 states and 181 transitions. [2018-06-22 01:57:20,831 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-22 01:57:20,832 INFO ]: Start accepts. Automaton has 4 states. Word has length 21 [2018-06-22 01:57:20,832 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:57:20,834 INFO ]: With dead ends: 116 [2018-06-22 01:57:20,835 INFO ]: Without dead ends: 97 [2018-06-22 01:57:20,835 INFO ]: 0 DeclaredPredicates, 26 GetRequests, 23 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-22 01:57:20,835 INFO ]: Start minimizeSevpa. Operand 97 states. [2018-06-22 01:57:20,847 INFO ]: Finished minimizeSevpa. Reduced states from 97 to 97. [2018-06-22 01:57:20,847 INFO ]: Start removeUnreachable. Operand 97 states. [2018-06-22 01:57:20,851 INFO ]: Finished removeUnreachable. Reduced from 97 states to 97 states and 150 transitions. [2018-06-22 01:57:20,851 INFO ]: Start accepts. Automaton has 97 states and 150 transitions. Word has length 21 [2018-06-22 01:57:20,851 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:57:20,851 INFO ]: Abstraction has 97 states and 150 transitions. [2018-06-22 01:57:20,851 INFO ]: Interpolant automaton has 4 states. [2018-06-22 01:57:20,851 INFO ]: Start isEmpty. Operand 97 states and 150 transitions. [2018-06-22 01:57:20,855 INFO ]: Finished isEmpty. Found accepting run of length 24 [2018-06-22 01:57:20,855 INFO ]: Found error trace [2018-06-22 01:57:20,855 INFO ]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:57:20,855 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:57:20,855 INFO ]: Analyzing trace with hash -1779255278, now seen corresponding path program 1 times [2018-06-22 01:57:20,855 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:57:20,855 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:57:20,856 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:57:20,856 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:57:20,856 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:57:20,896 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:57:20,982 INFO ]: Checked inductivity of 5 backedges. 3 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-06-22 01:57:20,982 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 01:57:20,982 INFO ]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-06-22 01:57:20,982 INFO ]: Interpolant automaton has 5 states [2018-06-22 01:57:20,983 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-22 01:57:20,983 INFO ]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-06-22 01:57:20,983 INFO ]: Start difference. First operand 97 states and 150 transitions. Second operand 5 states. [2018-06-22 01:57:21,448 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:57:21,449 INFO ]: Finished difference Result 189 states and 361 transitions. [2018-06-22 01:57:21,451 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 01:57:21,451 INFO ]: Start accepts. Automaton has 5 states. Word has length 23 [2018-06-22 01:57:21,452 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:57:21,475 INFO ]: With dead ends: 189 [2018-06-22 01:57:21,475 INFO ]: Without dead ends: 189 [2018-06-22 01:57:21,475 INFO ]: 0 DeclaredPredicates, 9 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=22, Invalid=34, Unknown=0, NotChecked=0, Total=56 [2018-06-22 01:57:21,475 INFO ]: Start minimizeSevpa. Operand 189 states. [2018-06-22 01:57:21,523 INFO ]: Finished minimizeSevpa. Reduced states from 189 to 102. [2018-06-22 01:57:21,523 INFO ]: Start removeUnreachable. Operand 102 states. [2018-06-22 01:57:21,528 INFO ]: Finished removeUnreachable. Reduced from 102 states to 102 states and 160 transitions. [2018-06-22 01:57:21,528 INFO ]: Start accepts. Automaton has 102 states and 160 transitions. Word has length 23 [2018-06-22 01:57:21,528 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:57:21,528 INFO ]: Abstraction has 102 states and 160 transitions. [2018-06-22 01:57:21,528 INFO ]: Interpolant automaton has 5 states. [2018-06-22 01:57:21,528 INFO ]: Start isEmpty. Operand 102 states and 160 transitions. [2018-06-22 01:57:21,531 INFO ]: Finished isEmpty. Found accepting run of length 25 [2018-06-22 01:57:21,531 INFO ]: Found error trace [2018-06-22 01:57:21,532 INFO ]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:57:21,532 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:57:21,532 INFO ]: Analyzing trace with hash 678461987, now seen corresponding path program 1 times [2018-06-22 01:57:21,532 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:57:21,532 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:57:21,533 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:57:21,533 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:57:21,533 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:57:21,565 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:57:21,880 INFO ]: Checked inductivity of 7 backedges. 5 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-06-22 01:57:21,880 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 01:57:21,880 INFO ]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2018-06-22 01:57:21,881 INFO ]: Interpolant automaton has 6 states [2018-06-22 01:57:21,881 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-22 01:57:21,881 INFO ]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2018-06-22 01:57:21,881 INFO ]: Start difference. First operand 102 states and 160 transitions. Second operand 6 states. [2018-06-22 01:57:22,437 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:57:22,437 INFO ]: Finished difference Result 207 states and 322 transitions. [2018-06-22 01:57:22,439 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-22 01:57:22,439 INFO ]: Start accepts. Automaton has 6 states. Word has length 24 [2018-06-22 01:57:22,439 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:57:22,446 INFO ]: With dead ends: 207 [2018-06-22 01:57:22,446 INFO ]: Without dead ends: 207 [2018-06-22 01:57:22,446 INFO ]: 0 DeclaredPredicates, 10 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2018-06-22 01:57:22,446 INFO ]: Start minimizeSevpa. Operand 207 states. [2018-06-22 01:57:22,462 INFO ]: Finished minimizeSevpa. Reduced states from 207 to 117. [2018-06-22 01:57:22,463 INFO ]: Start removeUnreachable. Operand 117 states. [2018-06-22 01:57:22,465 INFO ]: Finished removeUnreachable. Reduced from 117 states to 117 states and 181 transitions. [2018-06-22 01:57:22,465 INFO ]: Start accepts. Automaton has 117 states and 181 transitions. Word has length 24 [2018-06-22 01:57:22,465 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:57:22,465 INFO ]: Abstraction has 117 states and 181 transitions. [2018-06-22 01:57:22,465 INFO ]: Interpolant automaton has 6 states. [2018-06-22 01:57:22,465 INFO ]: Start isEmpty. Operand 117 states and 181 transitions. [2018-06-22 01:57:22,471 INFO ]: Finished isEmpty. Found accepting run of length 54 [2018-06-22 01:57:22,471 INFO ]: Found error trace [2018-06-22 01:57:22,471 INFO ]: trace histogram [5, 5, 5, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:57:22,471 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:57:22,471 INFO ]: Analyzing trace with hash 1068088598, now seen corresponding path program 1 times [2018-06-22 01:57:22,471 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:57:22,472 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:57:22,472 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:57:22,472 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:57:22,472 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:57:22,495 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:57:22,629 INFO ]: Checked inductivity of 71 backedges. 31 proven. 3 refuted. 0 times theorem prover too weak. 37 trivial. 0 not checked. [2018-06-22 01:57:22,630 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:57:22,630 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 01:57:22,647 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:57:22,704 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:57:22,709 INFO ]: Computing forward predicates... [2018-06-22 01:57:22,802 INFO ]: Checked inductivity of 71 backedges. 45 proven. 0 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2018-06-22 01:57:22,836 INFO ]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-06-22 01:57:22,836 INFO ]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 10 [2018-06-22 01:57:22,837 INFO ]: Interpolant automaton has 10 states [2018-06-22 01:57:22,837 INFO ]: Constructing interpolant automaton starting with 10 interpolants. [2018-06-22 01:57:22,837 INFO ]: CoverageRelationStatistics Valid=21, Invalid=69, Unknown=0, NotChecked=0, Total=90 [2018-06-22 01:57:22,837 INFO ]: Start difference. First operand 117 states and 181 transitions. Second operand 10 states. [2018-06-22 01:57:23,973 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:57:23,973 INFO ]: Finished difference Result 284 states and 568 transitions. [2018-06-22 01:57:23,974 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-06-22 01:57:23,974 INFO ]: Start accepts. Automaton has 10 states. Word has length 53 [2018-06-22 01:57:23,974 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:57:23,985 INFO ]: With dead ends: 284 [2018-06-22 01:57:23,985 INFO ]: Without dead ends: 264 [2018-06-22 01:57:23,986 INFO ]: 0 DeclaredPredicates, 70 GetRequests, 54 SyntacticMatches, 0 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 28 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=89, Invalid=217, Unknown=0, NotChecked=0, Total=306 [2018-06-22 01:57:23,986 INFO ]: Start minimizeSevpa. Operand 264 states. [2018-06-22 01:57:24,013 INFO ]: Finished minimizeSevpa. Reduced states from 264 to 165. [2018-06-22 01:57:24,014 INFO ]: Start removeUnreachable. Operand 165 states. [2018-06-22 01:57:24,016 INFO ]: Finished removeUnreachable. Reduced from 165 states to 165 states and 275 transitions. [2018-06-22 01:57:24,017 INFO ]: Start accepts. Automaton has 165 states and 275 transitions. Word has length 53 [2018-06-22 01:57:24,017 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:57:24,017 INFO ]: Abstraction has 165 states and 275 transitions. [2018-06-22 01:57:24,017 INFO ]: Interpolant automaton has 10 states. [2018-06-22 01:57:24,017 INFO ]: Start isEmpty. Operand 165 states and 275 transitions. [2018-06-22 01:57:24,024 INFO ]: Finished isEmpty. Found accepting run of length 55 [2018-06-22 01:57:24,024 INFO ]: Found error trace [2018-06-22 01:57:24,024 INFO ]: trace histogram [5, 5, 5, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:57:24,024 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:57:24,024 INFO ]: Analyzing trace with hash 250579813, now seen corresponding path program 2 times [2018-06-22 01:57:24,024 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:57:24,024 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:57:24,025 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:57:24,025 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:57:24,025 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:57:24,047 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:57:24,132 INFO ]: Checked inductivity of 78 backedges. 25 proven. 0 refuted. 0 times theorem prover too weak. 53 trivial. 0 not checked. [2018-06-22 01:57:24,132 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 01:57:24,132 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-22 01:57:24,134 INFO ]: Interpolant automaton has 3 states [2018-06-22 01:57:24,135 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-22 01:57:24,135 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-22 01:57:24,135 INFO ]: Start difference. First operand 165 states and 275 transitions. Second operand 3 states. [2018-06-22 01:57:24,228 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:57:24,228 INFO ]: Finished difference Result 169 states and 275 transitions. [2018-06-22 01:57:24,230 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-22 01:57:24,230 INFO ]: Start accepts. Automaton has 3 states. Word has length 54 [2018-06-22 01:57:24,230 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:57:24,234 INFO ]: With dead ends: 169 [2018-06-22 01:57:24,234 INFO ]: Without dead ends: 165 [2018-06-22 01:57:24,235 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 01:57:24,237 INFO ]: Start minimizeSevpa. Operand 165 states. [2018-06-22 01:57:24,265 INFO ]: Finished minimizeSevpa. Reduced states from 165 to 165. [2018-06-22 01:57:24,265 INFO ]: Start removeUnreachable. Operand 165 states. [2018-06-22 01:57:24,267 INFO ]: Finished removeUnreachable. Reduced from 165 states to 165 states and 271 transitions. [2018-06-22 01:57:24,267 INFO ]: Start accepts. Automaton has 165 states and 271 transitions. Word has length 54 [2018-06-22 01:57:24,267 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:57:24,267 INFO ]: Abstraction has 165 states and 271 transitions. [2018-06-22 01:57:24,267 INFO ]: Interpolant automaton has 3 states. [2018-06-22 01:57:24,267 INFO ]: Start isEmpty. Operand 165 states and 271 transitions. [2018-06-22 01:57:24,273 INFO ]: Finished isEmpty. Found accepting run of length 55 [2018-06-22 01:57:24,274 INFO ]: Found error trace [2018-06-22 01:57:24,274 INFO ]: trace histogram [5, 5, 5, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:57:24,274 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:57:24,274 INFO ]: Analyzing trace with hash -1029283865, now seen corresponding path program 1 times [2018-06-22 01:57:24,274 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:57:24,274 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:57:24,275 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:57:24,275 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:57:24,275 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:57:24,299 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:57:24,456 INFO ]: Checked inductivity of 78 backedges. 23 proven. 8 refuted. 0 times theorem prover too weak. 47 trivial. 0 not checked. [2018-06-22 01:57:24,456 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:57:24,456 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 01:57:24,472 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:57:24,534 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:57:24,538 INFO ]: Computing forward predicates... [2018-06-22 01:57:24,555 INFO ]: Checked inductivity of 78 backedges. 23 proven. 8 refuted. 0 times theorem prover too weak. 47 trivial. 0 not checked. [2018-06-22 01:57:24,588 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:57:24,588 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 9 [2018-06-22 01:57:24,589 INFO ]: Interpolant automaton has 9 states [2018-06-22 01:57:24,589 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-22 01:57:24,589 INFO ]: CoverageRelationStatistics Valid=15, Invalid=57, Unknown=0, NotChecked=0, Total=72 [2018-06-22 01:57:24,589 INFO ]: Start difference. First operand 165 states and 271 transitions. Second operand 9 states. [2018-06-22 01:57:25,475 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:57:25,475 INFO ]: Finished difference Result 383 states and 898 transitions. [2018-06-22 01:57:25,476 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-06-22 01:57:25,476 INFO ]: Start accepts. Automaton has 9 states. Word has length 54 [2018-06-22 01:57:25,476 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:57:25,488 INFO ]: With dead ends: 383 [2018-06-22 01:57:25,488 INFO ]: Without dead ends: 383 [2018-06-22 01:57:25,489 INFO ]: 0 DeclaredPredicates, 75 GetRequests, 58 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 31 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=101, Invalid=241, Unknown=0, NotChecked=0, Total=342 [2018-06-22 01:57:25,489 INFO ]: Start minimizeSevpa. Operand 383 states. [2018-06-22 01:57:25,520 INFO ]: Finished minimizeSevpa. Reduced states from 383 to 197. [2018-06-22 01:57:25,520 INFO ]: Start removeUnreachable. Operand 197 states. [2018-06-22 01:57:25,523 INFO ]: Finished removeUnreachable. Reduced from 197 states to 197 states and 315 transitions. [2018-06-22 01:57:25,523 INFO ]: Start accepts. Automaton has 197 states and 315 transitions. Word has length 54 [2018-06-22 01:57:25,524 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:57:25,524 INFO ]: Abstraction has 197 states and 315 transitions. [2018-06-22 01:57:25,524 INFO ]: Interpolant automaton has 9 states. [2018-06-22 01:57:25,524 INFO ]: Start isEmpty. Operand 197 states and 315 transitions. [2018-06-22 01:57:25,531 INFO ]: Finished isEmpty. Found accepting run of length 65 [2018-06-22 01:57:25,531 INFO ]: Found error trace [2018-06-22 01:57:25,531 INFO ]: trace histogram [6, 6, 6, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:57:25,532 INFO ]: === Iteration 9 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:57:25,532 INFO ]: Analyzing trace with hash 1908843488, now seen corresponding path program 1 times [2018-06-22 01:57:25,532 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:57:25,532 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:57:25,532 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:57:25,532 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:57:25,532 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:57:25,546 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:57:25,602 INFO ]: Checked inductivity of 102 backedges. 33 proven. 7 refuted. 0 times theorem prover too weak. 62 trivial. 0 not checked. [2018-06-22 01:57:25,602 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:57:25,602 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 01:57:25,607 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:57:25,665 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:57:25,670 INFO ]: Computing forward predicates... [2018-06-22 01:57:25,823 INFO ]: Checked inductivity of 102 backedges. 61 proven. 0 refuted. 0 times theorem prover too weak. 41 trivial. 0 not checked. [2018-06-22 01:57:25,843 INFO ]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-06-22 01:57:25,844 INFO ]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 10 [2018-06-22 01:57:25,844 INFO ]: Interpolant automaton has 10 states [2018-06-22 01:57:25,844 INFO ]: Constructing interpolant automaton starting with 10 interpolants. [2018-06-22 01:57:25,844 INFO ]: CoverageRelationStatistics Valid=17, Invalid=73, Unknown=0, NotChecked=0, Total=90 [2018-06-22 01:57:25,844 INFO ]: Start difference. First operand 197 states and 315 transitions. Second operand 10 states. [2018-06-22 01:57:29,409 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:57:29,409 INFO ]: Finished difference Result 603 states and 1467 transitions. [2018-06-22 01:57:29,410 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 57 states. [2018-06-22 01:57:29,410 INFO ]: Start accepts. Automaton has 10 states. Word has length 64 [2018-06-22 01:57:29,410 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:57:29,427 INFO ]: With dead ends: 603 [2018-06-22 01:57:29,427 INFO ]: Without dead ends: 505 [2018-06-22 01:57:29,429 INFO ]: 0 DeclaredPredicates, 136 GetRequests, 78 SyntacticMatches, 0 SemanticMatches, 58 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1149 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=565, Invalid=2975, Unknown=0, NotChecked=0, Total=3540 [2018-06-22 01:57:29,429 INFO ]: Start minimizeSevpa. Operand 505 states. [2018-06-22 01:57:29,476 INFO ]: Finished minimizeSevpa. Reduced states from 505 to 258. [2018-06-22 01:57:29,476 INFO ]: Start removeUnreachable. Operand 258 states. [2018-06-22 01:57:29,482 INFO ]: Finished removeUnreachable. Reduced from 258 states to 258 states and 446 transitions. [2018-06-22 01:57:29,482 INFO ]: Start accepts. Automaton has 258 states and 446 transitions. Word has length 64 [2018-06-22 01:57:29,484 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:57:29,484 INFO ]: Abstraction has 258 states and 446 transitions. [2018-06-22 01:57:29,484 INFO ]: Interpolant automaton has 10 states. [2018-06-22 01:57:29,484 INFO ]: Start isEmpty. Operand 258 states and 446 transitions. [2018-06-22 01:57:29,494 INFO ]: Finished isEmpty. Found accepting run of length 67 [2018-06-22 01:57:29,494 INFO ]: Found error trace [2018-06-22 01:57:29,497 INFO ]: trace histogram [6, 6, 6, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:57:29,497 INFO ]: === Iteration 10 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:57:29,497 INFO ]: Analyzing trace with hash 934315030, now seen corresponding path program 2 times [2018-06-22 01:57:29,497 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:57:29,498 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:57:29,498 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:57:29,498 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:57:29,498 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:57:29,518 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:57:29,593 INFO ]: Checked inductivity of 117 backedges. 55 proven. 4 refuted. 0 times theorem prover too weak. 58 trivial. 0 not checked. [2018-06-22 01:57:29,593 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:57:29,593 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 01:57:29,599 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 01:57:29,649 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 01:57:29,649 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:57:29,653 INFO ]: Computing forward predicates... [2018-06-22 01:57:29,661 INFO ]: Checked inductivity of 117 backedges. 75 proven. 0 refuted. 0 times theorem prover too weak. 42 trivial. 0 not checked. [2018-06-22 01:57:29,687 INFO ]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-06-22 01:57:29,687 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [4] total 4 [2018-06-22 01:57:29,687 INFO ]: Interpolant automaton has 4 states [2018-06-22 01:57:29,687 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 01:57:29,687 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 01:57:29,687 INFO ]: Start difference. First operand 258 states and 446 transitions. Second operand 4 states. [2018-06-22 01:57:29,782 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:57:29,783 INFO ]: Finished difference Result 394 states and 656 transitions. [2018-06-22 01:57:29,783 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-22 01:57:29,783 INFO ]: Start accepts. Automaton has 4 states. Word has length 66 [2018-06-22 01:57:29,783 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:57:29,788 INFO ]: With dead ends: 394 [2018-06-22 01:57:29,788 INFO ]: Without dead ends: 248 [2018-06-22 01:57:29,788 INFO ]: 0 DeclaredPredicates, 71 GetRequests, 68 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-22 01:57:29,788 INFO ]: Start minimizeSevpa. Operand 248 states. [2018-06-22 01:57:29,802 INFO ]: Finished minimizeSevpa. Reduced states from 248 to 248. [2018-06-22 01:57:29,802 INFO ]: Start removeUnreachable. Operand 248 states. [2018-06-22 01:57:29,807 INFO ]: Finished removeUnreachable. Reduced from 248 states to 248 states and 402 transitions. [2018-06-22 01:57:29,807 INFO ]: Start accepts. Automaton has 248 states and 402 transitions. Word has length 66 [2018-06-22 01:57:29,807 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:57:29,807 INFO ]: Abstraction has 248 states and 402 transitions. [2018-06-22 01:57:29,807 INFO ]: Interpolant automaton has 4 states. [2018-06-22 01:57:29,808 INFO ]: Start isEmpty. Operand 248 states and 402 transitions. [2018-06-22 01:57:29,816 INFO ]: Finished isEmpty. Found accepting run of length 74 [2018-06-22 01:57:29,816 INFO ]: Found error trace [2018-06-22 01:57:29,816 INFO ]: trace histogram [7, 7, 7, 4, 4, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:57:29,816 INFO ]: === Iteration 11 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:57:29,816 INFO ]: Analyzing trace with hash 1713545221, now seen corresponding path program 1 times [2018-06-22 01:57:29,816 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:57:29,816 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:57:29,817 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:57:29,817 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:57:29,817 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:57:29,836 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:57:29,886 INFO ]: Checked inductivity of 160 backedges. 70 proven. 6 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2018-06-22 01:57:29,886 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:57:29,886 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 01:57:29,897 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:57:29,950 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:57:29,954 INFO ]: Computing forward predicates... [2018-06-22 01:57:29,985 INFO ]: Checked inductivity of 160 backedges. 96 proven. 1 refuted. 0 times theorem prover too weak. 63 trivial. 0 not checked. [2018-06-22 01:57:30,024 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:57:30,025 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 4 [2018-06-22 01:57:30,025 INFO ]: Interpolant automaton has 4 states [2018-06-22 01:57:30,025 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 01:57:30,025 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 01:57:30,025 INFO ]: Start difference. First operand 248 states and 402 transitions. Second operand 4 states. [2018-06-22 01:57:30,175 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:57:30,175 INFO ]: Finished difference Result 304 states and 494 transitions. [2018-06-22 01:57:30,175 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-22 01:57:30,175 INFO ]: Start accepts. Automaton has 4 states. Word has length 73 [2018-06-22 01:57:30,176 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:57:30,179 INFO ]: With dead ends: 304 [2018-06-22 01:57:30,179 INFO ]: Without dead ends: 248 [2018-06-22 01:57:30,179 INFO ]: 0 DeclaredPredicates, 78 GetRequests, 75 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-22 01:57:30,180 INFO ]: Start minimizeSevpa. Operand 248 states. [2018-06-22 01:57:30,194 INFO ]: Finished minimizeSevpa. Reduced states from 248 to 248. [2018-06-22 01:57:30,194 INFO ]: Start removeUnreachable. Operand 248 states. [2018-06-22 01:57:30,197 INFO ]: Finished removeUnreachable. Reduced from 248 states to 248 states and 400 transitions. [2018-06-22 01:57:30,198 INFO ]: Start accepts. Automaton has 248 states and 400 transitions. Word has length 73 [2018-06-22 01:57:30,198 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:57:30,198 INFO ]: Abstraction has 248 states and 400 transitions. [2018-06-22 01:57:30,198 INFO ]: Interpolant automaton has 4 states. [2018-06-22 01:57:30,198 INFO ]: Start isEmpty. Operand 248 states and 400 transitions. [2018-06-22 01:57:30,207 INFO ]: Finished isEmpty. Found accepting run of length 102 [2018-06-22 01:57:30,207 INFO ]: Found error trace [2018-06-22 01:57:30,207 INFO ]: trace histogram [10, 10, 10, 5, 5, 5, 4, 4, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:57:30,207 INFO ]: === Iteration 12 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:57:30,207 INFO ]: Analyzing trace with hash -1203076981, now seen corresponding path program 1 times [2018-06-22 01:57:30,207 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:57:30,207 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:57:30,209 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:57:30,209 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:57:30,209 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:57:30,233 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:57:30,374 INFO ]: Checked inductivity of 317 backedges. 100 proven. 6 refuted. 0 times theorem prover too weak. 211 trivial. 0 not checked. [2018-06-22 01:57:30,374 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:57:30,374 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 01:57:30,385 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:57:30,448 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:57:30,453 INFO ]: Computing forward predicates... [2018-06-22 01:57:30,508 INFO ]: Checked inductivity of 317 backedges. 138 proven. 0 refuted. 0 times theorem prover too weak. 179 trivial. 0 not checked. [2018-06-22 01:57:30,529 INFO ]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-06-22 01:57:30,529 INFO ]: Number of different interpolants: perfect sequences [6] imperfect sequences [8] total 12 [2018-06-22 01:57:30,529 INFO ]: Interpolant automaton has 12 states [2018-06-22 01:57:30,529 INFO ]: Constructing interpolant automaton starting with 12 interpolants. [2018-06-22 01:57:30,529 INFO ]: CoverageRelationStatistics Valid=25, Invalid=107, Unknown=0, NotChecked=0, Total=132 [2018-06-22 01:57:30,530 INFO ]: Start difference. First operand 248 states and 400 transitions. Second operand 12 states. [2018-06-22 01:57:31,866 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:57:31,866 INFO ]: Finished difference Result 381 states and 769 transitions. [2018-06-22 01:57:31,866 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2018-06-22 01:57:31,866 INFO ]: Start accepts. Automaton has 12 states. Word has length 101 [2018-06-22 01:57:31,867 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:57:31,873 INFO ]: With dead ends: 381 [2018-06-22 01:57:31,873 INFO ]: Without dead ends: 379 [2018-06-22 01:57:31,873 INFO ]: 0 DeclaredPredicates, 128 GetRequests, 104 SyntacticMatches, 0 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 86 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=115, Invalid=535, Unknown=0, NotChecked=0, Total=650 [2018-06-22 01:57:31,873 INFO ]: Start minimizeSevpa. Operand 379 states. [2018-06-22 01:57:31,892 INFO ]: Finished minimizeSevpa. Reduced states from 379 to 236. [2018-06-22 01:57:31,893 INFO ]: Start removeUnreachable. Operand 236 states. [2018-06-22 01:57:31,895 INFO ]: Finished removeUnreachable. Reduced from 236 states to 236 states and 374 transitions. [2018-06-22 01:57:31,895 INFO ]: Start accepts. Automaton has 236 states and 374 transitions. Word has length 101 [2018-06-22 01:57:31,895 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:57:31,895 INFO ]: Abstraction has 236 states and 374 transitions. [2018-06-22 01:57:31,895 INFO ]: Interpolant automaton has 12 states. [2018-06-22 01:57:31,896 INFO ]: Start isEmpty. Operand 236 states and 374 transitions. [2018-06-22 01:57:31,902 INFO ]: Finished isEmpty. Found accepting run of length 103 [2018-06-22 01:57:31,902 INFO ]: Found error trace [2018-06-22 01:57:31,902 INFO ]: trace histogram [10, 10, 10, 5, 5, 5, 5, 4, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:57:31,902 INFO ]: === Iteration 13 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:57:31,903 INFO ]: Analyzing trace with hash -1488649266, now seen corresponding path program 2 times [2018-06-22 01:57:31,903 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:57:31,903 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:57:31,903 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:57:31,903 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:57:31,903 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:57:31,922 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:57:32,042 INFO ]: Checked inductivity of 331 backedges. 84 proven. 3 refuted. 0 times theorem prover too weak. 244 trivial. 0 not checked. [2018-06-22 01:57:32,043 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:57:32,043 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 01:57:32,056 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 01:57:32,135 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 01:57:32,135 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:57:32,140 INFO ]: Computing forward predicates... [2018-06-22 01:57:32,258 INFO ]: Checked inductivity of 331 backedges. 126 proven. 0 refuted. 0 times theorem prover too weak. 205 trivial. 0 not checked. [2018-06-22 01:57:32,279 INFO ]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-06-22 01:57:32,280 INFO ]: Number of different interpolants: perfect sequences [8] imperfect sequences [7] total 13 [2018-06-22 01:57:32,280 INFO ]: Interpolant automaton has 13 states [2018-06-22 01:57:32,280 INFO ]: Constructing interpolant automaton starting with 13 interpolants. [2018-06-22 01:57:32,280 INFO ]: CoverageRelationStatistics Valid=28, Invalid=128, Unknown=0, NotChecked=0, Total=156 [2018-06-22 01:57:32,280 INFO ]: Start difference. First operand 236 states and 374 transitions. Second operand 13 states. [2018-06-22 01:57:35,884 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:57:35,884 INFO ]: Finished difference Result 711 states and 2202 transitions. [2018-06-22 01:57:35,884 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 43 states. [2018-06-22 01:57:35,884 INFO ]: Start accepts. Automaton has 13 states. Word has length 102 [2018-06-22 01:57:35,884 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:57:35,910 INFO ]: With dead ends: 711 [2018-06-22 01:57:35,910 INFO ]: Without dead ends: 709 [2018-06-22 01:57:35,911 INFO ]: 0 DeclaredPredicates, 157 GetRequests, 111 SyntacticMatches, 0 SemanticMatches, 46 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 542 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=406, Invalid=1850, Unknown=0, NotChecked=0, Total=2256 [2018-06-22 01:57:35,912 INFO ]: Start minimizeSevpa. Operand 709 states. [2018-06-22 01:57:36,013 INFO ]: Finished minimizeSevpa. Reduced states from 709 to 242. [2018-06-22 01:57:36,013 INFO ]: Start removeUnreachable. Operand 242 states. [2018-06-22 01:57:36,016 INFO ]: Finished removeUnreachable. Reduced from 242 states to 242 states and 398 transitions. [2018-06-22 01:57:36,016 INFO ]: Start accepts. Automaton has 242 states and 398 transitions. Word has length 102 [2018-06-22 01:57:36,016 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:57:36,016 INFO ]: Abstraction has 242 states and 398 transitions. [2018-06-22 01:57:36,016 INFO ]: Interpolant automaton has 13 states. [2018-06-22 01:57:36,016 INFO ]: Start isEmpty. Operand 242 states and 398 transitions. [2018-06-22 01:57:36,021 INFO ]: Finished isEmpty. Found accepting run of length 104 [2018-06-22 01:57:36,021 INFO ]: Found error trace [2018-06-22 01:57:36,021 INFO ]: trace histogram [10, 10, 10, 6, 5, 5, 5, 4, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:57:36,022 INFO ]: === Iteration 14 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:57:36,022 INFO ]: Analyzing trace with hash -526219921, now seen corresponding path program 3 times [2018-06-22 01:57:36,022 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:57:36,022 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:57:36,022 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:57:36,022 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:57:36,022 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:57:36,046 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:57:36,811 INFO ]: Checked inductivity of 346 backedges. 101 proven. 38 refuted. 0 times theorem prover too weak. 207 trivial. 0 not checked. [2018-06-22 01:57:36,811 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:57:36,811 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:57:36,817 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 01:57:36,885 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2018-06-22 01:57:36,885 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:57:36,889 INFO ]: Computing forward predicates... [2018-06-22 01:57:37,101 INFO ]: Checked inductivity of 346 backedges. 95 proven. 8 refuted. 0 times theorem prover too weak. 243 trivial. 0 not checked. [2018-06-22 01:57:37,121 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:57:37,121 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 10] total 18 [2018-06-22 01:57:37,121 INFO ]: Interpolant automaton has 18 states [2018-06-22 01:57:37,122 INFO ]: Constructing interpolant automaton starting with 18 interpolants. [2018-06-22 01:57:37,122 INFO ]: CoverageRelationStatistics Valid=36, Invalid=270, Unknown=0, NotChecked=0, Total=306 [2018-06-22 01:57:37,122 INFO ]: Start difference. First operand 242 states and 398 transitions. Second operand 18 states. [2018-06-22 01:57:39,633 WARN ]: Spent 120.00 ms on a formula simplification that was a NOOP. DAG size: 18 [2018-06-22 01:57:48,192 WARN ]: Spent 125.00 ms on a formula simplification that was a NOOP. DAG size: 16 [2018-06-22 01:57:49,449 WARN ]: Spent 121.00 ms on a formula simplification that was a NOOP. DAG size: 20 [2018-06-22 01:57:58,418 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:57:58,418 INFO ]: Finished difference Result 2319 states and 8124 transitions. [2018-06-22 01:57:58,418 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 212 states. [2018-06-22 01:57:58,418 INFO ]: Start accepts. Automaton has 18 states. Word has length 103 [2018-06-22 01:57:58,418 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:57:58,605 INFO ]: With dead ends: 2319 [2018-06-22 01:57:58,605 INFO ]: Without dead ends: 2319 [2018-06-22 01:57:58,614 INFO ]: 0 DeclaredPredicates, 421 GetRequests, 202 SyntacticMatches, 0 SemanticMatches, 219 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 19803 ImplicationChecksByTransitivity, 5.8s TimeCoverageRelationStatistics Valid=3231, Invalid=45389, Unknown=0, NotChecked=0, Total=48620 [2018-06-22 01:57:58,615 INFO ]: Start minimizeSevpa. Operand 2319 states. [2018-06-22 01:57:59,074 INFO ]: Finished minimizeSevpa. Reduced states from 2319 to 332. [2018-06-22 01:57:59,074 INFO ]: Start removeUnreachable. Operand 332 states. [2018-06-22 01:57:59,079 INFO ]: Finished removeUnreachable. Reduced from 332 states to 332 states and 569 transitions. [2018-06-22 01:57:59,079 INFO ]: Start accepts. Automaton has 332 states and 569 transitions. Word has length 103 [2018-06-22 01:57:59,079 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:57:59,079 INFO ]: Abstraction has 332 states and 569 transitions. [2018-06-22 01:57:59,079 INFO ]: Interpolant automaton has 18 states. [2018-06-22 01:57:59,079 INFO ]: Start isEmpty. Operand 332 states and 569 transitions. [2018-06-22 01:57:59,091 INFO ]: Finished isEmpty. Found accepting run of length 143 [2018-06-22 01:57:59,091 INFO ]: Found error trace [2018-06-22 01:57:59,091 INFO ]: trace histogram [14, 14, 14, 8, 7, 7, 6, 5, 5, 5, 5, 5, 4, 4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:57:59,091 INFO ]: === Iteration 15 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:57:59,091 INFO ]: Analyzing trace with hash -1623751822, now seen corresponding path program 1 times [2018-06-22 01:57:59,091 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:57:59,091 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:57:59,092 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:57:59,092 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:57:59,092 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:57:59,106 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:57:59,285 INFO ]: Checked inductivity of 692 backedges. 111 proven. 78 refuted. 0 times theorem prover too weak. 503 trivial. 0 not checked. [2018-06-22 01:57:59,285 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:57:59,285 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:57:59,304 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:57:59,399 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:57:59,404 INFO ]: Computing forward predicates... [2018-06-22 01:57:59,422 INFO ]: Checked inductivity of 692 backedges. 344 proven. 1 refuted. 0 times theorem prover too weak. 347 trivial. 0 not checked. [2018-06-22 01:57:59,459 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:57:59,459 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 4 [2018-06-22 01:57:59,459 INFO ]: Interpolant automaton has 4 states [2018-06-22 01:57:59,459 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 01:57:59,459 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 01:57:59,460 INFO ]: Start difference. First operand 332 states and 569 transitions. Second operand 4 states. [2018-06-22 01:57:59,578 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:57:59,578 INFO ]: Finished difference Result 367 states and 630 transitions. [2018-06-22 01:57:59,578 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-22 01:57:59,578 INFO ]: Start accepts. Automaton has 4 states. Word has length 142 [2018-06-22 01:57:59,578 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:57:59,584 INFO ]: With dead ends: 367 [2018-06-22 01:57:59,584 INFO ]: Without dead ends: 332 [2018-06-22 01:57:59,584 INFO ]: 0 DeclaredPredicates, 147 GetRequests, 144 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-22 01:57:59,584 INFO ]: Start minimizeSevpa. Operand 332 states. [2018-06-22 01:57:59,602 INFO ]: Finished minimizeSevpa. Reduced states from 332 to 332. [2018-06-22 01:57:59,602 INFO ]: Start removeUnreachable. Operand 332 states. [2018-06-22 01:57:59,606 INFO ]: Finished removeUnreachable. Reduced from 332 states to 332 states and 567 transitions. [2018-06-22 01:57:59,606 INFO ]: Start accepts. Automaton has 332 states and 567 transitions. Word has length 142 [2018-06-22 01:57:59,606 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:57:59,606 INFO ]: Abstraction has 332 states and 567 transitions. [2018-06-22 01:57:59,606 INFO ]: Interpolant automaton has 4 states. [2018-06-22 01:57:59,606 INFO ]: Start isEmpty. Operand 332 states and 567 transitions. [2018-06-22 01:57:59,617 INFO ]: Finished isEmpty. Found accepting run of length 170 [2018-06-22 01:57:59,617 INFO ]: Found error trace [2018-06-22 01:57:59,617 INFO ]: trace histogram [17, 17, 17, 9, 9, 9, 8, 6, 5, 5, 5, 5, 4, 4, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:57:59,617 INFO ]: === Iteration 16 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:57:59,617 INFO ]: Analyzing trace with hash -1059448837, now seen corresponding path program 1 times [2018-06-22 01:57:59,617 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:57:59,617 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:57:59,618 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:57:59,618 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:57:59,618 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:57:59,631 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:57:59,795 INFO ]: Checked inductivity of 1033 backedges. 141 proven. 79 refuted. 0 times theorem prover too weak. 813 trivial. 0 not checked. [2018-06-22 01:57:59,795 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:57:59,795 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:57:59,809 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:57:59,990 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:57:59,998 INFO ]: Computing forward predicates... [2018-06-22 01:58:00,024 INFO ]: Checked inductivity of 1033 backedges. 580 proven. 7 refuted. 0 times theorem prover too weak. 446 trivial. 0 not checked. [2018-06-22 01:58:00,059 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:58:00,059 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 4 [2018-06-22 01:58:00,059 INFO ]: Interpolant automaton has 4 states [2018-06-22 01:58:00,060 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 01:58:00,060 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 01:58:00,060 INFO ]: Start difference. First operand 332 states and 567 transitions. Second operand 4 states. [2018-06-22 01:58:00,326 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:58:00,326 INFO ]: Finished difference Result 405 states and 674 transitions. [2018-06-22 01:58:00,326 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-22 01:58:00,326 INFO ]: Start accepts. Automaton has 4 states. Word has length 169 [2018-06-22 01:58:00,327 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:58:00,332 INFO ]: With dead ends: 405 [2018-06-22 01:58:00,332 INFO ]: Without dead ends: 323 [2018-06-22 01:58:00,333 INFO ]: 0 DeclaredPredicates, 174 GetRequests, 171 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-22 01:58:00,333 INFO ]: Start minimizeSevpa. Operand 323 states. [2018-06-22 01:58:00,348 INFO ]: Finished minimizeSevpa. Reduced states from 323 to 323. [2018-06-22 01:58:00,348 INFO ]: Start removeUnreachable. Operand 323 states. [2018-06-22 01:58:00,356 INFO ]: Finished removeUnreachable. Reduced from 323 states to 323 states and 531 transitions. [2018-06-22 01:58:00,357 INFO ]: Start accepts. Automaton has 323 states and 531 transitions. Word has length 169 [2018-06-22 01:58:00,357 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:58:00,357 INFO ]: Abstraction has 323 states and 531 transitions. [2018-06-22 01:58:00,357 INFO ]: Interpolant automaton has 4 states. [2018-06-22 01:58:00,357 INFO ]: Start isEmpty. Operand 323 states and 531 transitions. [2018-06-22 01:58:00,363 INFO ]: Finished isEmpty. Found accepting run of length 134 [2018-06-22 01:58:00,363 INFO ]: Found error trace [2018-06-22 01:58:00,363 INFO ]: trace histogram [13, 13, 13, 7, 7, 7, 6, 5, 4, 4, 4, 4, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:58:00,363 INFO ]: === Iteration 17 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:58:00,364 INFO ]: Analyzing trace with hash -1903770061, now seen corresponding path program 2 times [2018-06-22 01:58:00,364 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:58:00,364 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:58:00,364 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:58:00,364 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:58:00,364 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:58:00,392 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:58:00,623 INFO ]: Checked inductivity of 606 backedges. 159 proven. 65 refuted. 0 times theorem prover too weak. 382 trivial. 0 not checked. [2018-06-22 01:58:00,624 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:58:00,624 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:58:00,630 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 01:58:00,724 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 01:58:00,724 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:58:00,729 INFO ]: Computing forward predicates... [2018-06-22 01:58:00,939 INFO ]: Checked inductivity of 606 backedges. 210 proven. 56 refuted. 0 times theorem prover too weak. 340 trivial. 0 not checked. [2018-06-22 01:58:00,960 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:58:00,961 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 12] total 21 [2018-06-22 01:58:00,961 INFO ]: Interpolant automaton has 21 states [2018-06-22 01:58:00,961 INFO ]: Constructing interpolant automaton starting with 21 interpolants. [2018-06-22 01:58:00,961 INFO ]: CoverageRelationStatistics Valid=44, Invalid=376, Unknown=0, NotChecked=0, Total=420 [2018-06-22 01:58:00,961 INFO ]: Start difference. First operand 323 states and 531 transitions. Second operand 21 states. [2018-06-22 01:58:02,866 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:58:02,866 INFO ]: Finished difference Result 878 states and 2372 transitions. [2018-06-22 01:58:02,866 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2018-06-22 01:58:02,866 INFO ]: Start accepts. Automaton has 21 states. Word has length 133 [2018-06-22 01:58:02,866 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:58:02,897 INFO ]: With dead ends: 878 [2018-06-22 01:58:02,897 INFO ]: Without dead ends: 878 [2018-06-22 01:58:02,898 INFO ]: 0 DeclaredPredicates, 167 GetRequests, 132 SyntacticMatches, 3 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 159 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=144, Invalid=978, Unknown=0, NotChecked=0, Total=1122 [2018-06-22 01:58:02,898 INFO ]: Start minimizeSevpa. Operand 878 states. [2018-06-22 01:58:02,985 INFO ]: Finished minimizeSevpa. Reduced states from 878 to 403. [2018-06-22 01:58:02,985 INFO ]: Start removeUnreachable. Operand 403 states. [2018-06-22 01:58:02,990 INFO ]: Finished removeUnreachable. Reduced from 403 states to 403 states and 681 transitions. [2018-06-22 01:58:02,990 INFO ]: Start accepts. Automaton has 403 states and 681 transitions. Word has length 133 [2018-06-22 01:58:02,990 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:58:02,990 INFO ]: Abstraction has 403 states and 681 transitions. [2018-06-22 01:58:02,990 INFO ]: Interpolant automaton has 21 states. [2018-06-22 01:58:02,990 INFO ]: Start isEmpty. Operand 403 states and 681 transitions. [2018-06-22 01:58:03,004 INFO ]: Finished isEmpty. Found accepting run of length 212 [2018-06-22 01:58:03,004 INFO ]: Found error trace [2018-06-22 01:58:03,004 INFO ]: trace histogram [21, 21, 21, 11, 11, 11, 10, 8, 6, 6, 6, 6, 6, 6, 5, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:58:03,004 INFO ]: === Iteration 18 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:58:03,004 INFO ]: Analyzing trace with hash -439802830, now seen corresponding path program 3 times [2018-06-22 01:58:03,004 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:58:03,004 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:58:03,005 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:58:03,005 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:58:03,005 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:58:03,032 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:58:03,373 INFO ]: Checked inductivity of 1608 backedges. 273 proven. 60 refuted. 0 times theorem prover too weak. 1275 trivial. 0 not checked. [2018-06-22 01:58:03,373 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:58:03,373 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 15 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 15 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:58:03,378 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 01:58:03,566 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 9 check-sat command(s) [2018-06-22 01:58:03,566 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:58:03,572 INFO ]: Computing forward predicates... [2018-06-22 01:58:03,674 INFO ]: Checked inductivity of 1608 backedges. 868 proven. 12 refuted. 0 times theorem prover too weak. 728 trivial. 0 not checked. [2018-06-22 01:58:03,708 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:58:03,709 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 9] total 15 [2018-06-22 01:58:03,709 INFO ]: Interpolant automaton has 15 states [2018-06-22 01:58:03,710 INFO ]: Constructing interpolant automaton starting with 15 interpolants. [2018-06-22 01:58:03,710 INFO ]: CoverageRelationStatistics Valid=29, Invalid=181, Unknown=0, NotChecked=0, Total=210 [2018-06-22 01:58:03,710 INFO ]: Start difference. First operand 403 states and 681 transitions. Second operand 15 states. [2018-06-22 01:58:13,316 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:58:13,316 INFO ]: Finished difference Result 2127 states and 7918 transitions. [2018-06-22 01:58:13,317 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 91 states. [2018-06-22 01:58:13,317 INFO ]: Start accepts. Automaton has 15 states. Word has length 211 [2018-06-22 01:58:13,317 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:58:13,473 INFO ]: With dead ends: 2127 [2018-06-22 01:58:13,473 INFO ]: Without dead ends: 2043 [2018-06-22 01:58:13,475 INFO ]: 0 DeclaredPredicates, 333 GetRequests, 236 SyntacticMatches, 0 SemanticMatches, 97 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3183 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=1106, Invalid=8596, Unknown=0, NotChecked=0, Total=9702 [2018-06-22 01:58:13,476 INFO ]: Start minimizeSevpa. Operand 2043 states. [2018-06-22 01:58:13,841 INFO ]: Finished minimizeSevpa. Reduced states from 2043 to 661. [2018-06-22 01:58:13,841 INFO ]: Start removeUnreachable. Operand 661 states. [2018-06-22 01:58:13,853 INFO ]: Finished removeUnreachable. Reduced from 661 states to 661 states and 1225 transitions. [2018-06-22 01:58:13,853 INFO ]: Start accepts. Automaton has 661 states and 1225 transitions. Word has length 211 [2018-06-22 01:58:13,853 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:58:13,853 INFO ]: Abstraction has 661 states and 1225 transitions. [2018-06-22 01:58:13,853 INFO ]: Interpolant automaton has 15 states. [2018-06-22 01:58:13,854 INFO ]: Start isEmpty. Operand 661 states and 1225 transitions. [2018-06-22 01:58:13,872 INFO ]: Finished isEmpty. Found accepting run of length 213 [2018-06-22 01:58:13,872 INFO ]: Found error trace [2018-06-22 01:58:13,872 INFO ]: trace histogram [21, 21, 21, 12, 11, 11, 10, 8, 6, 6, 6, 6, 6, 6, 5, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:58:13,873 INFO ]: === Iteration 19 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:58:13,873 INFO ]: Analyzing trace with hash 963430959, now seen corresponding path program 4 times [2018-06-22 01:58:13,873 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:58:13,873 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:58:13,873 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:58:13,873 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:58:13,873 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:58:13,928 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:58:14,926 INFO ]: Checked inductivity of 1641 backedges. 305 proven. 164 refuted. 0 times theorem prover too weak. 1172 trivial. 0 not checked. [2018-06-22 01:58:14,926 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:58:14,926 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 16 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 16 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:58:14,933 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 01:58:15,074 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 01:58:15,074 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:58:15,082 INFO ]: Computing forward predicates... [2018-06-22 01:58:15,326 INFO ]: Checked inductivity of 1641 backedges. 281 proven. 85 refuted. 0 times theorem prover too weak. 1275 trivial. 0 not checked. [2018-06-22 01:58:15,351 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:58:15,351 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 11] total 21 [2018-06-22 01:58:15,351 INFO ]: Interpolant automaton has 21 states [2018-06-22 01:58:15,351 INFO ]: Constructing interpolant automaton starting with 21 interpolants. [2018-06-22 01:58:15,352 INFO ]: CoverageRelationStatistics Valid=42, Invalid=378, Unknown=0, NotChecked=0, Total=420 [2018-06-22 01:58:15,352 INFO ]: Start difference. First operand 661 states and 1225 transitions. Second operand 21 states. Received shutdown request... [2018-06-22 01:58:20,671 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2018-06-22 01:58:20,671 WARN ]: Verification canceled [2018-06-22 01:58:20,680 WARN ]: Timeout [2018-06-22 01:58:20,680 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 01:58:20 BoogieIcfgContainer [2018-06-22 01:58:20,680 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 01:58:20,681 INFO ]: Toolchain (without parser) took 63515.73 ms. Allocated memory was 300.4 MB in the beginning and 1.0 GB in the end (delta: 737.1 MB). Free memory was 248.8 MB in the beginning and 921.2 MB in the end (delta: -672.4 MB). Peak memory consumption was 64.7 MB. Max. memory is 3.6 GB. [2018-06-22 01:58:20,682 INFO ]: SmtParser took 0.10 ms. Allocated memory is still 300.4 MB. Free memory is still 264.9 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 01:58:20,682 INFO ]: ChcToBoogie took 79.15 ms. Allocated memory is still 300.4 MB. Free memory was 248.8 MB in the beginning and 246.8 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 01:58:20,682 INFO ]: Boogie Preprocessor took 51.68 ms. Allocated memory is still 300.4 MB. Free memory was 246.8 MB in the beginning and 244.8 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 01:58:20,683 INFO ]: RCFGBuilder took 692.66 ms. Allocated memory is still 300.4 MB. Free memory was 244.8 MB in the beginning and 222.8 MB in the end (delta: 22.0 MB). Peak memory consumption was 22.0 MB. Max. memory is 3.6 GB. [2018-06-22 01:58:20,683 INFO ]: TraceAbstraction took 62676.79 ms. Allocated memory was 300.4 MB in the beginning and 1.0 GB in the end (delta: 737.1 MB). Free memory was 222.8 MB in the beginning and 921.2 MB in the end (delta: -698.4 MB). Peak memory consumption was 38.7 MB. Max. memory is 3.6 GB. [2018-06-22 01:58:20,685 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.10 ms. Allocated memory is still 300.4 MB. Free memory is still 264.9 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 79.15 ms. Allocated memory is still 300.4 MB. Free memory was 248.8 MB in the beginning and 246.8 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 51.68 ms. Allocated memory is still 300.4 MB. Free memory was 246.8 MB in the beginning and 244.8 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 692.66 ms. Allocated memory is still 300.4 MB. Free memory was 244.8 MB in the beginning and 222.8 MB in the end (delta: 22.0 MB). Peak memory consumption was 22.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 62676.79 ms. Allocated memory was 300.4 MB in the beginning and 1.0 GB in the end (delta: 737.1 MB). Free memory was 222.8 MB in the beginning and 921.2 MB in the end (delta: -698.4 MB). Peak memory consumption was 38.7 MB. 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 constructing difference of abstraction (661states) and interpolant automaton (currently 30 states, 21 states before enhancement), while ReachableStatesComputation was computing reachable states (1256 states constructedinput type IntersectNwa). - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 47 locations, 1 error locations. TIMEOUT Result, 62.6s OverallTime, 19 OverallIterations, 21 TraceHistogramMax, 53.0s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 2774 SDtfs, 2398 SDslu, 12582 SDs, 0 SdLazy, 46419 SolverSat, 6679 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 36.1s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 2277 GetRequests, 1687 SyntacticMatches, 3 SemanticMatches, 587 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 25274 ImplicationChecksByTransitivity, 13.1s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=661occurred in iteration=18, 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: 1.4s AutomataMinimizationTime, 18 MinimizatonAttempts, 5163 StatesRemovedByMinimization, 10 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.3s SsaConstructionTime, 1.3s SatisfiabilityAnalysisTime, 5.3s InterpolantComputationTime, 3128 NumberOfCodeBlocks, 3066 NumberOfCodeBlocksAsserted, 49 NumberOfCheckSat, 3095 ConstructedInterpolants, 0 QuantifiedInterpolants, 595587 SizeOfPredicates, 70 NumberOfNonLiveVariables, 8480 ConjunctsInSsa, 152 ConjunctsInUnsatCore, 33 InterpolantComputations, 10 PerfectInterpolantSequences, 13603/14304 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/McCarthy9103.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_01-58-20-794.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/McCarthy9103.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_01-58-20-794.csv Completed graceful shutdown