java -Xmx8000000000 -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data --generate-csv --csv-dir csv -tc ../../../trunk/examples/toolchains/AutomizerBplInline.xml -s ../../../trunk/examples/settings/pu-bench/svcomp-Reach-32bit-Automizer_Default_PUPT.epf -i ../../../trunk/examples/programs/20170304-DifficultPathPrograms/jain_5.i_2.bpl -------------------------------------------------------------------------------- This is Ultimate 0.1.23-133090d [2018-10-04 09:45:20,424 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-10-04 09:45:20,426 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-10-04 09:45:20,437 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-10-04 09:45:20,437 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-10-04 09:45:20,438 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-10-04 09:45:20,440 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-10-04 09:45:20,441 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-10-04 09:45:20,443 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-10-04 09:45:20,444 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-10-04 09:45:20,445 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-10-04 09:45:20,445 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-10-04 09:45:20,446 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-10-04 09:45:20,447 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-10-04 09:45:20,448 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-10-04 09:45:20,448 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-10-04 09:45:20,449 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-10-04 09:45:20,451 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-10-04 09:45:20,453 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-10-04 09:45:20,455 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-10-04 09:45:20,456 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-10-04 09:45:20,460 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-10-04 09:45:20,463 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-10-04 09:45:20,465 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-10-04 09:45:20,465 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-10-04 09:45:20,466 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-10-04 09:45:20,470 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-10-04 09:45:20,471 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-10-04 09:45:20,474 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-10-04 09:45:20,476 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-10-04 09:45:20,476 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-10-04 09:45:20,476 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-10-04 09:45:20,477 INFO L177 SettingsManager]: ReqParser provides no preferences, ignoring... [2018-10-04 09:45:20,479 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-10-04 09:45:20,480 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-10-04 09:45:20,481 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-10-04 09:45:20,481 INFO L98 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/pu-bench/svcomp-Reach-32bit-Automizer_Default_PUPT.epf [2018-10-04 09:45:20,509 INFO L110 SettingsManager]: Loading preferences was successful [2018-10-04 09:45:20,509 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-10-04 09:45:20,510 INFO L131 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2018-10-04 09:45:20,510 INFO L133 SettingsManager]: * to procedures, called more than once=true [2018-10-04 09:45:20,511 INFO L131 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2018-10-04 09:45:20,511 INFO L133 SettingsManager]: * Create parallel compositions if possible=false [2018-10-04 09:45:20,511 INFO L133 SettingsManager]: * Use SBE=true [2018-10-04 09:45:20,512 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-10-04 09:45:20,512 INFO L133 SettingsManager]: * sizeof long=4 [2018-10-04 09:45:20,512 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-10-04 09:45:20,512 INFO L133 SettingsManager]: * sizeof POINTER=4 [2018-10-04 09:45:20,512 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-10-04 09:45:20,513 INFO L133 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2018-10-04 09:45:20,513 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-10-04 09:45:20,513 INFO L133 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2018-10-04 09:45:20,513 INFO L133 SettingsManager]: * sizeof long double=12 [2018-10-04 09:45:20,513 INFO L133 SettingsManager]: * Check if freed pointer was valid=false [2018-10-04 09:45:20,514 INFO L133 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2018-10-04 09:45:20,515 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-10-04 09:45:20,515 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-10-04 09:45:20,515 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-10-04 09:45:20,515 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-10-04 09:45:20,515 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-10-04 09:45:20,516 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-10-04 09:45:20,517 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-10-04 09:45:20,517 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-10-04 09:45:20,517 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-10-04 09:45:20,517 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-10-04 09:45:20,517 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-10-04 09:45:20,518 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-10-04 09:45:20,518 INFO L133 SettingsManager]: * Use predicate trie based predicate unification=true [2018-10-04 09:45:20,570 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-10-04 09:45:20,584 INFO L258 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-10-04 09:45:20,589 INFO L214 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2018-10-04 09:45:20,591 INFO L271 PluginConnector]: Initializing Boogie PL CUP Parser... [2018-10-04 09:45:20,591 INFO L276 PluginConnector]: Boogie PL CUP Parser initialized [2018-10-04 09:45:20,592 INFO L418 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/programs/20170304-DifficultPathPrograms/jain_5.i_2.bpl [2018-10-04 09:45:20,592 INFO L111 BoogieParser]: Parsing: '/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/programs/20170304-DifficultPathPrograms/jain_5.i_2.bpl' [2018-10-04 09:45:20,639 INFO L296 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-10-04 09:45:20,641 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2018-10-04 09:45:20,642 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2018-10-04 09:45:20,642 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2018-10-04 09:45:20,642 INFO L276 PluginConnector]: Boogie Procedure Inliner initialized [2018-10-04 09:45:20,662 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "jain_5.i_2.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 04.10 09:45:20" (1/1) ... [2018-10-04 09:45:20,674 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "jain_5.i_2.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 04.10 09:45:20" (1/1) ... [2018-10-04 09:45:20,681 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2018-10-04 09:45:20,681 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-10-04 09:45:20,682 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-10-04 09:45:20,682 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-10-04 09:45:20,693 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "jain_5.i_2.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 04.10 09:45:20" (1/1) ... [2018-10-04 09:45:20,693 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "jain_5.i_2.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 04.10 09:45:20" (1/1) ... [2018-10-04 09:45:20,694 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "jain_5.i_2.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 04.10 09:45:20" (1/1) ... [2018-10-04 09:45:20,694 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "jain_5.i_2.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 04.10 09:45:20" (1/1) ... [2018-10-04 09:45:20,697 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "jain_5.i_2.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 04.10 09:45:20" (1/1) ... [2018-10-04 09:45:20,699 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "jain_5.i_2.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 04.10 09:45:20" (1/1) ... [2018-10-04 09:45:20,700 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "jain_5.i_2.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 04.10 09:45:20" (1/1) ... [2018-10-04 09:45:20,701 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-10-04 09:45:20,701 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-10-04 09:45:20,702 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-10-04 09:45:20,702 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-10-04 09:45:20,703 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "jain_5.i_2.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 04.10 09:45:20" (1/1) ... No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-10-04 09:45:20,772 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-10-04 09:45:20,772 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-10-04 09:45:20,948 INFO L341 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-10-04 09:45:20,949 INFO L202 PluginConnector]: Adding new model jain_5.i_2.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 04.10 09:45:20 BoogieIcfgContainer [2018-10-04 09:45:20,949 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-10-04 09:45:20,950 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-10-04 09:45:20,950 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-10-04 09:45:20,953 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-10-04 09:45:20,954 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "jain_5.i_2.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 04.10 09:45:20" (1/2) ... [2018-10-04 09:45:20,955 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@436d8af5 and model type jain_5.i_2.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 04.10 09:45:20, skipping insertion in model container [2018-10-04 09:45:20,955 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "jain_5.i_2.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 04.10 09:45:20" (2/2) ... [2018-10-04 09:45:20,957 INFO L112 eAbstractionObserver]: Analyzing ICFG jain_5.i_2.bpl [2018-10-04 09:45:20,966 INFO L136 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-10-04 09:45:20,974 INFO L148 ceAbstractionStarter]: Appying trace abstraction to program that has 1 error locations. [2018-10-04 09:45:21,025 INFO L133 ementStrategyFactory]: Using default assertion order modulation [2018-10-04 09:45:21,026 INFO L381 AbstractCegarLoop]: Interprodecural is true [2018-10-04 09:45:21,026 INFO L382 AbstractCegarLoop]: Hoare is true [2018-10-04 09:45:21,026 INFO L383 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-10-04 09:45:21,027 INFO L384 AbstractCegarLoop]: Backedges is STRAIGHT_LINE [2018-10-04 09:45:21,027 INFO L385 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-10-04 09:45:21,027 INFO L386 AbstractCegarLoop]: Difference is false [2018-10-04 09:45:21,027 INFO L387 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-10-04 09:45:21,027 INFO L392 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-10-04 09:45:21,043 INFO L276 IsEmpty]: Start isEmpty. Operand 7 states. [2018-10-04 09:45:21,049 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 5 [2018-10-04 09:45:21,049 INFO L367 BasicCegarLoop]: Found error trace [2018-10-04 09:45:21,050 INFO L375 BasicCegarLoop]: trace histogram [1, 1, 1, 1] [2018-10-04 09:45:21,052 INFO L423 AbstractCegarLoop]: === Iteration 1 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-04 09:45:21,059 INFO L104 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-04 09:45:21,059 INFO L82 PathProgramCache]: Analyzing trace with hash 925701, now seen corresponding path program 1 times [2018-10-04 09:45:21,061 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-04 09:45:21,062 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-04 09:45:21,115 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 09:45:21,115 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-04 09:45:21,116 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 09:45:21,159 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 09:45:21,271 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 09:45:21,273 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-10-04 09:45:21,273 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-10-04 09:45:21,277 INFO L459 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-10-04 09:45:21,289 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-10-04 09:45:21,289 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-04 09:45:21,291 INFO L87 Difference]: Start difference. First operand 7 states. Second operand 4 states. [2018-10-04 09:45:21,370 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-04 09:45:21,371 INFO L93 Difference]: Finished difference Result 12 states and 13 transitions. [2018-10-04 09:45:21,371 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-10-04 09:45:21,373 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 4 [2018-10-04 09:45:21,373 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-04 09:45:21,385 INFO L225 Difference]: With dead ends: 12 [2018-10-04 09:45:21,385 INFO L226 Difference]: Without dead ends: 8 [2018-10-04 09:45:21,389 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s Time 0.0s impTime 2 [2018-10-04 09:45:21,408 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 8 states. [2018-10-04 09:45:21,426 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 8 to 7. [2018-10-04 09:45:21,428 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 7 states. [2018-10-04 09:45:21,429 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7 states to 7 states and 7 transitions. [2018-10-04 09:45:21,431 INFO L78 Accepts]: Start accepts. Automaton has 7 states and 7 transitions. Word has length 4 [2018-10-04 09:45:21,431 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-04 09:45:21,431 INFO L480 AbstractCegarLoop]: Abstraction has 7 states and 7 transitions. [2018-10-04 09:45:21,432 INFO L481 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-10-04 09:45:21,432 INFO L276 IsEmpty]: Start isEmpty. Operand 7 states and 7 transitions. [2018-10-04 09:45:21,435 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 7 [2018-10-04 09:45:21,435 INFO L367 BasicCegarLoop]: Found error trace [2018-10-04 09:45:21,436 INFO L375 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1] [2018-10-04 09:45:21,436 INFO L423 AbstractCegarLoop]: === Iteration 2 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-04 09:45:21,436 INFO L104 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-04 09:45:21,437 INFO L82 PathProgramCache]: Analyzing trace with hash 889531649, now seen corresponding path program 1 times [2018-10-04 09:45:21,437 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-04 09:45:21,437 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-04 09:45:21,438 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 09:45:21,438 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-04 09:45:21,439 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 09:45:21,454 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 09:45:21,634 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 09:45:21,634 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-04 09:45:21,634 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 2 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-04 09:45:21,651 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-04 09:45:21,675 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 09:45:21,683 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-04 09:45:21,878 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 09:45:21,900 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-04 09:45:21,900 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 9 [2018-10-04 09:45:21,900 INFO L459 AbstractCegarLoop]: Interpolant automaton has 10 states [2018-10-04 09:45:21,902 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2018-10-04 09:45:21,902 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-04 09:45:21,902 INFO L87 Difference]: Start difference. First operand 7 states and 7 transitions. Second operand 10 states. [2018-10-04 09:45:22,009 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-04 09:45:22,009 INFO L93 Difference]: Finished difference Result 12 states and 12 transitions. [2018-10-04 09:45:22,010 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-10-04 09:45:22,010 INFO L78 Accepts]: Start accepts. Automaton has 10 states. Word has length 6 [2018-10-04 09:45:22,010 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-04 09:45:22,011 INFO L225 Difference]: With dead ends: 12 [2018-10-04 09:45:22,011 INFO L226 Difference]: Without dead ends: 10 [2018-10-04 09:45:22,012 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.3s Time 0.1s impTime 7 [2018-10-04 09:45:22,012 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 10 states. [2018-10-04 09:45:22,015 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 10 to 9. [2018-10-04 09:45:22,016 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 9 states. [2018-10-04 09:45:22,016 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 9 states to 9 states and 9 transitions. [2018-10-04 09:45:22,017 INFO L78 Accepts]: Start accepts. Automaton has 9 states and 9 transitions. Word has length 6 [2018-10-04 09:45:22,017 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-04 09:45:22,017 INFO L480 AbstractCegarLoop]: Abstraction has 9 states and 9 transitions. [2018-10-04 09:45:22,017 INFO L481 AbstractCegarLoop]: Interpolant automaton has 10 states. [2018-10-04 09:45:22,017 INFO L276 IsEmpty]: Start isEmpty. Operand 9 states and 9 transitions. [2018-10-04 09:45:22,018 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 9 [2018-10-04 09:45:22,018 INFO L367 BasicCegarLoop]: Found error trace [2018-10-04 09:45:22,018 INFO L375 BasicCegarLoop]: trace histogram [3, 2, 1, 1, 1] [2018-10-04 09:45:22,019 INFO L423 AbstractCegarLoop]: === Iteration 3 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-04 09:45:22,019 INFO L104 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-04 09:45:22,019 INFO L82 PathProgramCache]: Analyzing trace with hash 141355773, now seen corresponding path program 2 times [2018-10-04 09:45:22,019 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-04 09:45:22,019 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-04 09:45:22,020 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 09:45:22,021 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-04 09:45:22,021 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 09:45:22,035 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 09:45:22,381 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 09:45:22,382 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-04 09:45:22,382 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/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-10-04 09:45:22,392 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-10-04 09:45:22,430 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-10-04 09:45:22,430 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-04 09:45:22,432 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-04 09:45:22,693 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 09:45:22,714 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-04 09:45:22,714 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 11 [2018-10-04 09:45:22,714 INFO L459 AbstractCegarLoop]: Interpolant automaton has 12 states [2018-10-04 09:45:22,715 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2018-10-04 09:45:22,715 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-04 09:45:22,715 INFO L87 Difference]: Start difference. First operand 9 states and 9 transitions. Second operand 12 states. [2018-10-04 09:45:22,942 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-04 09:45:22,942 INFO L93 Difference]: Finished difference Result 14 states and 14 transitions. [2018-10-04 09:45:22,944 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-10-04 09:45:22,944 INFO L78 Accepts]: Start accepts. Automaton has 12 states. Word has length 8 [2018-10-04 09:45:22,944 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-04 09:45:22,944 INFO L225 Difference]: With dead ends: 14 [2018-10-04 09:45:22,945 INFO L226 Difference]: Without dead ends: 12 [2018-10-04 09:45:22,945 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 14 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.5s Time 0.3s impTime 8 [2018-10-04 09:45:22,945 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 12 states. [2018-10-04 09:45:22,949 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 12 to 11. [2018-10-04 09:45:22,950 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 11 states. [2018-10-04 09:45:22,950 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 11 states to 11 states and 11 transitions. [2018-10-04 09:45:22,950 INFO L78 Accepts]: Start accepts. Automaton has 11 states and 11 transitions. Word has length 8 [2018-10-04 09:45:22,951 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-04 09:45:22,951 INFO L480 AbstractCegarLoop]: Abstraction has 11 states and 11 transitions. [2018-10-04 09:45:22,951 INFO L481 AbstractCegarLoop]: Interpolant automaton has 12 states. [2018-10-04 09:45:22,952 INFO L276 IsEmpty]: Start isEmpty. Operand 11 states and 11 transitions. [2018-10-04 09:45:22,952 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2018-10-04 09:45:22,952 INFO L367 BasicCegarLoop]: Found error trace [2018-10-04 09:45:22,953 INFO L375 BasicCegarLoop]: trace histogram [4, 3, 1, 1, 1] [2018-10-04 09:45:22,953 INFO L423 AbstractCegarLoop]: === Iteration 4 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-04 09:45:22,953 INFO L104 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-04 09:45:22,953 INFO L82 PathProgramCache]: Analyzing trace with hash -1596122631, now seen corresponding path program 3 times [2018-10-04 09:45:22,953 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-04 09:45:22,955 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-04 09:45:22,956 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 09:45:22,956 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-04 09:45:22,956 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 09:45:22,978 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 09:45:23,172 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 12 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 09:45:23,173 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-04 09:45:23,173 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/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-10-04 09:45:23,186 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-10-04 09:45:23,206 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-10-04 09:45:23,207 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-04 09:45:23,208 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-04 09:45:23,348 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 12 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 09:45:23,368 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-04 09:45:23,368 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 13 [2018-10-04 09:45:23,369 INFO L459 AbstractCegarLoop]: Interpolant automaton has 14 states [2018-10-04 09:45:23,369 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2018-10-04 09:45:23,369 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-04 09:45:23,370 INFO L87 Difference]: Start difference. First operand 11 states and 11 transitions. Second operand 14 states. [2018-10-04 09:45:23,891 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-04 09:45:23,891 INFO L93 Difference]: Finished difference Result 16 states and 16 transitions. [2018-10-04 09:45:23,895 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-10-04 09:45:23,895 INFO L78 Accepts]: Start accepts. Automaton has 14 states. Word has length 10 [2018-10-04 09:45:23,895 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-04 09:45:23,896 INFO L225 Difference]: With dead ends: 16 [2018-10-04 09:45:23,896 INFO L226 Difference]: Without dead ends: 14 [2018-10-04 09:45:23,896 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 18 GetRequests, 4 SyntacticMatches, 0 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.4s Time 0.3s impTime 11 [2018-10-04 09:45:23,896 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 14 states. [2018-10-04 09:45:23,900 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 14 to 13. [2018-10-04 09:45:23,901 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 13 states. [2018-10-04 09:45:23,901 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 13 states to 13 states and 13 transitions. [2018-10-04 09:45:23,902 INFO L78 Accepts]: Start accepts. Automaton has 13 states and 13 transitions. Word has length 10 [2018-10-04 09:45:23,902 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-04 09:45:23,902 INFO L480 AbstractCegarLoop]: Abstraction has 13 states and 13 transitions. [2018-10-04 09:45:23,902 INFO L481 AbstractCegarLoop]: Interpolant automaton has 14 states. [2018-10-04 09:45:23,902 INFO L276 IsEmpty]: Start isEmpty. Operand 13 states and 13 transitions. [2018-10-04 09:45:23,903 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2018-10-04 09:45:23,903 INFO L367 BasicCegarLoop]: Found error trace [2018-10-04 09:45:23,903 INFO L375 BasicCegarLoop]: trace histogram [5, 4, 1, 1, 1] [2018-10-04 09:45:23,904 INFO L423 AbstractCegarLoop]: === Iteration 5 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-04 09:45:23,904 INFO L104 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-04 09:45:23,904 INFO L82 PathProgramCache]: Analyzing trace with hash -570590731, now seen corresponding path program 4 times [2018-10-04 09:45:23,904 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-04 09:45:23,904 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-04 09:45:23,905 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 09:45:23,905 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-04 09:45:23,905 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 09:45:23,919 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 09:45:24,108 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 0 proven. 20 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 09:45:24,108 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-04 09:45:24,109 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/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-10-04 09:45:24,116 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-10-04 09:45:24,138 INFO L242 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-10-04 09:45:24,138 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-04 09:45:24,142 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-04 09:45:24,270 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 0 proven. 20 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 09:45:24,291 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-04 09:45:24,291 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 15 [2018-10-04 09:45:24,291 INFO L459 AbstractCegarLoop]: Interpolant automaton has 16 states [2018-10-04 09:45:24,292 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2018-10-04 09:45:24,292 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-04 09:45:24,292 INFO L87 Difference]: Start difference. First operand 13 states and 13 transitions. Second operand 16 states. [2018-10-04 09:45:24,500 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-04 09:45:24,500 INFO L93 Difference]: Finished difference Result 18 states and 18 transitions. [2018-10-04 09:45:24,500 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-10-04 09:45:24,500 INFO L78 Accepts]: Start accepts. Automaton has 16 states. Word has length 12 [2018-10-04 09:45:24,501 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-04 09:45:24,501 INFO L225 Difference]: With dead ends: 18 [2018-10-04 09:45:24,501 INFO L226 Difference]: Without dead ends: 16 [2018-10-04 09:45:24,502 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 22 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.3s Time 0.1s impTime 14 [2018-10-04 09:45:24,502 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 16 states. [2018-10-04 09:45:24,507 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 16 to 15. [2018-10-04 09:45:24,507 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 15 states. [2018-10-04 09:45:24,508 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 15 states to 15 states and 15 transitions. [2018-10-04 09:45:24,508 INFO L78 Accepts]: Start accepts. Automaton has 15 states and 15 transitions. Word has length 12 [2018-10-04 09:45:24,509 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-04 09:45:24,509 INFO L480 AbstractCegarLoop]: Abstraction has 15 states and 15 transitions. [2018-10-04 09:45:24,509 INFO L481 AbstractCegarLoop]: Interpolant automaton has 16 states. [2018-10-04 09:45:24,509 INFO L276 IsEmpty]: Start isEmpty. Operand 15 states and 15 transitions. [2018-10-04 09:45:24,509 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2018-10-04 09:45:24,510 INFO L367 BasicCegarLoop]: Found error trace [2018-10-04 09:45:24,510 INFO L375 BasicCegarLoop]: trace histogram [6, 5, 1, 1, 1] [2018-10-04 09:45:24,510 INFO L423 AbstractCegarLoop]: === Iteration 6 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-04 09:45:24,510 INFO L104 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-04 09:45:24,511 INFO L82 PathProgramCache]: Analyzing trace with hash 1418054385, now seen corresponding path program 5 times [2018-10-04 09:45:24,511 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-04 09:45:24,511 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-04 09:45:24,512 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 09:45:24,512 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-04 09:45:24,512 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 09:45:24,525 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 09:45:24,836 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 0 proven. 30 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 09:45:24,837 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-04 09:45:24,837 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/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-10-04 09:45:24,857 INFO L103 rtionOrderModulation]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-10-04 09:45:39,553 INFO L242 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2018-10-04 09:45:39,553 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-04 09:45:39,568 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-04 09:45:39,729 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 0 proven. 30 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 09:45:39,750 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-04 09:45:39,750 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 17 [2018-10-04 09:45:39,751 INFO L459 AbstractCegarLoop]: Interpolant automaton has 18 states [2018-10-04 09:45:39,751 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2018-10-04 09:45:39,751 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-04 09:45:39,751 INFO L87 Difference]: Start difference. First operand 15 states and 15 transitions. Second operand 18 states. [2018-10-04 09:45:40,166 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-04 09:45:40,166 INFO L93 Difference]: Finished difference Result 20 states and 20 transitions. [2018-10-04 09:45:40,166 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-10-04 09:45:40,166 INFO L78 Accepts]: Start accepts. Automaton has 18 states. Word has length 14 [2018-10-04 09:45:40,167 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-04 09:45:40,167 INFO L225 Difference]: With dead ends: 20 [2018-10-04 09:45:40,167 INFO L226 Difference]: Without dead ends: 18 [2018-10-04 09:45:40,168 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 26 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.5s Time 0.3s impTime 17 [2018-10-04 09:45:40,168 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 18 states. [2018-10-04 09:45:40,172 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 18 to 17. [2018-10-04 09:45:40,173 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 17 states. [2018-10-04 09:45:40,173 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 17 states to 17 states and 17 transitions. [2018-10-04 09:45:40,174 INFO L78 Accepts]: Start accepts. Automaton has 17 states and 17 transitions. Word has length 14 [2018-10-04 09:45:40,174 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-04 09:45:40,174 INFO L480 AbstractCegarLoop]: Abstraction has 17 states and 17 transitions. [2018-10-04 09:45:40,174 INFO L481 AbstractCegarLoop]: Interpolant automaton has 18 states. [2018-10-04 09:45:40,174 INFO L276 IsEmpty]: Start isEmpty. Operand 17 states and 17 transitions. [2018-10-04 09:45:40,175 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2018-10-04 09:45:40,175 INFO L367 BasicCegarLoop]: Found error trace [2018-10-04 09:45:40,175 INFO L375 BasicCegarLoop]: trace histogram [7, 6, 1, 1, 1] [2018-10-04 09:45:40,176 INFO L423 AbstractCegarLoop]: === Iteration 7 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-04 09:45:40,176 INFO L104 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-04 09:45:40,176 INFO L82 PathProgramCache]: Analyzing trace with hash 1245564141, now seen corresponding path program 6 times [2018-10-04 09:45:40,176 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-04 09:45:40,176 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-04 09:45:40,177 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 09:45:40,177 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-04 09:45:40,178 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 09:45:40,192 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 09:45:40,439 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 0 proven. 42 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 09:45:40,439 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-04 09:45:40,440 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/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-10-04 09:45:40,455 INFO L103 rtionOrderModulation]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-10-04 09:45:52,835 INFO L242 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2018-10-04 09:45:52,835 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-04 09:45:52,839 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-04 09:45:52,993 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 0 proven. 42 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 09:45:53,014 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-04 09:45:53,014 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 19 [2018-10-04 09:45:53,015 INFO L459 AbstractCegarLoop]: Interpolant automaton has 20 states [2018-10-04 09:45:53,015 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2018-10-04 09:45:53,015 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-04 09:45:53,015 INFO L87 Difference]: Start difference. First operand 17 states and 17 transitions. Second operand 20 states. [2018-10-04 09:45:53,231 INFO L248 BPredicateUnifier]: --------PredicateTrie is restructured: old depths: 19 new depth: 8 [2018-10-04 09:45:53,342 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-04 09:45:53,342 INFO L93 Difference]: Finished difference Result 22 states and 22 transitions. [2018-10-04 09:45:53,342 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-10-04 09:45:53,343 INFO L78 Accepts]: Start accepts. Automaton has 20 states. Word has length 16 [2018-10-04 09:45:53,343 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-04 09:45:53,344 INFO L225 Difference]: With dead ends: 22 [2018-10-04 09:45:53,344 INFO L226 Difference]: Without dead ends: 20 [2018-10-04 09:45:53,345 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 30 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.4s Time 0.2s impTime 9 [2018-10-04 09:45:53,345 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 20 states. [2018-10-04 09:45:53,350 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 20 to 19. [2018-10-04 09:45:53,350 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 19 states. [2018-10-04 09:45:53,351 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 19 states to 19 states and 19 transitions. [2018-10-04 09:45:53,351 INFO L78 Accepts]: Start accepts. Automaton has 19 states and 19 transitions. Word has length 16 [2018-10-04 09:45:53,351 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-04 09:45:53,351 INFO L480 AbstractCegarLoop]: Abstraction has 19 states and 19 transitions. [2018-10-04 09:45:53,351 INFO L481 AbstractCegarLoop]: Interpolant automaton has 20 states. [2018-10-04 09:45:53,351 INFO L276 IsEmpty]: Start isEmpty. Operand 19 states and 19 transitions. [2018-10-04 09:45:53,352 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2018-10-04 09:45:53,352 INFO L367 BasicCegarLoop]: Found error trace [2018-10-04 09:45:53,352 INFO L375 BasicCegarLoop]: trace histogram [8, 7, 1, 1, 1] [2018-10-04 09:45:53,353 INFO L423 AbstractCegarLoop]: === Iteration 8 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-04 09:45:53,353 INFO L104 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-04 09:45:53,353 INFO L82 PathProgramCache]: Analyzing trace with hash -1308803095, now seen corresponding path program 7 times [2018-10-04 09:45:53,353 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-04 09:45:53,353 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-04 09:45:53,354 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 09:45:53,354 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-04 09:45:53,355 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 09:45:53,369 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 09:45:53,620 INFO L134 CoverageAnalysis]: Checked inductivity of 56 backedges. 0 proven. 56 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 09:45:53,620 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-04 09:45:53,620 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/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-10-04 09:45:53,628 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-04 09:45:53,649 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 09:45:53,651 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-04 09:45:53,864 INFO L134 CoverageAnalysis]: Checked inductivity of 56 backedges. 0 proven. 56 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 09:45:53,884 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-04 09:45:53,884 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11] total 21 [2018-10-04 09:45:53,885 INFO L459 AbstractCegarLoop]: Interpolant automaton has 22 states [2018-10-04 09:45:53,885 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2018-10-04 09:45:53,885 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-04 09:45:53,886 INFO L87 Difference]: Start difference. First operand 19 states and 19 transitions. Second operand 22 states. [2018-10-04 09:45:54,341 INFO L248 BPredicateUnifier]: --------PredicateTrie is restructured: old depths: 19 new depth: 9 [2018-10-04 09:45:54,712 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-04 09:45:54,713 INFO L93 Difference]: Finished difference Result 24 states and 24 transitions. [2018-10-04 09:45:54,713 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-10-04 09:45:54,713 INFO L78 Accepts]: Start accepts. Automaton has 22 states. Word has length 18 [2018-10-04 09:45:54,713 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-04 09:45:54,714 INFO L225 Difference]: With dead ends: 24 [2018-10-04 09:45:54,714 INFO L226 Difference]: Without dead ends: 22 [2018-10-04 09:45:54,714 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 34 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.6s Time 0.4s impTime 13 [2018-10-04 09:45:54,714 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 22 states. [2018-10-04 09:45:54,720 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 22 to 21. [2018-10-04 09:45:54,720 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 21 states. [2018-10-04 09:45:54,720 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 21 states to 21 states and 21 transitions. [2018-10-04 09:45:54,721 INFO L78 Accepts]: Start accepts. Automaton has 21 states and 21 transitions. Word has length 18 [2018-10-04 09:45:54,721 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-04 09:45:54,721 INFO L480 AbstractCegarLoop]: Abstraction has 21 states and 21 transitions. [2018-10-04 09:45:54,721 INFO L481 AbstractCegarLoop]: Interpolant automaton has 22 states. [2018-10-04 09:45:54,721 INFO L276 IsEmpty]: Start isEmpty. Operand 21 states and 21 transitions. [2018-10-04 09:45:54,722 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2018-10-04 09:45:54,722 INFO L367 BasicCegarLoop]: Found error trace [2018-10-04 09:45:54,722 INFO L375 BasicCegarLoop]: trace histogram [9, 8, 1, 1, 1] [2018-10-04 09:45:54,723 INFO L423 AbstractCegarLoop]: === Iteration 9 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-04 09:45:54,723 INFO L104 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-04 09:45:54,723 INFO L82 PathProgramCache]: Analyzing trace with hash 665576421, now seen corresponding path program 8 times [2018-10-04 09:45:54,723 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-04 09:45:54,723 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-04 09:45:54,724 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 09:45:54,724 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-04 09:45:54,724 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 09:45:54,744 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 09:45:55,355 INFO L134 CoverageAnalysis]: Checked inductivity of 72 backedges. 0 proven. 72 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 09:45:55,355 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-04 09:45:55,355 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/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-10-04 09:45:55,366 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-10-04 09:45:55,384 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-10-04 09:45:55,384 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-04 09:45:55,386 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-04 09:45:55,940 INFO L248 BPredicateUnifier]: --------PredicateTrie is restructured: old depths: 19 new depth: 10 [2018-10-04 09:45:55,962 INFO L134 CoverageAnalysis]: Checked inductivity of 72 backedges. 0 proven. 72 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 09:45:55,982 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-04 09:45:55,982 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 23 [2018-10-04 09:45:55,983 INFO L459 AbstractCegarLoop]: Interpolant automaton has 24 states [2018-10-04 09:45:55,983 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2018-10-04 09:45:55,983 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-04 09:45:55,984 INFO L87 Difference]: Start difference. First operand 21 states and 21 transitions. Second operand 24 states. [2018-10-04 09:45:56,836 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-04 09:45:56,836 INFO L93 Difference]: Finished difference Result 26 states and 26 transitions. [2018-10-04 09:45:56,838 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-10-04 09:45:56,838 INFO L78 Accepts]: Start accepts. Automaton has 24 states. Word has length 20 [2018-10-04 09:45:56,838 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-04 09:45:56,839 INFO L225 Difference]: With dead ends: 26 [2018-10-04 09:45:56,839 INFO L226 Difference]: Without dead ends: 24 [2018-10-04 09:45:56,840 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 38 GetRequests, 9 SyntacticMatches, 0 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 1.2s Time 0.9s impTime 17 [2018-10-04 09:45:56,840 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states. [2018-10-04 09:45:56,846 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 23. [2018-10-04 09:45:56,846 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 23 states. [2018-10-04 09:45:56,847 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 23 states to 23 states and 23 transitions. [2018-10-04 09:45:56,847 INFO L78 Accepts]: Start accepts. Automaton has 23 states and 23 transitions. Word has length 20 [2018-10-04 09:45:56,847 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-04 09:45:56,847 INFO L480 AbstractCegarLoop]: Abstraction has 23 states and 23 transitions. [2018-10-04 09:45:56,848 INFO L481 AbstractCegarLoop]: Interpolant automaton has 24 states. [2018-10-04 09:45:56,848 INFO L276 IsEmpty]: Start isEmpty. Operand 23 states and 23 transitions. [2018-10-04 09:45:56,848 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2018-10-04 09:45:56,848 INFO L367 BasicCegarLoop]: Found error trace [2018-10-04 09:45:56,849 INFO L375 BasicCegarLoop]: trace histogram [10, 9, 1, 1, 1] [2018-10-04 09:45:56,849 INFO L423 AbstractCegarLoop]: === Iteration 10 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-04 09:45:56,849 INFO L104 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-04 09:45:56,849 INFO L82 PathProgramCache]: Analyzing trace with hash -331253535, now seen corresponding path program 9 times [2018-10-04 09:45:56,849 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-04 09:45:56,849 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-04 09:45:56,850 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 09:45:56,851 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-04 09:45:56,851 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 09:45:56,865 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 09:45:57,150 INFO L134 CoverageAnalysis]: Checked inductivity of 90 backedges. 0 proven. 90 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 09:45:57,150 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-04 09:45:57,151 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/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-10-04 09:45:57,159 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-10-04 09:46:01,956 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 10 check-sat command(s) [2018-10-04 09:46:01,956 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-04 09:46:01,960 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-04 09:46:02,151 INFO L248 BPredicateUnifier]: --------PredicateTrie is restructured: old depths: 19 new depth: 10 [2018-10-04 09:46:02,202 INFO L134 CoverageAnalysis]: Checked inductivity of 90 backedges. 0 proven. 90 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 09:46:02,223 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-04 09:46:02,224 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 25 [2018-10-04 09:46:02,224 INFO L459 AbstractCegarLoop]: Interpolant automaton has 26 states [2018-10-04 09:46:02,224 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2018-10-04 09:46:02,224 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-04 09:46:02,225 INFO L87 Difference]: Start difference. First operand 23 states and 23 transitions. Second operand 26 states. [2018-10-04 09:46:02,668 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-04 09:46:02,668 INFO L93 Difference]: Finished difference Result 28 states and 28 transitions. [2018-10-04 09:46:02,669 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-10-04 09:46:02,669 INFO L78 Accepts]: Start accepts. Automaton has 26 states. Word has length 22 [2018-10-04 09:46:02,669 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-04 09:46:02,670 INFO L225 Difference]: With dead ends: 28 [2018-10-04 09:46:02,670 INFO L226 Difference]: Without dead ends: 26 [2018-10-04 09:46:02,671 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 42 GetRequests, 10 SyntacticMatches, 0 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.5s Time 0.3s impTime 20 [2018-10-04 09:46:02,671 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 26 states. [2018-10-04 09:46:02,678 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 26 to 25. [2018-10-04 09:46:02,678 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 25 states. [2018-10-04 09:46:02,678 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 25 states to 25 states and 25 transitions. [2018-10-04 09:46:02,678 INFO L78 Accepts]: Start accepts. Automaton has 25 states and 25 transitions. Word has length 22 [2018-10-04 09:46:02,679 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-04 09:46:02,679 INFO L480 AbstractCegarLoop]: Abstraction has 25 states and 25 transitions. [2018-10-04 09:46:02,679 INFO L481 AbstractCegarLoop]: Interpolant automaton has 26 states. [2018-10-04 09:46:02,679 INFO L276 IsEmpty]: Start isEmpty. Operand 25 states and 25 transitions. [2018-10-04 09:46:02,679 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2018-10-04 09:46:02,680 INFO L367 BasicCegarLoop]: Found error trace [2018-10-04 09:46:02,680 INFO L375 BasicCegarLoop]: trace histogram [11, 10, 1, 1, 1] [2018-10-04 09:46:02,680 INFO L423 AbstractCegarLoop]: === Iteration 11 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-04 09:46:02,680 INFO L104 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-04 09:46:02,680 INFO L82 PathProgramCache]: Analyzing trace with hash -507134243, now seen corresponding path program 10 times [2018-10-04 09:46:02,680 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-04 09:46:02,680 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-04 09:46:02,681 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 09:46:02,681 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-04 09:46:02,681 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 09:46:02,693 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 09:46:03,083 INFO L134 CoverageAnalysis]: Checked inductivity of 110 backedges. 0 proven. 110 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 09:46:03,084 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-04 09:46:03,084 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/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-10-04 09:46:03,092 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-10-04 09:46:03,123 INFO L242 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-10-04 09:46:03,123 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-04 09:46:03,126 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-04 09:46:03,453 INFO L248 BPredicateUnifier]: --------PredicateTrie is restructured: old depths: 19 new depth: 11 [2018-10-04 09:46:03,538 INFO L134 CoverageAnalysis]: Checked inductivity of 110 backedges. 0 proven. 110 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 09:46:03,558 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-04 09:46:03,558 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 27 [2018-10-04 09:46:03,559 INFO L459 AbstractCegarLoop]: Interpolant automaton has 28 states [2018-10-04 09:46:03,559 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2018-10-04 09:46:03,559 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-04 09:46:03,559 INFO L87 Difference]: Start difference. First operand 25 states and 25 transitions. Second operand 28 states. [2018-10-04 09:46:04,347 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-04 09:46:04,347 INFO L93 Difference]: Finished difference Result 30 states and 30 transitions. [2018-10-04 09:46:04,347 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2018-10-04 09:46:04,347 INFO L78 Accepts]: Start accepts. Automaton has 28 states. Word has length 24 [2018-10-04 09:46:04,348 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-04 09:46:04,348 INFO L225 Difference]: With dead ends: 30 [2018-10-04 09:46:04,348 INFO L226 Difference]: Without dead ends: 28 [2018-10-04 09:46:04,348 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 46 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.9s Time 0.6s impTime 24 [2018-10-04 09:46:04,349 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 28 states. [2018-10-04 09:46:04,355 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 28 to 27. [2018-10-04 09:46:04,356 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 27 states. [2018-10-04 09:46:04,356 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 27 states to 27 states and 27 transitions. [2018-10-04 09:46:04,356 INFO L78 Accepts]: Start accepts. Automaton has 27 states and 27 transitions. Word has length 24 [2018-10-04 09:46:04,357 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-04 09:46:04,357 INFO L480 AbstractCegarLoop]: Abstraction has 27 states and 27 transitions. [2018-10-04 09:46:04,357 INFO L481 AbstractCegarLoop]: Interpolant automaton has 28 states. [2018-10-04 09:46:04,357 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 27 transitions. [2018-10-04 09:46:04,358 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2018-10-04 09:46:04,358 INFO L367 BasicCegarLoop]: Found error trace [2018-10-04 09:46:04,358 INFO L375 BasicCegarLoop]: trace histogram [12, 11, 1, 1, 1] [2018-10-04 09:46:04,359 INFO L423 AbstractCegarLoop]: === Iteration 12 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-04 09:46:04,359 INFO L104 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-04 09:46:04,359 INFO L82 PathProgramCache]: Analyzing trace with hash -2024770087, now seen corresponding path program 11 times [2018-10-04 09:46:04,359 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-04 09:46:04,359 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-04 09:46:04,360 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 09:46:04,360 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-04 09:46:04,360 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 09:46:04,371 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 09:46:04,638 INFO L134 CoverageAnalysis]: Checked inductivity of 132 backedges. 0 proven. 132 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 09:46:04,638 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-04 09:46:04,638 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/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-10-04 09:46:04,646 INFO L103 rtionOrderModulation]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-10-04 09:47:35,376 INFO L242 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 12 check-sat command(s) [2018-10-04 09:47:35,376 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-04 09:47:35,419 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-04 09:47:35,571 INFO L248 BPredicateUnifier]: --------PredicateTrie is restructured: old depths: 19 new depth: 13 [2018-10-04 09:47:35,719 INFO L134 CoverageAnalysis]: Checked inductivity of 132 backedges. 0 proven. 132 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 09:47:35,749 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-04 09:47:35,750 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 15] total 29 [2018-10-04 09:47:35,750 INFO L459 AbstractCegarLoop]: Interpolant automaton has 30 states [2018-10-04 09:47:35,750 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2018-10-04 09:47:35,750 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-04 09:47:35,751 INFO L87 Difference]: Start difference. First operand 27 states and 27 transitions. Second operand 30 states. [2018-10-04 09:47:36,566 INFO L248 BPredicateUnifier]: --------PredicateTrie is restructured: old depths: 29 new depth: 13 [2018-10-04 09:47:36,659 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-04 09:47:36,659 INFO L93 Difference]: Finished difference Result 32 states and 32 transitions. [2018-10-04 09:47:36,659 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2018-10-04 09:47:36,659 INFO L78 Accepts]: Start accepts. Automaton has 30 states. Word has length 26 [2018-10-04 09:47:36,660 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-04 09:47:36,660 INFO L225 Difference]: With dead ends: 32 [2018-10-04 09:47:36,660 INFO L226 Difference]: Without dead ends: 30 [2018-10-04 09:47:36,661 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 50 GetRequests, 12 SyntacticMatches, 0 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.7s Time 0.5s impTime 14 [2018-10-04 09:47:36,661 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 30 states. [2018-10-04 09:47:36,668 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 30 to 29. [2018-10-04 09:47:36,668 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 29 states. [2018-10-04 09:47:36,669 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 29 states to 29 states and 29 transitions. [2018-10-04 09:47:36,669 INFO L78 Accepts]: Start accepts. Automaton has 29 states and 29 transitions. Word has length 26 [2018-10-04 09:47:36,669 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-04 09:47:36,669 INFO L480 AbstractCegarLoop]: Abstraction has 29 states and 29 transitions. [2018-10-04 09:47:36,669 INFO L481 AbstractCegarLoop]: Interpolant automaton has 30 states. [2018-10-04 09:47:36,670 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 29 transitions. [2018-10-04 09:47:36,670 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2018-10-04 09:47:36,670 INFO L367 BasicCegarLoop]: Found error trace [2018-10-04 09:47:36,670 INFO L375 BasicCegarLoop]: trace histogram [13, 12, 1, 1, 1] [2018-10-04 09:47:36,671 INFO L423 AbstractCegarLoop]: === Iteration 13 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-04 09:47:36,671 INFO L104 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-04 09:47:36,671 INFO L82 PathProgramCache]: Analyzing trace with hash -183935531, now seen corresponding path program 12 times [2018-10-04 09:47:36,671 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-04 09:47:36,671 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-04 09:47:36,672 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 09:47:36,672 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-04 09:47:36,672 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 09:47:36,684 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 09:47:37,713 INFO L134 CoverageAnalysis]: Checked inductivity of 156 backedges. 0 proven. 156 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 09:47:37,714 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-04 09:47:37,714 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/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-10-04 09:47:37,722 INFO L103 rtionOrderModulation]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-10-04 09:48:37,763 INFO L242 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 13 check-sat command(s) [2018-10-04 09:48:37,763 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-04 09:48:38,138 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-04 09:48:38,260 INFO L248 BPredicateUnifier]: --------PredicateTrie is restructured: old depths: 19 new depth: 13 [2018-10-04 09:48:38,423 INFO L134 CoverageAnalysis]: Checked inductivity of 156 backedges. 0 proven. 156 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 09:48:38,444 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-04 09:48:38,444 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 31 [2018-10-04 09:48:38,444 INFO L459 AbstractCegarLoop]: Interpolant automaton has 32 states [2018-10-04 09:48:38,445 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2018-10-04 09:48:38,445 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-04 09:48:38,445 INFO L87 Difference]: Start difference. First operand 29 states and 29 transitions. Second operand 32 states. [2018-10-04 09:48:39,058 INFO L248 BPredicateUnifier]: --------PredicateTrie is restructured: old depths: 29 new depth: 14 [2018-10-04 09:48:39,248 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-04 09:48:39,248 INFO L93 Difference]: Finished difference Result 34 states and 34 transitions. [2018-10-04 09:48:39,249 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2018-10-04 09:48:39,249 INFO L78 Accepts]: Start accepts. Automaton has 32 states. Word has length 28 [2018-10-04 09:48:39,249 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-04 09:48:39,250 INFO L225 Difference]: With dead ends: 34 [2018-10-04 09:48:39,250 INFO L226 Difference]: Without dead ends: 32 [2018-10-04 09:48:39,250 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 54 GetRequests, 13 SyntacticMatches, 0 SemanticMatches, 41 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 1.4s Time 1.0s impTime 17 [2018-10-04 09:48:39,250 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2018-10-04 09:48:39,262 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 31. [2018-10-04 09:48:39,262 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 31 states. [2018-10-04 09:48:39,263 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 31 states to 31 states and 31 transitions. [2018-10-04 09:48:39,263 INFO L78 Accepts]: Start accepts. Automaton has 31 states and 31 transitions. Word has length 28 [2018-10-04 09:48:39,263 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-04 09:48:39,264 INFO L480 AbstractCegarLoop]: Abstraction has 31 states and 31 transitions. [2018-10-04 09:48:39,264 INFO L481 AbstractCegarLoop]: Interpolant automaton has 32 states. [2018-10-04 09:48:39,264 INFO L276 IsEmpty]: Start isEmpty. Operand 31 states and 31 transitions. [2018-10-04 09:48:39,265 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2018-10-04 09:48:39,265 INFO L367 BasicCegarLoop]: Found error trace [2018-10-04 09:48:39,265 INFO L375 BasicCegarLoop]: trace histogram [14, 13, 1, 1, 1] [2018-10-04 09:48:39,265 INFO L423 AbstractCegarLoop]: === Iteration 14 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-04 09:48:39,265 INFO L104 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-04 09:48:39,265 INFO L82 PathProgramCache]: Analyzing trace with hash -668453167, now seen corresponding path program 13 times [2018-10-04 09:48:39,265 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-04 09:48:39,266 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-04 09:48:39,266 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 09:48:39,266 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-04 09:48:39,267 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 09:48:39,278 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 09:48:39,587 INFO L134 CoverageAnalysis]: Checked inductivity of 182 backedges. 0 proven. 182 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 09:48:39,587 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-04 09:48:39,588 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/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-10-04 09:48:39,596 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-04 09:48:39,619 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 09:48:39,622 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-04 09:48:39,757 INFO L248 BPredicateUnifier]: --------PredicateTrie is restructured: old depths: 19 new depth: 14 [2018-10-04 09:48:39,938 INFO L134 CoverageAnalysis]: Checked inductivity of 182 backedges. 0 proven. 182 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 09:48:39,958 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-04 09:48:39,959 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 17] total 33 [2018-10-04 09:48:39,959 INFO L459 AbstractCegarLoop]: Interpolant automaton has 34 states [2018-10-04 09:48:39,959 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 34 interpolants. [2018-10-04 09:48:39,959 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-04 09:48:39,959 INFO L87 Difference]: Start difference. First operand 31 states and 31 transitions. Second operand 34 states. [2018-10-04 09:48:40,992 INFO L248 BPredicateUnifier]: --------PredicateTrie is restructured: old depths: 30 new depth: 15 [2018-10-04 09:48:41,357 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-04 09:48:41,358 INFO L93 Difference]: Finished difference Result 36 states and 36 transitions. [2018-10-04 09:48:41,358 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2018-10-04 09:48:41,358 INFO L78 Accepts]: Start accepts. Automaton has 34 states. Word has length 30 [2018-10-04 09:48:41,359 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-04 09:48:41,359 INFO L225 Difference]: With dead ends: 36 [2018-10-04 09:48:41,359 INFO L226 Difference]: Without dead ends: 34 [2018-10-04 09:48:41,360 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 58 GetRequests, 14 SyntacticMatches, 0 SemanticMatches, 44 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 1.0s Time 0.8s impTime 21 [2018-10-04 09:48:41,360 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 34 states. [2018-10-04 09:48:41,370 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 34 to 33. [2018-10-04 09:48:41,370 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 33 states. [2018-10-04 09:48:41,371 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 33 transitions. [2018-10-04 09:48:41,371 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 33 transitions. Word has length 30 [2018-10-04 09:48:41,371 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-04 09:48:41,372 INFO L480 AbstractCegarLoop]: Abstraction has 33 states and 33 transitions. [2018-10-04 09:48:41,372 INFO L481 AbstractCegarLoop]: Interpolant automaton has 34 states. [2018-10-04 09:48:41,372 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 33 transitions. [2018-10-04 09:48:41,373 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2018-10-04 09:48:41,373 INFO L367 BasicCegarLoop]: Found error trace [2018-10-04 09:48:41,373 INFO L375 BasicCegarLoop]: trace histogram [15, 14, 1, 1, 1] [2018-10-04 09:48:41,373 INFO L423 AbstractCegarLoop]: === Iteration 15 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-04 09:48:41,373 INFO L104 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-04 09:48:41,373 INFO L82 PathProgramCache]: Analyzing trace with hash 1861533901, now seen corresponding path program 14 times [2018-10-04 09:48:41,373 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-04 09:48:41,374 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-04 09:48:41,374 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 09:48:41,374 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-04 09:48:41,375 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 09:48:41,386 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 09:48:42,573 INFO L134 CoverageAnalysis]: Checked inductivity of 210 backedges. 0 proven. 210 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 09:48:42,573 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-04 09:48:42,573 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/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-10-04 09:48:42,583 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-10-04 09:48:42,605 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-10-04 09:48:42,605 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-04 09:48:42,608 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-04 09:48:42,808 INFO L248 BPredicateUnifier]: --------PredicateTrie is restructured: old depths: 19 new depth: 15 [2018-10-04 09:48:43,045 INFO L134 CoverageAnalysis]: Checked inductivity of 210 backedges. 0 proven. 210 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 09:48:43,066 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-10-04 09:48:43,066 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 18] total 35 [2018-10-04 09:48:43,066 INFO L459 AbstractCegarLoop]: Interpolant automaton has 36 states [2018-10-04 09:48:43,066 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 36 interpolants. [2018-10-04 09:48:43,066 INFO L146 InterpolantAutomaton]: No coverage relation statistics for ImplicationMap [2018-10-04 09:48:43,067 INFO L87 Difference]: Start difference. First operand 33 states and 33 transitions. Second operand 36 states. [2018-10-04 09:48:43,303 INFO L248 BPredicateUnifier]: --------PredicateTrie is restructured: old depths: 31 new depth: 16 [2018-10-04 09:48:43,978 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-04 09:48:43,978 INFO L93 Difference]: Finished difference Result 38 states and 38 transitions. [2018-10-04 09:48:43,978 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2018-10-04 09:48:43,979 INFO L78 Accepts]: Start accepts. Automaton has 36 states. Word has length 32 [2018-10-04 09:48:43,979 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-04 09:48:43,980 INFO L225 Difference]: With dead ends: 38 [2018-10-04 09:48:43,980 INFO L226 Difference]: Without dead ends: 36 [2018-10-04 09:48:43,980 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 62 GetRequests, 15 SyntacticMatches, 0 SemanticMatches, 47 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 1.7s Time 1.4s impTime 26 [2018-10-04 09:48:43,981 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 36 states. [2018-10-04 09:48:43,990 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 36 to 35. [2018-10-04 09:48:43,990 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 35 states. [2018-10-04 09:48:43,990 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 35 states to 35 states and 35 transitions. [2018-10-04 09:48:43,991 INFO L78 Accepts]: Start accepts. Automaton has 35 states and 35 transitions. Word has length 32 [2018-10-04 09:48:43,991 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-04 09:48:43,991 INFO L480 AbstractCegarLoop]: Abstraction has 35 states and 35 transitions. [2018-10-04 09:48:43,991 INFO L481 AbstractCegarLoop]: Interpolant automaton has 36 states. [2018-10-04 09:48:43,991 INFO L276 IsEmpty]: Start isEmpty. Operand 35 states and 35 transitions. [2018-10-04 09:48:43,992 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2018-10-04 09:48:43,992 INFO L367 BasicCegarLoop]: Found error trace [2018-10-04 09:48:43,992 INFO L375 BasicCegarLoop]: trace histogram [16, 15, 1, 1, 1] [2018-10-04 09:48:43,992 INFO L423 AbstractCegarLoop]: === Iteration 16 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-04 09:48:43,992 INFO L104 BPredicateUnifier]: Initialized predicate-trie based predicate unifier [2018-10-04 09:48:43,992 INFO L82 PathProgramCache]: Analyzing trace with hash -2067350583, now seen corresponding path program 15 times [2018-10-04 09:48:43,993 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-10-04 09:48:43,993 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-10-04 09:48:43,993 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 09:48:43,994 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-04 09:48:43,994 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-04 09:48:44,004 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-04 09:48:44,548 INFO L134 CoverageAnalysis]: Checked inductivity of 240 backedges. 0 proven. 240 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-04 09:48:44,548 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-04 09:48:44,548 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/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-10-04 09:48:44,556 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 Received shutdown request... [2018-10-04 09:50:05,956 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 16 check-sat command(s) [2018-10-04 09:50:05,956 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-04 09:50:06,012 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-04 09:50:06,039 INFO L177 TraceCheckSpWp]: Timeout while computing interpolants [2018-10-04 09:50:06,239 WARN L521 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-04 09:50:06,240 WARN L549 AbstractCegarLoop]: Verification canceled [2018-10-04 09:50:06,245 WARN L205 ceAbstractionStarter]: Timeout [2018-10-04 09:50:06,245 INFO L202 PluginConnector]: Adding new model jain_5.i_2.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 04.10 09:50:06 BoogieIcfgContainer [2018-10-04 09:50:06,246 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-10-04 09:50:06,247 INFO L168 Benchmark]: Toolchain (without parser) took 285606.66 ms. Allocated memory was 1.5 GB in the beginning and 1.5 GB in the end (delta: 5.8 MB). Free memory was 1.5 GB in the beginning and 970.1 MB in the end (delta: 500.8 MB). Peak memory consumption was 506.6 MB. Max. memory is 7.1 GB. [2018-10-04 09:50:06,249 INFO L168 Benchmark]: Boogie PL CUP Parser took 0.15 ms. Allocated memory is still 1.5 GB. Free memory is still 1.5 GB. There was no memory consumed. Max. memory is 7.1 GB. [2018-10-04 09:50:06,249 INFO L168 Benchmark]: Boogie Procedure Inliner took 39.65 ms. Allocated memory is still 1.5 GB. Free memory is still 1.5 GB. There was no memory consumed. Max. memory is 7.1 GB. [2018-10-04 09:50:06,250 INFO L168 Benchmark]: Boogie Preprocessor took 19.52 ms. Allocated memory is still 1.5 GB. Free memory is still 1.5 GB. There was no memory consumed. Max. memory is 7.1 GB. [2018-10-04 09:50:06,250 INFO L168 Benchmark]: RCFGBuilder took 247.58 ms. Allocated memory is still 1.5 GB. Free memory was 1.5 GB in the beginning and 1.4 GB in the end (delta: 21.1 MB). Peak memory consumption was 21.1 MB. Max. memory is 7.1 GB. [2018-10-04 09:50:06,251 INFO L168 Benchmark]: TraceAbstraction took 285295.84 ms. Allocated memory was 1.5 GB in the beginning and 1.5 GB in the end (delta: 5.8 MB). Free memory was 1.4 GB in the beginning and 970.1 MB in the end (delta: 479.7 MB). Peak memory consumption was 485.4 MB. Max. memory is 7.1 GB. [2018-10-04 09:50:06,255 INFO L336 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * Boogie PL CUP Parser took 0.15 ms. Allocated memory is still 1.5 GB. Free memory is still 1.5 GB. There was no memory consumed. Max. memory is 7.1 GB. * Boogie Procedure Inliner took 39.65 ms. Allocated memory is still 1.5 GB. Free memory is still 1.5 GB. There was no memory consumed. Max. memory is 7.1 GB. * Boogie Preprocessor took 19.52 ms. Allocated memory is still 1.5 GB. Free memory is still 1.5 GB. There was no memory consumed. Max. memory is 7.1 GB. * RCFGBuilder took 247.58 ms. Allocated memory is still 1.5 GB. Free memory was 1.5 GB in the beginning and 1.4 GB in the end (delta: 21.1 MB). Peak memory consumption was 21.1 MB. Max. memory is 7.1 GB. * TraceAbstraction took 285295.84 ms. Allocated memory was 1.5 GB in the beginning and 1.5 GB in the end (delta: 5.8 MB). Free memory was 1.4 GB in the beginning and 970.1 MB in the end (delta: 479.7 MB). Peak memory consumption was 485.4 MB. Max. memory is 7.1 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [Line: 35]: Timeout (TraceAbstraction) Unable to prove that assertion always holds (line 35). Cancelled while BasicCegarLoop was analyzing trace of length 35 with TraceHistMax 16, while TraceCheckSpWp was constructing forward predicates, while XnfDer was eliminating 2 quantified variables from 4 xjuncts. - StatisticsResult: Ultimate Automizer benchmark data CFG has 1 procedures, 7 locations, 1 error locations. TIMEOUT Result, 285.2s OverallTime, 16 OverallIterations, 16 TraceHistogramMax, 8.8s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 46 SDtfs, 187 SDslu, 434 SDs, 0 SdLazy, 4222 SolverSat, 187 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 5.1s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 507 GetRequests, 120 SyntacticMatches, 0 SemanticMatches, 387 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 11.0s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=35occurred in iteration=15, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s AbstIntTime, 0 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 0.1s AutomataMinimizationTime, 15 MinimizatonAttempts, 15 StatesRemovedByMinimization, 15 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 183.0s SatisfiabilityAnalysisTime, 10.1s InterpolantComputationTime, 536 NumberOfCodeBlocks, 536 NumberOfCodeBlocksAsserted, 80 NumberOfCheckSat, 507 ConstructedInterpolants, 0 QuantifiedInterpolants, 117489 SizeOfPredicates, 70 NumberOfNonLiveVariables, 1183 ConjunctsInSsa, 658 ConjunctsInUnsatCore, 29 InterpolantComputations, 1 PerfectInterpolantSequences, 0/2240 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/repos/ultimate/releaseScripts/default/UAutomizer-linux/csv/jain_5.i_2.bpl_svcomp-Reach-32bit-Automizer_Default_PUPT.epf_AutomizerBplInline.xml/Csv-Benchmark-0-2018-10-04_09-50-06-271.csv Written .csv to /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/csv/jain_5.i_2.bpl_svcomp-Reach-32bit-Automizer_Default_PUPT.epf_AutomizerBplInline.xml/Csv-TraceAbstractionBenchmarks-0-2018-10-04_09-50-06-271.csv Completed graceful shutdown