java -Xmx6000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data ./data --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -tc ../../../trunk/examples/toolchains/AutomizerC.xml -s ../../../trunk/examples/settings/ai/eq-bench/mempurity-32bit-Automizer_Camel+AI_EQ.epf -i ../../../trunk/examples/svcomp/forester-heap/dll-circular_true-unreach-call_true-valid-memsafety.i -------------------------------------------------------------------------------- This is Ultimate 0.1.23-2f49842 [2018-01-20 22:26:25,058 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-01-20 22:26:25,060 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-01-20 22:26:25,075 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-01-20 22:26:25,075 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-01-20 22:26:25,076 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-01-20 22:26:25,077 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-01-20 22:26:25,079 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-01-20 22:26:25,081 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-01-20 22:26:25,082 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-01-20 22:26:25,082 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-01-20 22:26:25,082 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-01-20 22:26:25,083 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-01-20 22:26:25,084 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-01-20 22:26:25,085 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-01-20 22:26:25,088 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-01-20 22:26:25,090 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-01-20 22:26:25,093 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-01-20 22:26:25,094 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-01-20 22:26:25,095 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-01-20 22:26:25,098 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-01-20 22:26:25,098 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-01-20 22:26:25,098 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-01-20 22:26:25,100 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-01-20 22:26:25,100 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-01-20 22:26:25,102 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-01-20 22:26:25,102 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-01-20 22:26:25,103 INFO L177 SettingsManager]: PEA to Boogie provides no preferences, ignoring... [2018-01-20 22:26:25,103 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-01-20 22:26:25,103 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-01-20 22:26:25,104 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-01-20 22:26:25,104 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/ai/eq-bench/mempurity-32bit-Automizer_Camel+AI_EQ.epf [2018-01-20 22:26:25,115 INFO L110 SettingsManager]: Loading preferences was successful [2018-01-20 22:26:25,115 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-01-20 22:26:25,116 INFO L131 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2018-01-20 22:26:25,116 INFO L133 SettingsManager]: * to procedures, called more than once=true [2018-01-20 22:26:25,116 INFO L131 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2018-01-20 22:26:25,116 INFO L133 SettingsManager]: * Abstract domain for RCFG-of-the-future=VPDomain [2018-01-20 22:26:25,117 INFO L133 SettingsManager]: * Use the RCFG-of-the-future interface=true [2018-01-20 22:26:25,117 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-01-20 22:26:25,118 INFO L133 SettingsManager]: * sizeof long=4 [2018-01-20 22:26:25,118 INFO L133 SettingsManager]: * Check unreachability of error function in SV-COMP mode=false [2018-01-20 22:26:25,118 INFO L133 SettingsManager]: * Check allocation purity=true [2018-01-20 22:26:25,118 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-01-20 22:26:25,118 INFO L133 SettingsManager]: * sizeof POINTER=4 [2018-01-20 22:26:25,119 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-01-20 22:26:25,119 INFO L133 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2018-01-20 22:26:25,119 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-01-20 22:26:25,119 INFO L133 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2018-01-20 22:26:25,119 INFO L133 SettingsManager]: * sizeof long double=12 [2018-01-20 22:26:25,119 INFO L133 SettingsManager]: * Check if freed pointer was valid=false [2018-01-20 22:26:25,120 INFO L133 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2018-01-20 22:26:25,120 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-01-20 22:26:25,120 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-01-20 22:26:25,120 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-01-20 22:26:25,120 INFO L133 SettingsManager]: * Add additional assume for each assert=false [2018-01-20 22:26:25,121 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-01-20 22:26:25,121 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-01-20 22:26:25,121 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-01-20 22:26:25,121 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-01-20 22:26:25,121 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-01-20 22:26:25,122 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-01-20 22:26:25,122 INFO L133 SettingsManager]: * Stop after first violation was found=false [2018-01-20 22:26:25,122 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-01-20 22:26:25,122 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-01-20 22:26:25,122 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-01-20 22:26:25,122 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-01-20 22:26:25,123 INFO L131 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2018-01-20 22:26:25,124 INFO L133 SettingsManager]: * TransformationType=HEAP_SEPARATOR [2018-01-20 22:26:25,160 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-01-20 22:26:25,171 INFO L266 ainManager$Toolchain]: [Toolchain 1]: Parser(s) successfully initialized [2018-01-20 22:26:25,174 INFO L222 ainManager$Toolchain]: [Toolchain 1]: Toolchain data selected. [2018-01-20 22:26:25,175 INFO L271 PluginConnector]: Initializing CDTParser... [2018-01-20 22:26:25,176 INFO L276 PluginConnector]: CDTParser initialized [2018-01-20 22:26:25,176 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/forester-heap/dll-circular_true-unreach-call_true-valid-memsafety.i [2018-01-20 22:26:25,334 INFO L304 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-01-20 22:26:25,339 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2018-01-20 22:26:25,340 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2018-01-20 22:26:25,340 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2018-01-20 22:26:25,346 INFO L276 PluginConnector]: CACSL2BoogieTranslator initialized [2018-01-20 22:26:25,347 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.01 10:26:25" (1/1) ... [2018-01-20 22:26:25,350 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@2eeba7ea and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 10:26:25, skipping insertion in model container [2018-01-20 22:26:25,350 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.01 10:26:25" (1/1) ... [2018-01-20 22:26:25,370 INFO L153 Dispatcher]: Using SV-COMP mode [2018-01-20 22:26:25,411 INFO L153 Dispatcher]: Using SV-COMP mode [2018-01-20 22:26:25,535 INFO L450 PostProcessor]: Settings: Checked method=main [2018-01-20 22:26:25,552 INFO L450 PostProcessor]: Settings: Checked method=main [2018-01-20 22:26:25,560 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 10:26:25 WrapperNode [2018-01-20 22:26:25,560 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2018-01-20 22:26:25,561 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-01-20 22:26:25,561 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-01-20 22:26:25,561 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-01-20 22:26:25,578 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 10:26:25" (1/1) ... [2018-01-20 22:26:25,578 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 10:26:25" (1/1) ... [2018-01-20 22:26:25,589 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 10:26:25" (1/1) ... [2018-01-20 22:26:25,589 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 10:26:25" (1/1) ... [2018-01-20 22:26:25,594 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 10:26:25" (1/1) ... [2018-01-20 22:26:25,597 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 10:26:25" (1/1) ... [2018-01-20 22:26:25,599 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 10:26:25" (1/1) ... [2018-01-20 22:26:25,601 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-01-20 22:26:25,601 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-01-20 22:26:25,601 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-01-20 22:26:25,601 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-01-20 22:26:25,602 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 10:26:25" (1/1) ... No working directory specified, using /storage/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-01-20 22:26:25,650 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2018-01-20 22:26:25,650 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-01-20 22:26:25,650 INFO L136 BoogieDeclarations]: Found implementation of procedure main [2018-01-20 22:26:25,650 INFO L128 BoogieDeclarations]: Found specification of procedure write~$Pointer$ [2018-01-20 22:26:25,650 INFO L128 BoogieDeclarations]: Found specification of procedure read~$Pointer$ [2018-01-20 22:26:25,650 INFO L128 BoogieDeclarations]: Found specification of procedure write~int [2018-01-20 22:26:25,650 INFO L128 BoogieDeclarations]: Found specification of procedure read~int [2018-01-20 22:26:25,650 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.free [2018-01-20 22:26:25,651 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2018-01-20 22:26:25,651 INFO L128 BoogieDeclarations]: Found specification of procedure #Ultimate.alloc [2018-01-20 22:26:25,651 INFO L128 BoogieDeclarations]: Found specification of procedure malloc [2018-01-20 22:26:25,651 INFO L128 BoogieDeclarations]: Found specification of procedure free [2018-01-20 22:26:25,651 INFO L128 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2018-01-20 22:26:25,651 INFO L128 BoogieDeclarations]: Found specification of procedure __VERIFIER_error [2018-01-20 22:26:25,651 INFO L128 BoogieDeclarations]: Found specification of procedure main [2018-01-20 22:26:25,651 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2018-01-20 22:26:25,652 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-01-20 22:26:25,955 INFO L257 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-01-20 22:26:25,955 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.01 10:26:25 BoogieIcfgContainer [2018-01-20 22:26:25,993 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-01-20 22:26:25,994 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-01-20 22:26:25,994 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-01-20 22:26:25,996 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-01-20 22:26:25,997 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 20.01 10:26:25" (1/3) ... [2018-01-20 22:26:25,998 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@307d8325 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.01 10:26:25, skipping insertion in model container [2018-01-20 22:26:25,998 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 10:26:25" (2/3) ... [2018-01-20 22:26:25,999 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@307d8325 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.01 10:26:25, skipping insertion in model container [2018-01-20 22:26:25,999 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.01 10:26:25" (3/3) ... [2018-01-20 22:26:26,000 INFO L105 eAbstractionObserver]: Analyzing ICFG dll-circular_true-unreach-call_true-valid-memsafety.i [2018-01-20 22:26:26,007 INFO L130 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-01-20 22:26:26,014 INFO L142 ceAbstractionStarter]: Appying trace abstraction to program that has 3 error locations. [2018-01-20 22:26:26,052 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-20 22:26:26,052 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-20 22:26:26,052 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-20 22:26:26,052 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-20 22:26:26,052 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-20 22:26:26,052 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-20 22:26:26,053 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-20 22:26:26,053 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == ULTIMATE.initErr0EnsuresViolation======== [2018-01-20 22:26:26,053 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-20 22:26:26,069 INFO L276 IsEmpty]: Start isEmpty. Operand 69 states. [2018-01-20 22:26:26,075 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 4 [2018-01-20 22:26:26,075 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:26:26,076 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1] [2018-01-20 22:26:26,076 INFO L371 AbstractCegarLoop]: === Iteration 1 === [ULTIMATE.initErr0EnsuresViolation]=== [2018-01-20 22:26:26,080 INFO L82 PathProgramCache]: Analyzing trace with hash 190435, now seen corresponding path program 1 times [2018-01-20 22:26:26,082 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:26:26,082 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:26:26,125 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:26,125 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:26:26,125 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:26,157 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2018-01-20 22:26:26,165 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2018-01-20 22:26:26,186 INFO L381 BasicCegarLoop]: Counterexample might be feasible [2018-01-20 22:26:26,194 WARN L343 cessorBacktranslator]: Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) [2018-01-20 22:26:26,202 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-20 22:26:26,202 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-20 22:26:26,202 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-20 22:26:26,202 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-20 22:26:26,203 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-20 22:26:26,203 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-20 22:26:26,203 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-20 22:26:26,203 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == ULTIMATE.startErr0EnsuresViolation======== [2018-01-20 22:26:26,203 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-20 22:26:26,206 INFO L276 IsEmpty]: Start isEmpty. Operand 69 states. [2018-01-20 22:26:26,208 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2018-01-20 22:26:26,208 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:26:26,209 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 22:26:26,209 INFO L371 AbstractCegarLoop]: === Iteration 1 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-20 22:26:26,209 INFO L82 PathProgramCache]: Analyzing trace with hash 1526713431, now seen corresponding path program 1 times [2018-01-20 22:26:26,209 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:26:26,209 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:26:26,210 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:26,211 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:26:26,211 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:26,243 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:26:26,253 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:26:26,301 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 22:26:26,304 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-20 22:26:26,304 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-01-20 22:26:26,306 INFO L409 AbstractCegarLoop]: Interpolant automaton has 2 states [2018-01-20 22:26:26,402 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2018-01-20 22:26:26,403 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-01-20 22:26:26,406 INFO L87 Difference]: Start difference. First operand 69 states. Second operand 2 states. [2018-01-20 22:26:26,434 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:26:26,434 INFO L93 Difference]: Finished difference Result 126 states and 162 transitions. [2018-01-20 22:26:26,434 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2018-01-20 22:26:26,435 INFO L78 Accepts]: Start accepts. Automaton has 2 states. Word has length 25 [2018-01-20 22:26:26,436 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:26:26,446 INFO L225 Difference]: With dead ends: 126 [2018-01-20 22:26:26,446 INFO L226 Difference]: Without dead ends: 66 [2018-01-20 22:26:26,449 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-01-20 22:26:26,462 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 66 states. [2018-01-20 22:26:26,478 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 66 to 66. [2018-01-20 22:26:26,479 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 66 states. [2018-01-20 22:26:26,481 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 66 states to 66 states and 72 transitions. [2018-01-20 22:26:26,483 INFO L78 Accepts]: Start accepts. Automaton has 66 states and 72 transitions. Word has length 25 [2018-01-20 22:26:26,483 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:26:26,483 INFO L432 AbstractCegarLoop]: Abstraction has 66 states and 72 transitions. [2018-01-20 22:26:26,483 INFO L433 AbstractCegarLoop]: Interpolant automaton has 2 states. [2018-01-20 22:26:26,483 INFO L276 IsEmpty]: Start isEmpty. Operand 66 states and 72 transitions. [2018-01-20 22:26:26,485 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2018-01-20 22:26:26,485 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:26:26,485 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 22:26:26,485 INFO L371 AbstractCegarLoop]: === Iteration 2 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-20 22:26:26,486 INFO L82 PathProgramCache]: Analyzing trace with hash -97713131, now seen corresponding path program 1 times [2018-01-20 22:26:26,486 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:26:26,486 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:26:26,487 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:26,487 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:26:26,487 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:26,528 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:26:26,529 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:26:27,130 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 22:26:27,130 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-20 22:26:27,130 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [10] imperfect sequences [] total 10 [2018-01-20 22:26:27,132 INFO L409 AbstractCegarLoop]: Interpolant automaton has 10 states [2018-01-20 22:26:27,132 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2018-01-20 22:26:27,133 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=24, Invalid=66, Unknown=0, NotChecked=0, Total=90 [2018-01-20 22:26:27,133 INFO L87 Difference]: Start difference. First operand 66 states and 72 transitions. Second operand 10 states. [2018-01-20 22:26:27,658 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:26:27,658 INFO L93 Difference]: Finished difference Result 132 states and 144 transitions. [2018-01-20 22:26:27,658 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-01-20 22:26:27,658 INFO L78 Accepts]: Start accepts. Automaton has 10 states. Word has length 33 [2018-01-20 22:26:27,659 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:26:27,662 INFO L225 Difference]: With dead ends: 132 [2018-01-20 22:26:27,662 INFO L226 Difference]: Without dead ends: 118 [2018-01-20 22:26:27,663 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 22 GetRequests, 2 SyntacticMatches, 4 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 20 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=100, Invalid=206, Unknown=0, NotChecked=0, Total=306 [2018-01-20 22:26:27,663 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 118 states. [2018-01-20 22:26:27,671 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 118 to 78. [2018-01-20 22:26:27,671 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 78 states. [2018-01-20 22:26:27,672 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 78 states to 78 states and 85 transitions. [2018-01-20 22:26:27,672 INFO L78 Accepts]: Start accepts. Automaton has 78 states and 85 transitions. Word has length 33 [2018-01-20 22:26:27,673 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:26:27,673 INFO L432 AbstractCegarLoop]: Abstraction has 78 states and 85 transitions. [2018-01-20 22:26:27,673 INFO L433 AbstractCegarLoop]: Interpolant automaton has 10 states. [2018-01-20 22:26:27,673 INFO L276 IsEmpty]: Start isEmpty. Operand 78 states and 85 transitions. [2018-01-20 22:26:27,674 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2018-01-20 22:26:27,674 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:26:27,674 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 22:26:27,674 INFO L371 AbstractCegarLoop]: === Iteration 3 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-20 22:26:27,675 INFO L82 PathProgramCache]: Analyzing trace with hash 1309040711, now seen corresponding path program 1 times [2018-01-20 22:26:27,675 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:26:27,675 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:26:27,676 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:27,677 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:26:27,677 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:27,694 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:26:27,695 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:26:27,743 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 22:26:27,743 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-20 22:26:27,743 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-01-20 22:26:27,744 INFO L409 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-01-20 22:26:27,744 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-01-20 22:26:27,744 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-20 22:26:27,744 INFO L87 Difference]: Start difference. First operand 78 states and 85 transitions. Second operand 3 states. [2018-01-20 22:26:27,781 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:26:27,781 INFO L93 Difference]: Finished difference Result 185 states and 204 transitions. [2018-01-20 22:26:27,782 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-01-20 22:26:27,782 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 45 [2018-01-20 22:26:27,783 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:26:27,786 INFO L225 Difference]: With dead ends: 185 [2018-01-20 22:26:27,786 INFO L226 Difference]: Without dead ends: 130 [2018-01-20 22:26:27,787 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-20 22:26:27,787 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 130 states. [2018-01-20 22:26:27,798 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 130 to 96. [2018-01-20 22:26:27,799 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 96 states. [2018-01-20 22:26:27,800 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 96 states to 96 states and 105 transitions. [2018-01-20 22:26:27,801 INFO L78 Accepts]: Start accepts. Automaton has 96 states and 105 transitions. Word has length 45 [2018-01-20 22:26:27,801 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:26:27,801 INFO L432 AbstractCegarLoop]: Abstraction has 96 states and 105 transitions. [2018-01-20 22:26:27,801 INFO L433 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-01-20 22:26:27,801 INFO L276 IsEmpty]: Start isEmpty. Operand 96 states and 105 transitions. [2018-01-20 22:26:27,803 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2018-01-20 22:26:27,803 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:26:27,803 INFO L322 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 22:26:27,803 INFO L371 AbstractCegarLoop]: === Iteration 4 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-20 22:26:27,803 INFO L82 PathProgramCache]: Analyzing trace with hash -403724794, now seen corresponding path program 1 times [2018-01-20 22:26:27,804 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:26:27,804 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:26:27,805 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:27,805 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:26:27,805 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:27,823 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:26:27,824 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:26:28,402 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 3 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 22:26:28,402 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-20 22:26:28,402 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [13] imperfect sequences [] total 13 [2018-01-20 22:26:28,403 INFO L409 AbstractCegarLoop]: Interpolant automaton has 13 states [2018-01-20 22:26:28,403 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2018-01-20 22:26:28,403 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=42, Invalid=114, Unknown=0, NotChecked=0, Total=156 [2018-01-20 22:26:28,403 INFO L87 Difference]: Start difference. First operand 96 states and 105 transitions. Second operand 13 states. [2018-01-20 22:26:28,763 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:26:28,763 INFO L93 Difference]: Finished difference Result 166 states and 181 transitions. [2018-01-20 22:26:28,763 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-01-20 22:26:28,763 INFO L78 Accepts]: Start accepts. Automaton has 13 states. Word has length 45 [2018-01-20 22:26:28,764 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:26:28,766 INFO L225 Difference]: With dead ends: 166 [2018-01-20 22:26:28,766 INFO L226 Difference]: Without dead ends: 136 [2018-01-20 22:26:28,767 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 28 GetRequests, 2 SyntacticMatches, 6 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 33 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=139, Invalid=323, Unknown=0, NotChecked=0, Total=462 [2018-01-20 22:26:28,767 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 136 states. [2018-01-20 22:26:28,776 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 136 to 101. [2018-01-20 22:26:28,776 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 101 states. [2018-01-20 22:26:28,777 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 101 states to 101 states and 110 transitions. [2018-01-20 22:26:28,778 INFO L78 Accepts]: Start accepts. Automaton has 101 states and 110 transitions. Word has length 45 [2018-01-20 22:26:28,778 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:26:28,778 INFO L432 AbstractCegarLoop]: Abstraction has 101 states and 110 transitions. [2018-01-20 22:26:28,778 INFO L433 AbstractCegarLoop]: Interpolant automaton has 13 states. [2018-01-20 22:26:28,778 INFO L276 IsEmpty]: Start isEmpty. Operand 101 states and 110 transitions. [2018-01-20 22:26:28,780 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 50 [2018-01-20 22:26:28,780 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:26:28,780 INFO L322 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 22:26:28,780 INFO L371 AbstractCegarLoop]: === Iteration 5 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-20 22:26:28,781 INFO L82 PathProgramCache]: Analyzing trace with hash 804308226, now seen corresponding path program 1 times [2018-01-20 22:26:28,781 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:26:28,781 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:26:28,782 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:28,782 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:26:28,782 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:28,801 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:26:28,802 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:26:29,142 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 22:26:29,143 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-20 22:26:29,143 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/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-01-20 22:26:29,150 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:26:29,188 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:26:29,194 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-20 22:26:29,314 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 26 treesize of output 22 [2018-01-20 22:26:29,317 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 14 [2018-01-20 22:26:29,318 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:29,323 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:29,328 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 18 [2018-01-20 22:26:29,331 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 10 [2018-01-20 22:26:29,331 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:29,333 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:29,335 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 2 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:29,335 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 4 variables, input treesize:33, output treesize:10 [2018-01-20 22:26:29,388 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 20 treesize of output 16 [2018-01-20 22:26:29,402 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 4 [2018-01-20 22:26:29,403 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:29,404 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:29,409 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:29,410 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:20, output treesize:4 [2018-01-20 22:26:29,454 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 22:26:29,488 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-20 22:26:29,488 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 9] total 22 [2018-01-20 22:26:29,489 INFO L409 AbstractCegarLoop]: Interpolant automaton has 22 states [2018-01-20 22:26:29,489 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2018-01-20 22:26:29,489 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=58, Invalid=404, Unknown=0, NotChecked=0, Total=462 [2018-01-20 22:26:29,489 INFO L87 Difference]: Start difference. First operand 101 states and 110 transitions. Second operand 22 states. [2018-01-20 22:26:30,264 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:26:30,264 INFO L93 Difference]: Finished difference Result 161 states and 175 transitions. [2018-01-20 22:26:30,265 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2018-01-20 22:26:30,265 INFO L78 Accepts]: Start accepts. Automaton has 22 states. Word has length 49 [2018-01-20 22:26:30,265 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:26:30,267 INFO L225 Difference]: With dead ends: 161 [2018-01-20 22:26:30,267 INFO L226 Difference]: Without dead ends: 155 [2018-01-20 22:26:30,268 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 89 GetRequests, 45 SyntacticMatches, 4 SemanticMatches, 40 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 364 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=267, Invalid=1455, Unknown=0, NotChecked=0, Total=1722 [2018-01-20 22:26:30,269 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 155 states. [2018-01-20 22:26:30,279 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 155 to 109. [2018-01-20 22:26:30,279 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 109 states. [2018-01-20 22:26:30,280 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 109 states to 109 states and 119 transitions. [2018-01-20 22:26:30,281 INFO L78 Accepts]: Start accepts. Automaton has 109 states and 119 transitions. Word has length 49 [2018-01-20 22:26:30,281 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:26:30,281 INFO L432 AbstractCegarLoop]: Abstraction has 109 states and 119 transitions. [2018-01-20 22:26:30,281 INFO L433 AbstractCegarLoop]: Interpolant automaton has 22 states. [2018-01-20 22:26:30,281 INFO L276 IsEmpty]: Start isEmpty. Operand 109 states and 119 transitions. [2018-01-20 22:26:30,283 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2018-01-20 22:26:30,283 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:26:30,283 INFO L322 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 22:26:30,283 INFO L371 AbstractCegarLoop]: === Iteration 6 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-20 22:26:30,284 INFO L82 PathProgramCache]: Analyzing trace with hash -2111307373, now seen corresponding path program 1 times [2018-01-20 22:26:30,284 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:26:30,284 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:26:30,285 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:30,285 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:26:30,285 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:30,304 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:26:30,305 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:26:31,308 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 22:26:31,308 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-20 22:26:31,308 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-20 22:26:31,317 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:26:31,336 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:26:31,340 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-20 22:26:31,343 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-20 22:26:31,343 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:31,344 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:31,344 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:6, output treesize:5 [2018-01-20 22:26:31,430 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:31,430 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:31,431 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 4 [2018-01-20 22:26:31,432 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:31,438 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:31,438 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:23, output treesize:17 [2018-01-20 22:26:31,489 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 8 [2018-01-20 22:26:31,492 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-01-20 22:26:31,492 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:31,494 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:31,504 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 8 [2018-01-20 22:26:31,506 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-01-20 22:26:31,506 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:31,508 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:31,517 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 2 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:31,517 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 3 variables, input treesize:36, output treesize:25 [2018-01-20 22:26:31,615 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:31,618 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 51 treesize of output 55 [2018-01-20 22:26:31,621 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 13 [2018-01-20 22:26:31,622 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:31,628 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:31,639 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:31,642 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 30 [2018-01-20 22:26:31,646 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 13 [2018-01-20 22:26:31,647 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:31,652 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:31,662 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 2 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-20 22:26:31,662 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 3 variables, input treesize:67, output treesize:51 [2018-01-20 22:26:31,749 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 28 treesize of output 26 [2018-01-20 22:26:31,753 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 1 [2018-01-20 22:26:31,753 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:31,761 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 3 [2018-01-20 22:26:31,761 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:31,764 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:31,780 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-20 22:26:31,780 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 2 variables, input treesize:59, output treesize:35 [2018-01-20 22:26:31,917 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 40 treesize of output 35 [2018-01-20 22:26:31,922 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 17 [2018-01-20 22:26:31,922 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:31,932 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:31,950 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-20 22:26:31,951 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:46, output treesize:34 [2018-01-20 22:26:32,008 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 34 treesize of output 33 [2018-01-20 22:26:32,010 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:32,012 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 14 [2018-01-20 22:26:32,012 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:32,016 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:32,021 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:32,021 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:44, output treesize:25 [2018-01-20 22:26:32,027 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 12 [2018-01-20 22:26:32,029 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 11 [2018-01-20 22:26:32,030 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:32,031 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:32,041 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 58 treesize of output 48 [2018-01-20 22:26:32,044 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 26 treesize of output 11 [2018-01-20 22:26:32,045 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:32,058 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:32,062 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:32,062 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 2 variables, input treesize:66, output treesize:31 [2018-01-20 22:26:32,134 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 38 treesize of output 26 [2018-01-20 22:26:32,137 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 21 treesize of output 12 [2018-01-20 22:26:32,137 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:32,141 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 1 [2018-01-20 22:26:32,142 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:32,144 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:32,147 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:32,147 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 3 variables, input treesize:38, output treesize:7 [2018-01-20 22:26:32,201 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 13 [2018-01-20 22:26:32,207 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 1 case distinctions, treesize of input 13 treesize of output 10 [2018-01-20 22:26:32,207 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-20 22:26:32,209 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-20 22:26:32,211 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 2 xjuncts. [2018-01-20 22:26:32,211 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:17, output treesize:10 [2018-01-20 22:26:32,276 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 22:26:32,296 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-20 22:26:32,297 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 18] total 35 [2018-01-20 22:26:32,297 INFO L409 AbstractCegarLoop]: Interpolant automaton has 35 states [2018-01-20 22:26:32,297 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 35 interpolants. [2018-01-20 22:26:32,298 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=100, Invalid=1090, Unknown=0, NotChecked=0, Total=1190 [2018-01-20 22:26:32,298 INFO L87 Difference]: Start difference. First operand 109 states and 119 transitions. Second operand 35 states. [2018-01-20 22:26:35,504 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:26:35,504 INFO L93 Difference]: Finished difference Result 276 states and 301 transitions. [2018-01-20 22:26:35,504 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 37 states. [2018-01-20 22:26:35,504 INFO L78 Accepts]: Start accepts. Automaton has 35 states. Word has length 50 [2018-01-20 22:26:35,505 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:26:35,506 INFO L225 Difference]: With dead ends: 276 [2018-01-20 22:26:35,506 INFO L226 Difference]: Without dead ends: 267 [2018-01-20 22:26:35,508 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 102 GetRequests, 35 SyntacticMatches, 2 SemanticMatches, 65 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 887 ImplicationChecksByTransitivity, 3.6s TimeCoverageRelationStatistics Valid=599, Invalid=3823, Unknown=0, NotChecked=0, Total=4422 [2018-01-20 22:26:35,508 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 267 states. [2018-01-20 22:26:35,521 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 267 to 140. [2018-01-20 22:26:35,521 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 140 states. [2018-01-20 22:26:35,522 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 140 states to 140 states and 153 transitions. [2018-01-20 22:26:35,522 INFO L78 Accepts]: Start accepts. Automaton has 140 states and 153 transitions. Word has length 50 [2018-01-20 22:26:35,522 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:26:35,523 INFO L432 AbstractCegarLoop]: Abstraction has 140 states and 153 transitions. [2018-01-20 22:26:35,523 INFO L433 AbstractCegarLoop]: Interpolant automaton has 35 states. [2018-01-20 22:26:35,523 INFO L276 IsEmpty]: Start isEmpty. Operand 140 states and 153 transitions. [2018-01-20 22:26:35,524 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2018-01-20 22:26:35,524 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:26:35,524 INFO L322 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 22:26:35,525 INFO L371 AbstractCegarLoop]: === Iteration 7 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-20 22:26:35,525 INFO L82 PathProgramCache]: Analyzing trace with hash -2105096794, now seen corresponding path program 1 times [2018-01-20 22:26:35,525 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:26:35,525 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:26:35,526 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:35,526 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:26:35,526 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:35,538 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:26:35,539 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:26:35,909 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-01-20 22:26:35,909 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-20 22:26:35,910 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-20 22:26:35,915 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:26:35,933 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:26:35,938 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-20 22:26:36,119 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 38 treesize of output 34 [2018-01-20 22:26:36,121 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 4 [2018-01-20 22:26:36,121 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:36,127 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:36,145 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 38 treesize of output 36 [2018-01-20 22:26:36,147 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 1 [2018-01-20 22:26:36,148 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:36,155 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:36,171 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 2 dim-2 vars, End of recursive call: 2 dim-0 vars, and 2 xjuncts. [2018-01-20 22:26:36,172 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 4 variables, input treesize:77, output treesize:59 [2018-01-20 22:26:36,184 WARN L1029 $PredicateComparison]: unable to prove that (or (exists ((v_prenex_2 Int)) (let ((.cse0 (select (select |c_#memory_$Pointer$.base| v_prenex_2) 0))) (and (not (= 0 .cse0)) (not (= 0 v_prenex_2)) (= |c_main_#t~mem23.base| .cse0) (= |c_#valid| (store |c_old(#valid)| v_prenex_2 1)) (= 0 (select |c_old(#valid)| v_prenex_2))))) (and (exists ((main_~head~5.base Int)) (and (not (= 0 main_~head~5.base)) (= |c_main_#t~mem23.base| (select (select |c_#memory_$Pointer$.base| main_~head~5.base) 0)) (= |c_#valid| (store |c_old(#valid)| main_~head~5.base 1)) (= 0 (select |c_old(#valid)| main_~head~5.base)))) (not (= |c_main_#t~mem23.offset| 0)))) is different from true [2018-01-20 22:26:36,191 WARN L1029 $PredicateComparison]: unable to prove that (or (and (not (= c_main_~x~5.offset 0)) (exists ((main_~head~5.base Int)) (and (= (select (select |c_#memory_$Pointer$.base| main_~head~5.base) 0) c_main_~x~5.base) (not (= 0 main_~head~5.base)) (= |c_#valid| (store |c_old(#valid)| main_~head~5.base 1)) (= 0 (select |c_old(#valid)| main_~head~5.base))))) (exists ((v_prenex_2 Int)) (let ((.cse0 (select (select |c_#memory_$Pointer$.base| v_prenex_2) 0))) (and (not (= 0 .cse0)) (not (= 0 v_prenex_2)) (= |c_#valid| (store |c_old(#valid)| v_prenex_2 1)) (= .cse0 c_main_~x~5.base) (= 0 (select |c_old(#valid)| v_prenex_2)))))) is different from true [2018-01-20 22:26:36,437 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 38 treesize of output 40 [2018-01-20 22:26:36,440 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 36 treesize of output 29 [2018-01-20 22:26:36,441 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:36,526 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 24 [2018-01-20 22:26:36,527 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:36,547 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 1 case distinctions, treesize of input 32 treesize of output 28 [2018-01-20 22:26:36,547 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 2 xjuncts. [2018-01-20 22:26:36,569 INFO L267 ElimStorePlain]: Start of recursive call 2: 3 dim-1 vars, End of recursive call: and 3 xjuncts. [2018-01-20 22:26:36,605 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 34 treesize of output 38 [2018-01-20 22:26:36,608 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 34 treesize of output 29 [2018-01-20 22:26:36,608 INFO L267 ElimStorePlain]: Start of recursive call 7: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:36,625 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 24 [2018-01-20 22:26:36,625 INFO L267 ElimStorePlain]: Start of recursive call 8: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:36,641 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 30 treesize of output 20 [2018-01-20 22:26:36,642 INFO L267 ElimStorePlain]: Start of recursive call 9: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:36,652 INFO L267 ElimStorePlain]: Start of recursive call 6: 3 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:36,679 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 2 dim-2 vars, End of recursive call: 4 dim-0 vars, and 4 xjuncts. [2018-01-20 22:26:36,679 INFO L202 ElimStorePlain]: Needed 9 recursive calls to eliminate 4 variables, input treesize:73, output treesize:92 [2018-01-20 22:26:36,996 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 3 not checked. [2018-01-20 22:26:37,017 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-20 22:26:37,017 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 17] total 31 [2018-01-20 22:26:37,018 INFO L409 AbstractCegarLoop]: Interpolant automaton has 31 states [2018-01-20 22:26:37,018 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 31 interpolants. [2018-01-20 22:26:37,018 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=81, Invalid=732, Unknown=7, NotChecked=110, Total=930 [2018-01-20 22:26:37,018 INFO L87 Difference]: Start difference. First operand 140 states and 153 transitions. Second operand 31 states. [2018-01-20 22:26:38,634 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:26:38,634 INFO L93 Difference]: Finished difference Result 183 states and 198 transitions. [2018-01-20 22:26:38,635 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2018-01-20 22:26:38,635 INFO L78 Accepts]: Start accepts. Automaton has 31 states. Word has length 55 [2018-01-20 22:26:38,635 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:26:38,636 INFO L225 Difference]: With dead ends: 183 [2018-01-20 22:26:38,636 INFO L226 Difference]: Without dead ends: 177 [2018-01-20 22:26:38,638 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 91 GetRequests, 39 SyntacticMatches, 4 SemanticMatches, 48 ConstructedPredicates, 2 IntricatePredicates, 0 DeprecatedPredicates, 409 ImplicationChecksByTransitivity, 1.8s TimeCoverageRelationStatistics Valid=331, Invalid=1908, Unknown=25, NotChecked=186, Total=2450 [2018-01-20 22:26:38,640 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 177 states. [2018-01-20 22:26:38,664 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 177 to 164. [2018-01-20 22:26:38,664 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 164 states. [2018-01-20 22:26:38,665 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 164 states to 164 states and 179 transitions. [2018-01-20 22:26:38,666 INFO L78 Accepts]: Start accepts. Automaton has 164 states and 179 transitions. Word has length 55 [2018-01-20 22:26:38,666 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:26:38,666 INFO L432 AbstractCegarLoop]: Abstraction has 164 states and 179 transitions. [2018-01-20 22:26:38,666 INFO L433 AbstractCegarLoop]: Interpolant automaton has 31 states. [2018-01-20 22:26:38,666 INFO L276 IsEmpty]: Start isEmpty. Operand 164 states and 179 transitions. [2018-01-20 22:26:38,668 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2018-01-20 22:26:38,668 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:26:38,668 INFO L322 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 22:26:38,668 INFO L371 AbstractCegarLoop]: === Iteration 8 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-20 22:26:38,668 INFO L82 PathProgramCache]: Analyzing trace with hash -70741641, now seen corresponding path program 1 times [2018-01-20 22:26:38,668 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:26:38,669 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:26:38,669 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:38,670 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:26:38,670 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:38,686 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:26:38,687 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:26:39,214 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 3 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 22:26:39,215 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-20 22:26:39,215 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-20 22:26:39,221 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:26:39,242 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:26:39,247 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-20 22:26:39,250 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-20 22:26:39,251 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:39,265 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:39,265 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:6, output treesize:5 [2018-01-20 22:26:39,398 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:39,399 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:39,399 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 4 [2018-01-20 22:26:39,399 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:39,404 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:39,404 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:23, output treesize:17 [2018-01-20 22:26:39,426 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 8 [2018-01-20 22:26:39,427 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-01-20 22:26:39,428 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:39,429 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:39,437 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 8 [2018-01-20 22:26:39,439 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-01-20 22:26:39,439 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:39,440 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:39,446 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 2 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:39,446 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 3 variables, input treesize:36, output treesize:25 [2018-01-20 22:26:39,494 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:39,498 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 51 treesize of output 55 [2018-01-20 22:26:39,500 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 13 [2018-01-20 22:26:39,500 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:39,505 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:39,516 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:39,518 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 30 [2018-01-20 22:26:39,520 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 13 [2018-01-20 22:26:39,521 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:39,525 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:39,532 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 2 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-20 22:26:39,533 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 3 variables, input treesize:67, output treesize:51 [2018-01-20 22:26:39,636 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 53 treesize of output 44 [2018-01-20 22:26:39,640 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 21 [2018-01-20 22:26:39,640 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:39,647 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:39,664 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 50 treesize of output 74 [2018-01-20 22:26:39,668 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 20 treesize of output 35 [2018-01-20 22:26:39,668 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:39,676 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:39,688 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 2 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-20 22:26:39,688 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 3 variables, input treesize:81, output treesize:105 [2018-01-20 22:26:39,729 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:39,734 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 121 treesize of output 110 [2018-01-20 22:26:39,739 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:39,747 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 2 case distinctions, treesize of input 78 treesize of output 64 [2018-01-20 22:26:39,748 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-20 22:26:39,779 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-20 22:26:39,829 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 87 treesize of output 88 [2018-01-20 22:26:39,832 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:39,833 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:39,833 INFO L682 Elim1Store]: detected equality via solver [2018-01-20 22:26:39,835 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 41 treesize of output 74 [2018-01-20 22:26:39,836 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:39,848 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:39,854 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 89 treesize of output 90 [2018-01-20 22:26:39,858 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:39,865 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 2 case distinctions, treesize of input 41 treesize of output 74 [2018-01-20 22:26:39,866 INFO L267 ElimStorePlain]: Start of recursive call 7: End of recursive call: and 2 xjuncts. [2018-01-20 22:26:39,885 INFO L267 ElimStorePlain]: Start of recursive call 6: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-20 22:26:39,916 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 2 dim-2 vars, End of recursive call: 1 dim-0 vars, and 2 xjuncts. [2018-01-20 22:26:39,917 INFO L202 ElimStorePlain]: Needed 7 recursive calls to eliminate 3 variables, input treesize:143, output treesize:149 [2018-01-20 22:26:39,972 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 255 treesize of output 191 [2018-01-20 22:26:39,986 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:40,003 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 2 case distinctions, treesize of input 167 treesize of output 165 [2018-01-20 22:26:40,005 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-20 22:26:40,046 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-20 22:26:40,114 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 132 treesize of output 113 [2018-01-20 22:26:40,122 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:40,130 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 2 case distinctions, treesize of input 49 treesize of output 55 [2018-01-20 22:26:40,131 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 2 xjuncts. [2018-01-20 22:26:40,151 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-20 22:26:40,157 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 128 treesize of output 109 [2018-01-20 22:26:40,160 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:40,161 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:40,162 INFO L682 Elim1Store]: detected equality via solver [2018-01-20 22:26:40,164 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 49 treesize of output 51 [2018-01-20 22:26:40,164 INFO L267 ElimStorePlain]: Start of recursive call 7: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:40,176 INFO L267 ElimStorePlain]: Start of recursive call 6: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:40,208 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 93 treesize of output 86 [2018-01-20 22:26:40,210 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 17 [2018-01-20 22:26:40,211 INFO L267 ElimStorePlain]: Start of recursive call 9: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:40,220 INFO L267 ElimStorePlain]: Start of recursive call 8: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:40,223 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 78 treesize of output 71 [2018-01-20 22:26:40,237 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 17 [2018-01-20 22:26:40,237 INFO L267 ElimStorePlain]: Start of recursive call 11: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:40,289 INFO L267 ElimStorePlain]: Start of recursive call 10: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:40,312 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 3 dim-2 vars, End of recursive call: 1 dim-0 vars, and 2 xjuncts. [2018-01-20 22:26:40,313 INFO L202 ElimStorePlain]: Needed 11 recursive calls to eliminate 4 variables, input treesize:255, output treesize:145 [2018-01-20 22:26:40,380 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 59 treesize of output 45 [2018-01-20 22:26:40,382 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 1 [2018-01-20 22:26:40,383 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:40,398 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 40 treesize of output 29 [2018-01-20 22:26:40,399 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:40,404 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:40,425 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:40,426 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 1 variables, input treesize:73, output treesize:43 [2018-01-20 22:26:40,531 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 27 treesize of output 23 [2018-01-20 22:26:40,533 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 3 [2018-01-20 22:26:40,533 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:40,534 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:40,539 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-20 22:26:40,539 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:49, output treesize:26 [2018-01-20 22:26:40,583 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-01-20 22:26:40,612 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-20 22:26:40,612 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 16] total 33 [2018-01-20 22:26:40,612 INFO L409 AbstractCegarLoop]: Interpolant automaton has 33 states [2018-01-20 22:26:40,612 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2018-01-20 22:26:40,613 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=80, Invalid=976, Unknown=0, NotChecked=0, Total=1056 [2018-01-20 22:26:40,613 INFO L87 Difference]: Start difference. First operand 164 states and 179 transitions. Second operand 33 states. [2018-01-20 22:26:41,941 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:26:41,941 INFO L93 Difference]: Finished difference Result 241 states and 261 transitions. [2018-01-20 22:26:41,942 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2018-01-20 22:26:41,942 INFO L78 Accepts]: Start accepts. Automaton has 33 states. Word has length 56 [2018-01-20 22:26:41,942 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:26:41,943 INFO L225 Difference]: With dead ends: 241 [2018-01-20 22:26:41,943 INFO L226 Difference]: Without dead ends: 224 [2018-01-20 22:26:41,944 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 94 GetRequests, 42 SyntacticMatches, 5 SemanticMatches, 47 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 380 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=315, Invalid=2037, Unknown=0, NotChecked=0, Total=2352 [2018-01-20 22:26:41,944 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 224 states. [2018-01-20 22:26:41,957 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 224 to 173. [2018-01-20 22:26:41,957 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 173 states. [2018-01-20 22:26:41,958 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 173 states to 173 states and 188 transitions. [2018-01-20 22:26:41,959 INFO L78 Accepts]: Start accepts. Automaton has 173 states and 188 transitions. Word has length 56 [2018-01-20 22:26:41,959 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:26:41,959 INFO L432 AbstractCegarLoop]: Abstraction has 173 states and 188 transitions. [2018-01-20 22:26:41,959 INFO L433 AbstractCegarLoop]: Interpolant automaton has 33 states. [2018-01-20 22:26:41,959 INFO L276 IsEmpty]: Start isEmpty. Operand 173 states and 188 transitions. [2018-01-20 22:26:41,960 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 58 [2018-01-20 22:26:41,960 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:26:41,967 INFO L322 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 22:26:41,967 INFO L371 AbstractCegarLoop]: === Iteration 9 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-20 22:26:41,967 INFO L82 PathProgramCache]: Analyzing trace with hash -1257592245, now seen corresponding path program 1 times [2018-01-20 22:26:41,967 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:26:41,967 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:26:41,968 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:41,968 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:26:41,968 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:41,984 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:26:41,985 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:26:42,233 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 3 proven. 0 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-01-20 22:26:42,234 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-20 22:26:42,234 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [13] imperfect sequences [] total 13 [2018-01-20 22:26:42,234 INFO L409 AbstractCegarLoop]: Interpolant automaton has 13 states [2018-01-20 22:26:42,234 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2018-01-20 22:26:42,234 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=126, Unknown=0, NotChecked=0, Total=156 [2018-01-20 22:26:42,234 INFO L87 Difference]: Start difference. First operand 173 states and 188 transitions. Second operand 13 states. [2018-01-20 22:26:42,536 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:26:42,536 INFO L93 Difference]: Finished difference Result 224 states and 242 transitions. [2018-01-20 22:26:42,536 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-01-20 22:26:42,536 INFO L78 Accepts]: Start accepts. Automaton has 13 states. Word has length 57 [2018-01-20 22:26:42,537 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:26:42,537 INFO L225 Difference]: With dead ends: 224 [2018-01-20 22:26:42,538 INFO L226 Difference]: Without dead ends: 204 [2018-01-20 22:26:42,538 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 24 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 77 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=103, Invalid=403, Unknown=0, NotChecked=0, Total=506 [2018-01-20 22:26:42,538 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 204 states. [2018-01-20 22:26:42,550 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 204 to 170. [2018-01-20 22:26:42,550 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 170 states. [2018-01-20 22:26:42,551 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 170 states to 170 states and 185 transitions. [2018-01-20 22:26:42,551 INFO L78 Accepts]: Start accepts. Automaton has 170 states and 185 transitions. Word has length 57 [2018-01-20 22:26:42,551 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:26:42,551 INFO L432 AbstractCegarLoop]: Abstraction has 170 states and 185 transitions. [2018-01-20 22:26:42,551 INFO L433 AbstractCegarLoop]: Interpolant automaton has 13 states. [2018-01-20 22:26:42,552 INFO L276 IsEmpty]: Start isEmpty. Operand 170 states and 185 transitions. [2018-01-20 22:26:42,552 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 62 [2018-01-20 22:26:42,552 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:26:42,552 INFO L322 BasicCegarLoop]: trace histogram [3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 22:26:42,552 INFO L371 AbstractCegarLoop]: === Iteration 10 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-20 22:26:42,553 INFO L82 PathProgramCache]: Analyzing trace with hash -266683574, now seen corresponding path program 2 times [2018-01-20 22:26:42,553 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:26:42,553 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:26:42,554 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:42,554 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:26:42,554 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:42,564 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:26:42,565 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:26:42,847 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 6 proven. 6 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-01-20 22:26:42,847 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-20 22:26:42,847 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-20 22:26:42,852 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-01-20 22:26:42,866 INFO L201 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-20 22:26:42,883 INFO L214 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-20 22:26:42,886 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-20 22:26:42,891 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-20 22:26:42,928 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 8 [2018-01-20 22:26:42,930 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-01-20 22:26:42,930 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:42,931 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:42,934 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:42,934 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:15, output treesize:11 [2018-01-20 22:26:42,962 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 21 treesize of output 16 [2018-01-20 22:26:42,964 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:42,965 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 23 [2018-01-20 22:26:42,965 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:42,970 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:42,973 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:42,973 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:24, output treesize:20 [2018-01-20 22:26:42,991 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 36 treesize of output 29 [2018-01-20 22:26:42,992 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:42,993 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:42,994 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:42,996 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 37 [2018-01-20 22:26:42,997 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:43,002 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:43,006 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:43,006 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:39, output treesize:20 [2018-01-20 22:26:43,030 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 10 [2018-01-20 22:26:43,034 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 9 [2018-01-20 22:26:43,035 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:43,036 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:43,045 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 36 treesize of output 29 [2018-01-20 22:26:43,047 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:43,048 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:43,049 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:43,052 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 37 [2018-01-20 22:26:43,053 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:43,058 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:43,063 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:43,064 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 2 variables, input treesize:52, output treesize:29 [2018-01-20 22:26:43,128 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 5 [2018-01-20 22:26:43,129 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 1 [2018-01-20 22:26:43,130 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:43,130 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:43,135 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-20 22:26:43,135 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:36, output treesize:29 [2018-01-20 22:26:43,271 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 26 treesize of output 16 [2018-01-20 22:26:43,282 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 0 new quantified variables, introduced 2 case distinctions, treesize of input 16 treesize of output 17 [2018-01-20 22:26:43,283 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 4 xjuncts. [2018-01-20 22:26:43,293 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 3 xjuncts. [2018-01-20 22:26:43,303 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 2 dim-0 vars, and 3 xjuncts. [2018-01-20 22:26:43,303 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:33, output treesize:44 [2018-01-20 22:26:43,386 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 13 [2018-01-20 22:26:43,390 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 1 case distinctions, treesize of input 13 treesize of output 10 [2018-01-20 22:26:43,390 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-20 22:26:43,392 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-20 22:26:43,394 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 2 xjuncts. [2018-01-20 22:26:43,394 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:17, output treesize:10 [2018-01-20 22:26:43,437 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 0 proven. 8 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2018-01-20 22:26:43,457 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-20 22:26:43,457 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 19] total 30 [2018-01-20 22:26:43,457 INFO L409 AbstractCegarLoop]: Interpolant automaton has 30 states [2018-01-20 22:26:43,457 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2018-01-20 22:26:43,458 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=87, Invalid=769, Unknown=14, NotChecked=0, Total=870 [2018-01-20 22:26:43,458 INFO L87 Difference]: Start difference. First operand 170 states and 185 transitions. Second operand 30 states. [2018-01-20 22:26:44,547 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:26:44,547 INFO L93 Difference]: Finished difference Result 200 states and 215 transitions. [2018-01-20 22:26:44,547 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2018-01-20 22:26:44,547 INFO L78 Accepts]: Start accepts. Automaton has 30 states. Word has length 61 [2018-01-20 22:26:44,548 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:26:44,548 INFO L225 Difference]: With dead ends: 200 [2018-01-20 22:26:44,548 INFO L226 Difference]: Without dead ends: 136 [2018-01-20 22:26:44,549 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 97 GetRequests, 44 SyntacticMatches, 4 SemanticMatches, 49 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 492 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=440, Invalid=2088, Unknown=22, NotChecked=0, Total=2550 [2018-01-20 22:26:44,549 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 136 states. [2018-01-20 22:26:44,556 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 136 to 132. [2018-01-20 22:26:44,556 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 132 states. [2018-01-20 22:26:44,557 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 132 states to 132 states and 144 transitions. [2018-01-20 22:26:44,557 INFO L78 Accepts]: Start accepts. Automaton has 132 states and 144 transitions. Word has length 61 [2018-01-20 22:26:44,557 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:26:44,557 INFO L432 AbstractCegarLoop]: Abstraction has 132 states and 144 transitions. [2018-01-20 22:26:44,557 INFO L433 AbstractCegarLoop]: Interpolant automaton has 30 states. [2018-01-20 22:26:44,557 INFO L276 IsEmpty]: Start isEmpty. Operand 132 states and 144 transitions. [2018-01-20 22:26:44,558 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 64 [2018-01-20 22:26:44,558 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:26:44,558 INFO L322 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 22:26:44,558 INFO L371 AbstractCegarLoop]: === Iteration 11 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-20 22:26:44,558 INFO L82 PathProgramCache]: Analyzing trace with hash 887372441, now seen corresponding path program 1 times [2018-01-20 22:26:44,558 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:26:44,558 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:26:44,559 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:44,559 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-01-20 22:26:44,559 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:44,568 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:26:44,569 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:26:44,600 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 14 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 22:26:44,601 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-20 22:26:44,601 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-01-20 22:26:44,601 INFO L409 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-01-20 22:26:44,601 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-01-20 22:26:44,601 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-20 22:26:44,602 INFO L87 Difference]: Start difference. First operand 132 states and 144 transitions. Second operand 3 states. [2018-01-20 22:26:44,622 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:26:44,623 INFO L93 Difference]: Finished difference Result 271 states and 298 transitions. [2018-01-20 22:26:44,623 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-01-20 22:26:44,623 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 63 [2018-01-20 22:26:44,623 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:26:44,624 INFO L225 Difference]: With dead ends: 271 [2018-01-20 22:26:44,624 INFO L226 Difference]: Without dead ends: 205 [2018-01-20 22:26:44,624 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-20 22:26:44,624 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 205 states. [2018-01-20 22:26:44,633 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 205 to 151. [2018-01-20 22:26:44,633 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 151 states. [2018-01-20 22:26:44,634 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 151 states to 151 states and 165 transitions. [2018-01-20 22:26:44,634 INFO L78 Accepts]: Start accepts. Automaton has 151 states and 165 transitions. Word has length 63 [2018-01-20 22:26:44,634 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:26:44,634 INFO L432 AbstractCegarLoop]: Abstraction has 151 states and 165 transitions. [2018-01-20 22:26:44,634 INFO L433 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-01-20 22:26:44,634 INFO L276 IsEmpty]: Start isEmpty. Operand 151 states and 165 transitions. [2018-01-20 22:26:44,635 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 68 [2018-01-20 22:26:44,635 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:26:44,635 INFO L322 BasicCegarLoop]: trace histogram [3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 22:26:44,635 INFO L371 AbstractCegarLoop]: === Iteration 12 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-20 22:26:44,636 INFO L82 PathProgramCache]: Analyzing trace with hash -1716260907, now seen corresponding path program 2 times [2018-01-20 22:26:44,636 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:26:44,636 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:26:44,637 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:44,637 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:26:44,637 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:26:44,660 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:26:44,661 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:26:47,348 WARN L146 SmtUtils]: Spent 141ms on a formula simplification. DAG size of input: 60 DAG size of output 44 [2018-01-20 22:26:47,812 WARN L146 SmtUtils]: Spent 411ms on a formula simplification. DAG size of input: 116 DAG size of output 78 [2018-01-20 22:26:48,369 WARN L146 SmtUtils]: Spent 509ms on a formula simplification. DAG size of input: 140 DAG size of output 86 [2018-01-20 22:26:48,744 WARN L146 SmtUtils]: Spent 311ms on a formula simplification. DAG size of input: 126 DAG size of output 84 [2018-01-20 22:26:49,251 WARN L146 SmtUtils]: Spent 378ms on a formula simplification. DAG size of input: 120 DAG size of output 77 [2018-01-20 22:26:49,736 WARN L146 SmtUtils]: Spent 419ms on a formula simplification. DAG size of input: 126 DAG size of output 75 [2018-01-20 22:26:50,483 WARN L146 SmtUtils]: Spent 117ms on a formula simplification. DAG size of input: 114 DAG size of output 52 [2018-01-20 22:26:50,806 WARN L146 SmtUtils]: Spent 231ms on a formula simplification. DAG size of input: 183 DAG size of output 39 [2018-01-20 22:26:51,302 WARN L146 SmtUtils]: Spent 359ms on a formula simplification. DAG size of input: 266 DAG size of output 64 [2018-01-20 22:26:51,698 WARN L146 SmtUtils]: Spent 249ms on a formula simplification. DAG size of input: 148 DAG size of output 37 [2018-01-20 22:26:52,172 WARN L146 SmtUtils]: Spent 140ms on a formula simplification. DAG size of input: 143 DAG size of output 32 [2018-01-20 22:26:52,427 WARN L146 SmtUtils]: Spent 115ms on a formula simplification. DAG size of input: 115 DAG size of output 32 [2018-01-20 22:26:52,698 WARN L146 SmtUtils]: Spent 124ms on a formula simplification. DAG size of input: 126 DAG size of output 32 [2018-01-20 22:26:55,317 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 0 proven. 23 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 22:26:55,317 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-20 22:26:55,317 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-20 22:26:55,322 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-01-20 22:26:55,335 INFO L201 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-20 22:26:55,345 INFO L214 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-20 22:26:55,349 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-20 22:26:55,353 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-20 22:26:55,657 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 8 [2018-01-20 22:26:55,659 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-01-20 22:26:55,659 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:55,661 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:55,671 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 8 [2018-01-20 22:26:55,673 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-01-20 22:26:55,673 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:55,675 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:55,683 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 2 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:55,683 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 3 variables, input treesize:49, output treesize:42 [2018-01-20 22:26:55,862 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:55,866 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 30 [2018-01-20 22:26:55,868 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 13 [2018-01-20 22:26:55,868 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:55,872 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:55,885 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:55,888 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 60 treesize of output 64 [2018-01-20 22:26:55,890 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 13 [2018-01-20 22:26:55,890 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:55,897 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:55,907 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 2 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-20 22:26:55,907 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 3 variables, input treesize:84, output treesize:68 [2018-01-20 22:26:56,019 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:56,028 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 59 treesize of output 51 [2018-01-20 22:26:56,030 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 1 [2018-01-20 22:26:56,030 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:56,043 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 38 treesize of output 27 [2018-01-20 22:26:56,043 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:56,049 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:56,058 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:56,059 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 24 treesize of output 22 [2018-01-20 22:26:56,061 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 3 [2018-01-20 22:26:56,061 INFO L267 ElimStorePlain]: Start of recursive call 6: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:56,066 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 1 [2018-01-20 22:26:56,066 INFO L267 ElimStorePlain]: Start of recursive call 7: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:56,068 INFO L267 ElimStorePlain]: Start of recursive call 5: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:56,073 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 2 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:56,073 INFO L202 ElimStorePlain]: Needed 7 recursive calls to eliminate 4 variables, input treesize:79, output treesize:27 [2018-01-20 22:26:56,253 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 10 [2018-01-20 22:26:56,255 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 9 [2018-01-20 22:26:56,255 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:56,256 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:56,271 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:56,271 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:40, output treesize:36 [2018-01-20 22:26:56,480 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 8 [2018-01-20 22:26:56,482 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-01-20 22:26:56,482 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:56,484 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:56,503 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 25 treesize of output 20 [2018-01-20 22:26:56,505 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:56,506 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 20 treesize of output 16 [2018-01-20 22:26:56,506 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:56,511 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:56,526 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 8 [2018-01-20 22:26:56,528 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-01-20 22:26:56,528 INFO L267 ElimStorePlain]: Start of recursive call 7: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:56,529 INFO L267 ElimStorePlain]: Start of recursive call 6: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:56,541 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 3 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:56,542 INFO L202 ElimStorePlain]: Needed 7 recursive calls to eliminate 4 variables, input treesize:87, output treesize:65 [2018-01-20 22:26:56,761 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:56,765 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 30 [2018-01-20 22:26:56,768 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 13 [2018-01-20 22:26:56,768 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:56,773 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:56,794 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:56,797 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 41 treesize of output 42 [2018-01-20 22:26:56,799 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 24 treesize of output 1 [2018-01-20 22:26:56,799 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:56,803 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:56,820 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:56,824 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 66 treesize of output 70 [2018-01-20 22:26:56,826 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 13 [2018-01-20 22:26:56,826 INFO L267 ElimStorePlain]: Start of recursive call 7: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:56,834 INFO L267 ElimStorePlain]: Start of recursive call 6: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:56,851 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 3 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-20 22:26:56,851 INFO L202 ElimStorePlain]: Needed 7 recursive calls to eliminate 4 variables, input treesize:138, output treesize:91 [2018-01-20 22:26:57,015 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:57,016 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 65 treesize of output 57 [2018-01-20 22:26:57,018 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 1 [2018-01-20 22:26:57,018 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:57,027 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 44 treesize of output 33 [2018-01-20 22:26:57,027 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:57,032 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:57,047 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:57,048 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 24 treesize of output 22 [2018-01-20 22:26:57,050 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 3 [2018-01-20 22:26:57,050 INFO L267 ElimStorePlain]: Start of recursive call 6: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:57,056 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 1 [2018-01-20 22:26:57,056 INFO L267 ElimStorePlain]: Start of recursive call 7: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:57,058 INFO L267 ElimStorePlain]: Start of recursive call 5: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:57,066 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 2 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-20 22:26:57,066 INFO L202 ElimStorePlain]: Needed 7 recursive calls to eliminate 4 variables, input treesize:100, output treesize:48 [2018-01-20 22:26:57,222 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:57,225 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 24 [2018-01-20 22:26:57,227 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 1 [2018-01-20 22:26:57,227 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:57,231 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:57,240 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-20 22:26:57,240 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:63, output treesize:48 [2018-01-20 22:26:57,246 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:57,250 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 21 treesize of output 22 [2018-01-20 22:26:57,253 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 9 [2018-01-20 22:26:57,253 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:57,260 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:57,274 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-20 22:26:57,274 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:61, output treesize:57 [2018-01-20 22:26:57,366 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:57,367 INFO L682 Elim1Store]: detected equality via solver [2018-01-20 22:26:57,369 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 26 treesize of output 25 [2018-01-20 22:26:57,372 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 7 [2018-01-20 22:26:57,372 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:57,376 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:57,385 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: 2 dim-0 vars, and 1 xjuncts. [2018-01-20 22:26:57,385 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:60, output treesize:49 [2018-01-20 22:26:58,306 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 68 treesize of output 64 [2018-01-20 22:26:58,308 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 4 [2018-01-20 22:26:58,338 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:58,348 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:58,378 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 68 treesize of output 66 [2018-01-20 22:26:58,380 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 1 [2018-01-20 22:26:58,380 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:58,390 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:58,418 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 57 treesize of output 55 [2018-01-20 22:26:58,420 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 1 [2018-01-20 22:26:58,420 INFO L267 ElimStorePlain]: Start of recursive call 7: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:58,429 INFO L267 ElimStorePlain]: Start of recursive call 6: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:58,455 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 61 treesize of output 57 [2018-01-20 22:26:58,459 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 4 [2018-01-20 22:26:58,459 INFO L267 ElimStorePlain]: Start of recursive call 9: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:58,471 INFO L267 ElimStorePlain]: Start of recursive call 8: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:58,496 INFO L267 ElimStorePlain]: Start of recursive call 1: 6 dim-0 vars, 4 dim-2 vars, End of recursive call: 6 dim-0 vars, and 2 xjuncts. [2018-01-20 22:26:58,496 INFO L202 ElimStorePlain]: Needed 9 recursive calls to eliminate 10 variables, input treesize:137, output treesize:101 [2018-01-20 22:26:58,802 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:58,814 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 2 case distinctions, treesize of input 59 treesize of output 73 [2018-01-20 22:26:58,818 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:58,820 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 56 treesize of output 50 [2018-01-20 22:26:58,820 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:58,893 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:58,895 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 48 treesize of output 42 [2018-01-20 22:26:58,895 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:58,916 INFO L267 ElimStorePlain]: Start of recursive call 2: 4 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:26:58,940 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:26:58,951 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 2 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 2 case distinctions, treesize of input 59 treesize of output 73 [2018-01-20 22:26:58,955 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 55 treesize of output 48 [2018-01-20 22:26:58,955 INFO L267 ElimStorePlain]: Start of recursive call 6: End of recursive call: and 1 xjuncts. [2018-01-20 22:26:59,008 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 1 case distinctions, treesize of input 52 treesize of output 50 [2018-01-20 22:26:59,009 INFO L267 ElimStorePlain]: Start of recursive call 7: End of recursive call: and 2 xjuncts. [2018-01-20 22:26:59,064 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 1 case distinctions, treesize of input 48 treesize of output 46 [2018-01-20 22:26:59,065 INFO L267 ElimStorePlain]: Start of recursive call 8: End of recursive call: and 2 xjuncts. [2018-01-20 22:26:59,122 INFO L267 ElimStorePlain]: Start of recursive call 5: 4 dim-1 vars, End of recursive call: and 3 xjuncts. [2018-01-20 22:26:59,162 INFO L267 ElimStorePlain]: Start of recursive call 1: 6 dim-0 vars, 2 dim-2 vars, End of recursive call: 12 dim-0 vars, and 4 xjuncts. [2018-01-20 22:26:59,162 INFO L202 ElimStorePlain]: Needed 8 recursive calls to eliminate 8 variables, input treesize:119, output treesize:164 [2018-01-20 22:26:59,441 WARN L1029 $PredicateComparison]: unable to prove that (or (and (not (= 0 c_main_~x~5.offset)) (exists ((v_prenex_34 Int) (v_prenex_35 Int) (v_prenex_32 Int)) (let ((.cse1 (store |c_old(#valid)| v_prenex_35 1))) (let ((.cse0 (store .cse1 v_prenex_34 1))) (and (= 0 (select .cse0 v_prenex_32)) (= 0 (select .cse1 v_prenex_34)) (= |c_#valid| (store .cse0 v_prenex_32 1))))))) (and (not (= 0 c_main_~x~5.base)) (exists ((v_prenex_44 Int) (v_prenex_43 Int) (v_prenex_42 Int)) (let ((.cse2 (store |c_old(#valid)| v_prenex_44 1))) (let ((.cse3 (store .cse2 v_prenex_43 1))) (and (not (= v_prenex_42 c_main_~x~5.base)) (not (= c_main_~x~5.base v_prenex_43)) (= 0 (select .cse2 v_prenex_43)) (= 0 (select .cse3 v_prenex_42)) (= |c_#valid| (store .cse3 v_prenex_42 1)))))))) is different from true [2018-01-20 22:26:59,449 WARN L1029 $PredicateComparison]: unable to prove that (exists ((v_prenex_44 Int) (v_prenex_43 Int) (v_prenex_42 Int) (main_~x~5.base Int)) (let ((.cse1 (store |c_old(#valid)| v_prenex_44 1))) (let ((.cse2 (store .cse1 v_prenex_43 1))) (let ((.cse0 (store .cse2 v_prenex_42 1))) (and (not (= 0 main_~x~5.base)) (not (= v_prenex_42 main_~x~5.base)) (= (store .cse0 main_~x~5.base 0) |c_#valid|) (not (= main_~x~5.base v_prenex_43)) (= 0 (select .cse1 v_prenex_43)) (= 0 (select .cse2 v_prenex_42)) (= 1 (select .cse0 main_~x~5.base))))))) is different from true [2018-01-20 22:26:59,483 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 0 proven. 23 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 22:26:59,504 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-20 22:26:59,504 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [25, 29] total 52 [2018-01-20 22:26:59,505 INFO L409 AbstractCegarLoop]: Interpolant automaton has 52 states [2018-01-20 22:26:59,505 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 52 interpolants. [2018-01-20 22:26:59,506 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=293, Invalid=2163, Unknown=2, NotChecked=194, Total=2652 [2018-01-20 22:26:59,506 INFO L87 Difference]: Start difference. First operand 151 states and 165 transitions. Second operand 52 states. [2018-01-20 22:27:00,766 WARN L146 SmtUtils]: Spent 160ms on a formula simplification. DAG size of input: 191 DAG size of output 42 [2018-01-20 22:27:00,997 WARN L146 SmtUtils]: Spent 140ms on a formula simplification. DAG size of input: 192 DAG size of output 44 [2018-01-20 22:27:01,288 WARN L146 SmtUtils]: Spent 154ms on a formula simplification. DAG size of input: 200 DAG size of output 55 [2018-01-20 22:27:01,536 WARN L146 SmtUtils]: Spent 151ms on a formula simplification. DAG size of input: 199 DAG size of output 53 [2018-01-20 22:27:01,845 WARN L146 SmtUtils]: Spent 190ms on a formula simplification. DAG size of input: 204 DAG size of output 58 [2018-01-20 22:27:02,724 WARN L146 SmtUtils]: Spent 225ms on a formula simplification. DAG size of input: 205 DAG size of output 72 [2018-01-20 22:27:03,384 WARN L146 SmtUtils]: Spent 192ms on a formula simplification. DAG size of input: 161 DAG size of output 73 [2018-01-20 22:27:04,167 WARN L146 SmtUtils]: Spent 208ms on a formula simplification. DAG size of input: 155 DAG size of output 72 [2018-01-20 22:27:04,548 WARN L146 SmtUtils]: Spent 157ms on a formula simplification. DAG size of input: 119 DAG size of output 65 [2018-01-20 22:27:07,049 WARN L146 SmtUtils]: Spent 131ms on a formula simplification. DAG size of input: 126 DAG size of output 59 [2018-01-20 22:27:08,098 WARN L146 SmtUtils]: Spent 193ms on a formula simplification. DAG size of input: 144 DAG size of output 77 [2018-01-20 22:27:08,617 WARN L146 SmtUtils]: Spent 238ms on a formula simplification. DAG size of input: 145 DAG size of output 73 [2018-01-20 22:27:10,157 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:27:10,157 INFO L93 Difference]: Finished difference Result 383 states and 416 transitions. [2018-01-20 22:27:10,158 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 50 states. [2018-01-20 22:27:10,158 INFO L78 Accepts]: Start accepts. Automaton has 52 states. Word has length 67 [2018-01-20 22:27:10,158 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:27:10,159 INFO L225 Difference]: With dead ends: 383 [2018-01-20 22:27:10,159 INFO L226 Difference]: Without dead ends: 358 [2018-01-20 22:27:10,161 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 160 GetRequests, 41 SyntacticMatches, 24 SemanticMatches, 95 ConstructedPredicates, 2 IntricatePredicates, 0 DeprecatedPredicates, 2355 ImplicationChecksByTransitivity, 18.7s TimeCoverageRelationStatistics Valid=1348, Invalid=7536, Unknown=54, NotChecked=374, Total=9312 [2018-01-20 22:27:10,161 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 358 states. [2018-01-20 22:27:10,181 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 358 to 212. [2018-01-20 22:27:10,181 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 212 states. [2018-01-20 22:27:10,182 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 212 states to 212 states and 233 transitions. [2018-01-20 22:27:10,182 INFO L78 Accepts]: Start accepts. Automaton has 212 states and 233 transitions. Word has length 67 [2018-01-20 22:27:10,183 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:27:10,183 INFO L432 AbstractCegarLoop]: Abstraction has 212 states and 233 transitions. [2018-01-20 22:27:10,183 INFO L433 AbstractCegarLoop]: Interpolant automaton has 52 states. [2018-01-20 22:27:10,183 INFO L276 IsEmpty]: Start isEmpty. Operand 212 states and 233 transitions. [2018-01-20 22:27:10,184 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 69 [2018-01-20 22:27:10,184 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:27:10,184 INFO L322 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 22:27:10,184 INFO L371 AbstractCegarLoop]: === Iteration 13 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-20 22:27:10,184 INFO L82 PathProgramCache]: Analyzing trace with hash -878465624, now seen corresponding path program 1 times [2018-01-20 22:27:10,185 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:27:10,185 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:27:10,185 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:27:10,185 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-01-20 22:27:10,186 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:27:10,199 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2018-01-20 22:27:10,214 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2018-01-20 22:27:10,227 INFO L381 BasicCegarLoop]: Counterexample might be feasible [2018-01-20 22:27:10,237 WARN L343 cessorBacktranslator]: Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) [2018-01-20 22:27:10,249 WARN L343 cessorBacktranslator]: Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) [2018-01-20 22:27:10,249 WARN L343 cessorBacktranslator]: Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) [2018-01-20 22:27:10,269 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-20 22:27:10,269 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-20 22:27:10,269 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-20 22:27:10,269 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-20 22:27:10,269 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-20 22:27:10,269 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-20 22:27:10,269 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-20 22:27:10,269 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == mainErr0EnsuresViolation======== [2018-01-20 22:27:10,269 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-20 22:27:10,271 INFO L276 IsEmpty]: Start isEmpty. Operand 69 states. [2018-01-20 22:27:10,271 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2018-01-20 22:27:10,271 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:27:10,271 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 22:27:10,272 INFO L371 AbstractCegarLoop]: === Iteration 1 === [mainErr0EnsuresViolation]=== [2018-01-20 22:27:10,272 INFO L82 PathProgramCache]: Analyzing trace with hash -177182084, now seen corresponding path program 1 times [2018-01-20 22:27:10,272 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:27:10,272 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:27:10,273 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:27:10,273 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:27:10,273 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:27:10,276 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:27:10,277 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:27:10,282 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 22:27:10,282 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-20 22:27:10,282 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-01-20 22:27:10,282 INFO L409 AbstractCegarLoop]: Interpolant automaton has 2 states [2018-01-20 22:27:10,282 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2018-01-20 22:27:10,282 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-01-20 22:27:10,283 INFO L87 Difference]: Start difference. First operand 69 states. Second operand 2 states. [2018-01-20 22:27:10,286 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:27:10,286 INFO L93 Difference]: Finished difference Result 126 states and 162 transitions. [2018-01-20 22:27:10,286 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2018-01-20 22:27:10,286 INFO L78 Accepts]: Start accepts. Automaton has 2 states. Word has length 23 [2018-01-20 22:27:10,286 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:27:10,287 INFO L225 Difference]: With dead ends: 126 [2018-01-20 22:27:10,287 INFO L226 Difference]: Without dead ends: 64 [2018-01-20 22:27:10,287 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-01-20 22:27:10,288 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 64 states. [2018-01-20 22:27:10,289 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 64 to 64. [2018-01-20 22:27:10,290 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 64 states. [2018-01-20 22:27:10,290 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 64 states to 64 states and 70 transitions. [2018-01-20 22:27:10,290 INFO L78 Accepts]: Start accepts. Automaton has 64 states and 70 transitions. Word has length 23 [2018-01-20 22:27:10,291 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:27:10,291 INFO L432 AbstractCegarLoop]: Abstraction has 64 states and 70 transitions. [2018-01-20 22:27:10,291 INFO L433 AbstractCegarLoop]: Interpolant automaton has 2 states. [2018-01-20 22:27:10,291 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 70 transitions. [2018-01-20 22:27:10,291 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2018-01-20 22:27:10,291 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:27:10,292 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 22:27:10,292 INFO L371 AbstractCegarLoop]: === Iteration 2 === [mainErr0EnsuresViolation]=== [2018-01-20 22:27:10,292 INFO L82 PathProgramCache]: Analyzing trace with hash -1050379846, now seen corresponding path program 1 times [2018-01-20 22:27:10,292 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:27:10,292 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:27:10,293 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:27:10,293 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:27:10,293 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:27:10,299 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:27:10,299 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:27:10,523 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 22:27:10,523 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-20 22:27:10,523 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2018-01-20 22:27:10,523 INFO L409 AbstractCegarLoop]: Interpolant automaton has 10 states [2018-01-20 22:27:10,523 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2018-01-20 22:27:10,523 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=71, Unknown=0, NotChecked=0, Total=90 [2018-01-20 22:27:10,524 INFO L87 Difference]: Start difference. First operand 64 states and 70 transitions. Second operand 10 states. [2018-01-20 22:27:10,781 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:27:10,781 INFO L93 Difference]: Finished difference Result 102 states and 111 transitions. [2018-01-20 22:27:10,781 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-01-20 22:27:10,781 INFO L78 Accepts]: Start accepts. Automaton has 10 states. Word has length 31 [2018-01-20 22:27:10,781 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:27:10,782 INFO L225 Difference]: With dead ends: 102 [2018-01-20 22:27:10,782 INFO L226 Difference]: Without dead ends: 98 [2018-01-20 22:27:10,782 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 21 GetRequests, 4 SyntacticMatches, 2 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=79, Invalid=193, Unknown=0, NotChecked=0, Total=272 [2018-01-20 22:27:10,782 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 98 states. [2018-01-20 22:27:10,785 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 98 to 94. [2018-01-20 22:27:10,785 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 94 states. [2018-01-20 22:27:10,785 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 94 states to 94 states and 103 transitions. [2018-01-20 22:27:10,785 INFO L78 Accepts]: Start accepts. Automaton has 94 states and 103 transitions. Word has length 31 [2018-01-20 22:27:10,785 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:27:10,785 INFO L432 AbstractCegarLoop]: Abstraction has 94 states and 103 transitions. [2018-01-20 22:27:10,785 INFO L433 AbstractCegarLoop]: Interpolant automaton has 10 states. [2018-01-20 22:27:10,785 INFO L276 IsEmpty]: Start isEmpty. Operand 94 states and 103 transitions. [2018-01-20 22:27:10,786 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2018-01-20 22:27:10,786 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:27:10,786 INFO L322 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 22:27:10,786 INFO L371 AbstractCegarLoop]: === Iteration 3 === [mainErr0EnsuresViolation]=== [2018-01-20 22:27:10,786 INFO L82 PathProgramCache]: Analyzing trace with hash -423368418, now seen corresponding path program 1 times [2018-01-20 22:27:10,786 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:27:10,786 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:27:10,787 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:27:10,787 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:27:10,787 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:27:10,792 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:27:10,792 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:27:11,148 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 22:27:11,149 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-20 22:27:11,149 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-20 22:27:11,157 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:27:11,171 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:27:11,173 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-20 22:27:11,178 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 8 [2018-01-20 22:27:11,180 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-01-20 22:27:11,180 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:27:11,181 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:11,183 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:11,183 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:15, output treesize:11 [2018-01-20 22:27:11,188 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 26 treesize of output 21 [2018-01-20 22:27:11,192 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:27:11,193 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 23 [2018-01-20 22:27:11,193 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:27:11,196 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:11,199 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:11,199 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:29, output treesize:20 [2018-01-20 22:27:11,220 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 36 treesize of output 29 [2018-01-20 22:27:11,223 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:27:11,223 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:27:11,224 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:27:11,228 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 37 [2018-01-20 22:27:11,228 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:27:11,235 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:11,240 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:11,240 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:39, output treesize:20 [2018-01-20 22:27:11,291 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 36 treesize of output 29 [2018-01-20 22:27:11,293 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:27:11,294 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:27:11,295 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:27:11,297 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 37 [2018-01-20 22:27:11,298 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:27:11,337 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:11,342 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:11,342 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:42, output treesize:20 [2018-01-20 22:27:11,414 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 37 treesize of output 33 [2018-01-20 22:27:11,415 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 4 [2018-01-20 22:27:11,416 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:27:11,420 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:11,438 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 37 treesize of output 35 [2018-01-20 22:27:11,440 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 1 [2018-01-20 22:27:11,440 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-20 22:27:11,446 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:11,456 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 2 dim-2 vars, End of recursive call: 2 dim-0 vars, and 2 xjuncts. [2018-01-20 22:27:11,457 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 4 variables, input treesize:75, output treesize:57 [2018-01-20 22:27:11,605 INFO L682 Elim1Store]: detected equality via solver [2018-01-20 22:27:11,606 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 28 [2018-01-20 22:27:11,614 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 2 disjoint index pairs (out of 3 index pairs), introduced 0 new quantified variables, introduced 1 case distinctions, treesize of input 21 treesize of output 16 [2018-01-20 22:27:11,614 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-20 22:27:11,627 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-20 22:27:11,647 INFO L682 Elim1Store]: detected equality via solver [2018-01-20 22:27:11,648 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 37 treesize of output 30 [2018-01-20 22:27:11,667 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 2 disjoint index pairs (out of 3 index pairs), introduced 0 new quantified variables, introduced 2 case distinctions, treesize of input 27 treesize of output 24 [2018-01-20 22:27:11,668 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 4 xjuncts. [2018-01-20 22:27:11,702 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 3 xjuncts. [2018-01-20 22:27:11,733 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 2 dim-2 vars, End of recursive call: and 5 xjuncts. [2018-01-20 22:27:11,733 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 4 variables, input treesize:71, output treesize:55 [2018-01-20 22:27:11,834 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-20 22:27:11,834 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-20 22:27:11,837 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:11,837 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:11, output treesize:10 [2018-01-20 22:27:11,842 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 22:27:11,861 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-20 22:27:11,862 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 16] total 25 [2018-01-20 22:27:11,862 INFO L409 AbstractCegarLoop]: Interpolant automaton has 25 states [2018-01-20 22:27:11,862 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2018-01-20 22:27:11,862 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=80, Invalid=520, Unknown=0, NotChecked=0, Total=600 [2018-01-20 22:27:11,863 INFO L87 Difference]: Start difference. First operand 94 states and 103 transitions. Second operand 25 states. [2018-01-20 22:27:12,629 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:27:12,629 INFO L93 Difference]: Finished difference Result 126 states and 137 transitions. [2018-01-20 22:27:12,629 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2018-01-20 22:27:12,629 INFO L78 Accepts]: Start accepts. Automaton has 25 states. Word has length 37 [2018-01-20 22:27:12,629 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:27:12,630 INFO L225 Difference]: With dead ends: 126 [2018-01-20 22:27:12,630 INFO L226 Difference]: Without dead ends: 122 [2018-01-20 22:27:12,631 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 70 GetRequests, 25 SyntacticMatches, 6 SemanticMatches, 39 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 329 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=252, Invalid=1388, Unknown=0, NotChecked=0, Total=1640 [2018-01-20 22:27:12,631 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 122 states. [2018-01-20 22:27:12,635 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 122 to 100. [2018-01-20 22:27:12,635 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 100 states. [2018-01-20 22:27:12,635 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 100 states to 100 states and 109 transitions. [2018-01-20 22:27:12,636 INFO L78 Accepts]: Start accepts. Automaton has 100 states and 109 transitions. Word has length 37 [2018-01-20 22:27:12,636 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:27:12,636 INFO L432 AbstractCegarLoop]: Abstraction has 100 states and 109 transitions. [2018-01-20 22:27:12,636 INFO L433 AbstractCegarLoop]: Interpolant automaton has 25 states. [2018-01-20 22:27:12,636 INFO L276 IsEmpty]: Start isEmpty. Operand 100 states and 109 transitions. [2018-01-20 22:27:12,636 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2018-01-20 22:27:12,636 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:27:12,636 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 22:27:12,636 INFO L371 AbstractCegarLoop]: === Iteration 4 === [mainErr0EnsuresViolation]=== [2018-01-20 22:27:12,637 INFO L82 PathProgramCache]: Analyzing trace with hash -1679082900, now seen corresponding path program 1 times [2018-01-20 22:27:12,637 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:27:12,637 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:27:12,637 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:27:12,637 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:27:12,637 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:27:12,641 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:27:12,642 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:27:12,651 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 22:27:12,651 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-20 22:27:12,651 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-01-20 22:27:12,651 INFO L409 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-01-20 22:27:12,652 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-01-20 22:27:12,652 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-20 22:27:12,652 INFO L87 Difference]: Start difference. First operand 100 states and 109 transitions. Second operand 3 states. [2018-01-20 22:27:12,688 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:27:12,689 INFO L93 Difference]: Finished difference Result 205 states and 225 transitions. [2018-01-20 22:27:12,689 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-01-20 22:27:12,689 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 43 [2018-01-20 22:27:12,689 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:27:12,690 INFO L225 Difference]: With dead ends: 205 [2018-01-20 22:27:12,690 INFO L226 Difference]: Without dead ends: 152 [2018-01-20 22:27:12,690 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-20 22:27:12,690 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 152 states. [2018-01-20 22:27:12,694 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 152 to 118. [2018-01-20 22:27:12,694 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 118 states. [2018-01-20 22:27:12,695 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 118 states to 118 states and 129 transitions. [2018-01-20 22:27:12,695 INFO L78 Accepts]: Start accepts. Automaton has 118 states and 129 transitions. Word has length 43 [2018-01-20 22:27:12,695 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:27:12,695 INFO L432 AbstractCegarLoop]: Abstraction has 118 states and 129 transitions. [2018-01-20 22:27:12,695 INFO L433 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-01-20 22:27:12,695 INFO L276 IsEmpty]: Start isEmpty. Operand 118 states and 129 transitions. [2018-01-20 22:27:12,696 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2018-01-20 22:27:12,696 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:27:12,696 INFO L322 BasicCegarLoop]: trace histogram [3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 22:27:12,696 INFO L371 AbstractCegarLoop]: === Iteration 5 === [mainErr0EnsuresViolation]=== [2018-01-20 22:27:12,696 INFO L82 PathProgramCache]: Analyzing trace with hash -964477566, now seen corresponding path program 2 times [2018-01-20 22:27:12,696 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:27:12,696 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:27:12,697 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:27:12,697 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:27:12,697 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:27:12,701 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:27:12,702 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:27:13,032 WARN L146 SmtUtils]: Spent 139ms on a formula simplification. DAG size of input: 25 DAG size of output 18 [2018-01-20 22:27:13,704 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 6 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 22:27:13,704 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-20 22:27:13,704 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-20 22:27:13,713 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-01-20 22:27:13,726 INFO L201 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-20 22:27:13,729 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-20 22:27:13,732 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-20 22:27:13,758 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 8 [2018-01-20 22:27:13,760 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-01-20 22:27:13,760 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:27:13,761 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:13,767 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 8 [2018-01-20 22:27:13,768 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-01-20 22:27:13,769 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-20 22:27:13,770 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:13,773 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:13,774 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 2 variables, input treesize:26, output treesize:18 [2018-01-20 22:27:13,796 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 21 treesize of output 16 [2018-01-20 22:27:13,798 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:27:13,799 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 23 [2018-01-20 22:27:13,799 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:27:13,803 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:13,814 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 21 treesize of output 16 [2018-01-20 22:27:13,816 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:27:13,817 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 23 [2018-01-20 22:27:13,817 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-20 22:27:13,821 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:13,828 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:13,828 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 2 variables, input treesize:44, output treesize:36 [2018-01-20 22:27:13,858 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 36 treesize of output 29 [2018-01-20 22:27:13,862 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:27:13,863 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:27:13,864 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:27:13,867 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 37 [2018-01-20 22:27:13,867 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:27:13,873 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:13,889 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 36 treesize of output 29 [2018-01-20 22:27:13,891 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:27:13,892 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:27:13,893 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:27:13,894 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 37 [2018-01-20 22:27:13,895 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-20 22:27:13,916 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:13,923 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:13,923 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 2 variables, input treesize:74, output treesize:36 [2018-01-20 22:27:13,962 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 10 [2018-01-20 22:27:13,964 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 9 [2018-01-20 22:27:13,964 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:27:13,966 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:13,984 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 36 treesize of output 29 [2018-01-20 22:27:13,987 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:27:13,988 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:27:13,989 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:27:13,993 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 37 [2018-01-20 22:27:13,993 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-20 22:27:14,000 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:14,015 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 36 treesize of output 29 [2018-01-20 22:27:14,018 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:27:14,019 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:27:14,019 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:27:14,022 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 37 [2018-01-20 22:27:14,022 INFO L267 ElimStorePlain]: Start of recursive call 7: End of recursive call: and 1 xjuncts. [2018-01-20 22:27:14,028 INFO L267 ElimStorePlain]: Start of recursive call 6: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:14,037 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:14,037 INFO L202 ElimStorePlain]: Needed 7 recursive calls to eliminate 3 variables, input treesize:87, output treesize:45 [2018-01-20 22:27:14,073 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 16 [2018-01-20 22:27:14,076 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 3 [2018-01-20 22:27:14,076 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:27:14,077 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:14,085 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 16 [2018-01-20 22:27:14,086 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 3 [2018-01-20 22:27:14,086 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-20 22:27:14,087 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:14,091 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 2 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:14,091 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 3 variables, input treesize:50, output treesize:11 [2018-01-20 22:27:14,155 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2018-01-20 22:27:14,156 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 3 [2018-01-20 22:27:14,156 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:27:14,157 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:14,160 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:14,160 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:19, output treesize:3 [2018-01-20 22:27:14,188 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2018-01-20 22:27:14,221 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-01-20 22:27:14,221 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [12] imperfect sequences [16] total 24 [2018-01-20 22:27:14,221 INFO L409 AbstractCegarLoop]: Interpolant automaton has 24 states [2018-01-20 22:27:14,221 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2018-01-20 22:27:14,221 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=68, Invalid=484, Unknown=0, NotChecked=0, Total=552 [2018-01-20 22:27:14,222 INFO L87 Difference]: Start difference. First operand 118 states and 129 transitions. Second operand 24 states. [2018-01-20 22:27:15,010 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:27:15,010 INFO L93 Difference]: Finished difference Result 160 states and 173 transitions. [2018-01-20 22:27:15,010 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2018-01-20 22:27:15,010 INFO L78 Accepts]: Start accepts. Automaton has 24 states. Word has length 43 [2018-01-20 22:27:15,010 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:27:15,011 INFO L225 Difference]: With dead ends: 160 [2018-01-20 22:27:15,011 INFO L226 Difference]: Without dead ends: 87 [2018-01-20 22:27:15,011 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 78 GetRequests, 35 SyntacticMatches, 4 SemanticMatches, 39 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 244 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=273, Invalid=1367, Unknown=0, NotChecked=0, Total=1640 [2018-01-20 22:27:15,012 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 87 states. [2018-01-20 22:27:15,014 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 87 to 85. [2018-01-20 22:27:15,014 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 85 states. [2018-01-20 22:27:15,014 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 85 states to 85 states and 93 transitions. [2018-01-20 22:27:15,014 INFO L78 Accepts]: Start accepts. Automaton has 85 states and 93 transitions. Word has length 43 [2018-01-20 22:27:15,014 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:27:15,014 INFO L432 AbstractCegarLoop]: Abstraction has 85 states and 93 transitions. [2018-01-20 22:27:15,015 INFO L433 AbstractCegarLoop]: Interpolant automaton has 24 states. [2018-01-20 22:27:15,015 INFO L276 IsEmpty]: Start isEmpty. Operand 85 states and 93 transitions. [2018-01-20 22:27:15,015 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 49 [2018-01-20 22:27:15,015 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:27:15,015 INFO L322 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 22:27:15,015 INFO L371 AbstractCegarLoop]: === Iteration 6 === [mainErr0EnsuresViolation]=== [2018-01-20 22:27:15,015 INFO L82 PathProgramCache]: Analyzing trace with hash -1503871304, now seen corresponding path program 1 times [2018-01-20 22:27:15,015 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:27:15,015 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:27:15,016 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:27:15,016 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-01-20 22:27:15,016 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:27:15,022 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:27:15,023 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:27:15,389 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 22:27:15,389 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-20 22:27:15,405 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-20 22:27:15,409 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:27:15,426 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:27:15,428 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-20 22:27:15,430 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-20 22:27:15,430 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-20 22:27:15,431 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:15,431 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:6, output treesize:5 [2018-01-20 22:27:15,467 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:27:15,468 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:27:15,468 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 4 [2018-01-20 22:27:15,469 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-20 22:27:15,473 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:15,473 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:23, output treesize:17 [2018-01-20 22:27:15,491 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 8 [2018-01-20 22:27:15,493 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-01-20 22:27:15,493 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:27:15,494 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:15,502 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 8 [2018-01-20 22:27:15,504 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-01-20 22:27:15,504 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-20 22:27:15,505 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:15,511 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 2 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:15,511 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 3 variables, input treesize:36, output treesize:25 [2018-01-20 22:27:15,556 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:27:15,560 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 30 [2018-01-20 22:27:15,562 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 13 [2018-01-20 22:27:15,562 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:27:15,567 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:15,579 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:27:15,582 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 43 treesize of output 47 [2018-01-20 22:27:15,585 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 13 [2018-01-20 22:27:15,585 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-20 22:27:15,590 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:15,600 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 2 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-20 22:27:15,600 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 3 variables, input treesize:67, output treesize:51 [2018-01-20 22:27:15,634 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 28 treesize of output 26 [2018-01-20 22:27:15,637 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 3 [2018-01-20 22:27:15,637 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:27:15,642 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 1 [2018-01-20 22:27:15,643 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-20 22:27:15,644 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:15,651 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-20 22:27:15,651 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 2 variables, input treesize:59, output treesize:35 [2018-01-20 22:27:15,707 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 40 treesize of output 31 [2018-01-20 22:27:15,710 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 17 [2018-01-20 22:27:15,710 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:27:15,715 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:15,735 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-20 22:27:15,736 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:46, output treesize:38 [2018-01-20 22:27:15,779 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:27:15,783 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 42 treesize of output 41 [2018-01-20 22:27:15,785 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:27:15,786 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 14 [2018-01-20 22:27:15,786 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:27:15,792 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:15,797 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:15,798 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:48, output treesize:25 [2018-01-20 22:27:15,826 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 66 treesize of output 56 [2018-01-20 22:27:15,828 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 26 treesize of output 11 [2018-01-20 22:27:15,828 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:27:15,833 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:15,839 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 12 [2018-01-20 22:27:15,840 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 11 [2018-01-20 22:27:15,840 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-20 22:27:15,842 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:15,845 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:27:15,846 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 2 variables, input treesize:66, output treesize:31 Received shutdown request... [2018-01-20 22:27:15,896 INFO L175 TraceCheckSpWp]: Timeout while computing interpolants [2018-01-20 22:27:15,896 WARN L491 AbstractCegarLoop]: Verification canceled [2018-01-20 22:27:15,898 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 20.01 10:27:15 BoogieIcfgContainer [2018-01-20 22:27:15,898 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-01-20 22:27:15,899 INFO L168 Benchmark]: Toolchain (without parser) took 50564.17 ms. Allocated memory was 296.7 MB in the beginning and 969.4 MB in the end (delta: 672.7 MB). Free memory was 255.1 MB in the beginning and 871.7 MB in the end (delta: -616.6 MB). Peak memory consumption was 56.1 MB. Max. memory is 5.3 GB. [2018-01-20 22:27:15,900 INFO L168 Benchmark]: CDTParser took 0.14 ms. Allocated memory is still 296.7 MB. Free memory is still 261.0 MB. There was no memory consumed. Max. memory is 5.3 GB. [2018-01-20 22:27:15,900 INFO L168 Benchmark]: CACSL2BoogieTranslator took 220.48 ms. Allocated memory is still 296.7 MB. Free memory was 254.1 MB in the beginning and 242.1 MB in the end (delta: 12.0 MB). Peak memory consumption was 12.0 MB. Max. memory is 5.3 GB. [2018-01-20 22:27:15,901 INFO L168 Benchmark]: Boogie Preprocessor took 39.99 ms. Allocated memory is still 296.7 MB. Free memory was 242.1 MB in the beginning and 240.1 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 5.3 GB. [2018-01-20 22:27:15,901 INFO L168 Benchmark]: RCFGBuilder took 391.98 ms. Allocated memory is still 296.7 MB. Free memory was 240.1 MB in the beginning and 217.4 MB in the end (delta: 22.7 MB). Peak memory consumption was 22.7 MB. Max. memory is 5.3 GB. [2018-01-20 22:27:15,901 INFO L168 Benchmark]: TraceAbstraction took 49903.92 ms. Allocated memory was 296.7 MB in the beginning and 969.4 MB in the end (delta: 672.7 MB). Free memory was 217.4 MB in the beginning and 871.7 MB in the end (delta: -654.2 MB). Peak memory consumption was 18.4 MB. Max. memory is 5.3 GB. [2018-01-20 22:27:15,903 INFO L344 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.14 ms. Allocated memory is still 296.7 MB. Free memory is still 261.0 MB. There was no memory consumed. Max. memory is 5.3 GB. * CACSL2BoogieTranslator took 220.48 ms. Allocated memory is still 296.7 MB. Free memory was 254.1 MB in the beginning and 242.1 MB in the end (delta: 12.0 MB). Peak memory consumption was 12.0 MB. Max. memory is 5.3 GB. * Boogie Preprocessor took 39.99 ms. Allocated memory is still 296.7 MB. Free memory was 242.1 MB in the beginning and 240.1 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 5.3 GB. * RCFGBuilder took 391.98 ms. Allocated memory is still 296.7 MB. Free memory was 240.1 MB in the beginning and 217.4 MB in the end (delta: 22.7 MB). Peak memory consumption was 22.7 MB. Max. memory is 5.3 GB. * TraceAbstraction took 49903.92 ms. Allocated memory was 296.7 MB in the beginning and 969.4 MB in the end (delta: 672.7 MB). Free memory was 217.4 MB in the beginning and 871.7 MB in the end (delta: -654.2 MB). Peak memory consumption was 18.4 MB. Max. memory is 5.3 GB. * Results from de.uni_freiburg.informatik.ultimate.boogie.preprocessor: - GenericResult: Unfinished Backtranslation Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) - GenericResult: Unfinished Backtranslation Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) - GenericResult: Unfinished Backtranslation Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) - GenericResult: Unfinished Backtranslation Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - CounterExampleResult [Line: 1]: not all allocated memory was freed not all allocated memory was freed We found a FailurePath: - StatisticsResult: Ultimate Automizer benchmark data for error location: ULTIMATE.initErr0EnsuresViolation CFG has 3 procedures, 69 locations, 3 error locations. UNSAFE Result, 0.1s OverallTime, 1 OverallIterations, 1 TraceHistogramMax, 0.0s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: No data available, PredicateUnifierStatistics: No data available, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=69occurred in iteration=0, 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, AutomataMinimizationStatistics: No data available, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.0s SatisfiabilityAnalysisTime, 0.0s InterpolantComputationTime, 3 NumberOfCodeBlocks, 3 NumberOfCodeBlocksAsserted, 1 NumberOfCheckSat, 0 ConstructedInterpolants, 0 QuantifiedInterpolants, 0 SizeOfPredicates, 0 NumberOfNonLiveVariables, 0 ConjunctsInSsa, 0 ConjunctsInUnsatCore, 0 InterpolantComputations, 0 PerfectInterpolantSequences, 0/0 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, REUSE_STATISTICS: No data available - CounterExampleResult [Line: 1]: not all allocated memory was freed not all allocated memory was freed We found a FailurePath: [L986] EXPR, FCALL malloc(sizeof(SLL)) VAL [malloc(sizeof(SLL))={17:0}] [L986] SLL* head = malloc(sizeof(SLL)); VAL [head={17:0}, malloc(sizeof(SLL))={17:0}] [L987] FCALL head->next = head VAL [head={17:0}, malloc(sizeof(SLL))={17:0}] [L988] FCALL head->prev = ((void*)0) VAL [head={17:0}, malloc(sizeof(SLL))={17:0}] [L989] FCALL head->data = 0 VAL [head={17:0}, malloc(sizeof(SLL))={17:0}] [L991] SLL* x = head; [L992] int state = 1; VAL [head={17:0}, malloc(sizeof(SLL))={17:0}, state=1, x={17:0}] [L995] COND TRUE __VERIFIER_nondet_int() [L998] EXPR, FCALL malloc(sizeof(SLL)) VAL [head={17:0}, malloc(sizeof(SLL))={13:0}, malloc(sizeof(SLL))={17:0}, state=1, x={17:0}] [L998] FCALL x->next = malloc(sizeof(SLL)) VAL [head={17:0}, malloc(sizeof(SLL))={13:0}, malloc(sizeof(SLL))={17:0}, state=1, x={17:0}] [L999] EXPR, FCALL x->next VAL [head={17:0}, malloc(sizeof(SLL))={13:0}, malloc(sizeof(SLL))={17:0}, state=1, x={17:0}, x->next={13:0}] [L999] FCALL x->next->prev = x VAL [head={17:0}, malloc(sizeof(SLL))={13:0}, malloc(sizeof(SLL))={17:0}, state=1, x={17:0}, x->next={13:0}] [L1000] EXPR, FCALL x->next VAL [head={17:0}, malloc(sizeof(SLL))={13:0}, malloc(sizeof(SLL))={17:0}, state=1, x={17:0}, x->next={13:0}] [L1000] x = x->next [L1001] FCALL x->next = head VAL [head={17:0}, malloc(sizeof(SLL))={13:0}, malloc(sizeof(SLL))={17:0}, state=1, x={13:0}] [L1003] COND FALSE !(__VERIFIER_nondet_int()) [L1013] FCALL x->data = state VAL [head={17:0}, malloc(sizeof(SLL))={13:0}, malloc(sizeof(SLL))={17:0}, state=1, x={13:0}] [L1015] COND FALSE !(!(((void*)0) != x)) VAL [head={17:0}, malloc(sizeof(SLL))={13:0}, malloc(sizeof(SLL))={17:0}, state=1, x={13:0}] [L1015] COND FALSE !(0) VAL [head={17:0}, malloc(sizeof(SLL))={13:0}, malloc(sizeof(SLL))={17:0}, state=1, x={13:0}] [L995] COND FALSE !(__VERIFIER_nondet_int()) [L1017] FCALL x->data = state VAL [head={17:0}, malloc(sizeof(SLL))={13:0}, malloc(sizeof(SLL))={17:0}, state=1, x={13:0}] [L1019] EXPR, FCALL head->next VAL [head={17:0}, head->next={13:0}, malloc(sizeof(SLL))={13:0}, malloc(sizeof(SLL))={17:0}, state=1, x={13:0}] [L1019] x = head->next [L1020] COND FALSE !(!(((void*)0) != x)) VAL [head={17:0}, malloc(sizeof(SLL))={13:0}, malloc(sizeof(SLL))={17:0}, state=1, x={13:0}] [L1020] COND FALSE !(0) VAL [head={17:0}, malloc(sizeof(SLL))={13:0}, malloc(sizeof(SLL))={17:0}, state=1, x={13:0}] [L1022] EXPR, FCALL x->data VAL [head={17:0}, malloc(sizeof(SLL))={13:0}, malloc(sizeof(SLL))={17:0}, state=1, x={13:0}, x->data=1] [L1022] COND TRUE x->data != 0 [L1024] EXPR, FCALL x->next VAL [head={17:0}, malloc(sizeof(SLL))={13:0}, malloc(sizeof(SLL))={17:0}, state=1, x={13:0}, x->next={17:0}] [L1024] EXPR, FCALL x->next->data VAL [head={17:0}, malloc(sizeof(SLL))={13:0}, malloc(sizeof(SLL))={17:0}, state=1, x={13:0}, x->next={17:0}, x->next->data=0] [L1024] EXPR x->next->data == 0 || x->data <= x->next->data VAL [head={17:0}, malloc(sizeof(SLL))={13:0}, malloc(sizeof(SLL))={17:0}, state=1, x={13:0}, x->next={17:0}, x->next->data=0, x->next->data == 0 || x->data <= x->next->data=1] [L1024] COND FALSE !(!(x->next->data == 0 || x->data <= x->next->data)) [L1024] COND FALSE !(0) VAL [head={17:0}, malloc(sizeof(SLL))={13:0}, malloc(sizeof(SLL))={17:0}, state=1, x={13:0}] [L1025] EXPR, FCALL x->next VAL [head={17:0}, malloc(sizeof(SLL))={13:0}, malloc(sizeof(SLL))={17:0}, state=1, x={13:0}, x->next={17:0}] [L1025] x = x->next [L1022] EXPR, FCALL x->data VAL [head={17:0}, malloc(sizeof(SLL))={13:0}, malloc(sizeof(SLL))={17:0}, state=1, x={17:0}, x->data=0] [L1022] COND FALSE !(x->data != 0) [L1028] EXPR, FCALL head->next VAL [head={17:0}, head->next={13:0}, malloc(sizeof(SLL))={13:0}, malloc(sizeof(SLL))={17:0}, state=1, x={17:0}] [L1028] x = head->next [L1030] EXPR, FCALL x->data VAL [head={17:0}, malloc(sizeof(SLL))={13:0}, malloc(sizeof(SLL))={17:0}, state=1, x={13:0}, x->data=1] [L1030] COND TRUE x->data != 0 [L1032] head = x VAL [head={13:0}, malloc(sizeof(SLL))={13:0}, malloc(sizeof(SLL))={17:0}, state=1, x={13:0}] [L1033] EXPR, FCALL x->next VAL [head={13:0}, malloc(sizeof(SLL))={13:0}, malloc(sizeof(SLL))={17:0}, state=1, x={13:0}, x->next={17:0}] [L1033] x = x->next [L1034] FCALL free(head) VAL [head={13:0}, malloc(sizeof(SLL))={13:0}, malloc(sizeof(SLL))={17:0}, state=1, x={17:0}] [L1030] EXPR, FCALL x->data VAL [head={13:0}, malloc(sizeof(SLL))={13:0}, malloc(sizeof(SLL))={17:0}, state=1, x={17:0}, x->data=0] [L1030] COND FALSE !(x->data != 0) [L1036] FCALL free(x) VAL [head={13:0}, malloc(sizeof(SLL))={13:0}, malloc(sizeof(SLL))={17:0}, state=1, x={17:0}] [L1038] return 0; - StatisticsResult: Ultimate Automizer benchmark data for error location: ULTIMATE.startErr0EnsuresViolation CFG has 3 procedures, 69 locations, 3 error locations. UNSAFE Result, 44.0s OverallTime, 13 OverallIterations, 3 TraceHistogramMax, 20.0s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 784 SDtfs, 5133 SDslu, 7099 SDs, 0 SdLazy, 6818 SolverSat, 802 SolverUnsat, 171 SolverUnknown, 0 SolverNotchecked, 6.0s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 715 GetRequests, 259 SyntacticMatches, 53 SemanticMatches, 403 ConstructedPredicates, 4 IntricatePredicates, 0 DeprecatedPredicates, 5017 ImplicationChecksByTransitivity, 29.2s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=212occurred in iteration=12, 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, AutomataMinimizationStatistics: 0.1s AutomataMinimizationTime, 12 MinimizatonAttempts, 584 StatesRemovedByMinimization, 11 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.3s SatisfiabilityAnalysisTime, 22.9s InterpolantComputationTime, 1012 NumberOfCodeBlocks, 1012 NumberOfCodeBlocksAsserted, 21 NumberOfCheckSat, 926 ConstructedInterpolants, 77 QuantifiedInterpolants, 1540092 SizeOfPredicates, 107 NumberOfNonLiveVariables, 982 ConjunctsInSsa, 311 ConjunctsInUnsatCore, 18 InterpolantComputations, 6 PerfectInterpolantSequences, 48/135 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, REUSE_STATISTICS: No data available - TimeoutResultAtElement [Line: 983]: Timeout (TraceAbstraction) Unable to prove that all allocated memory was freed (line 983). Cancelled while BasicCegarLoop was analyzing trace of length 49 with TraceHistMax 2, while TraceCheckSpWp was constructing forward predicates, while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 20. - StatisticsResult: Ultimate Automizer benchmark data for error location: mainErr0EnsuresViolation CFG has 3 procedures, 69 locations, 3 error locations. TIMEOUT Result, 5.6s OverallTime, 6 OverallIterations, 3 TraceHistogramMax, 1.8s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 287 SDtfs, 936 SDslu, 1636 SDs, 0 SdLazy, 1197 SolverSat, 100 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.6s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 174 GetRequests, 68 SyntacticMatches, 12 SemanticMatches, 94 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 586 ImplicationChecksByTransitivity, 3.0s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=118occurred in iteration=4, 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, AutomataMinimizationStatistics: 0.0s AutomataMinimizationTime, 5 MinimizatonAttempts, 62 StatesRemovedByMinimization, 4 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.0s SatisfiabilityAnalysisTime, 2.7s InterpolantComputationTime, 257 NumberOfCodeBlocks, 245 NumberOfCodeBlocksAsserted, 7 NumberOfCheckSat, 250 ConstructedInterpolants, 5 QuantifiedInterpolants, 111412 SizeOfPredicates, 25 NumberOfNonLiveVariables, 225 ConjunctsInSsa, 72 ConjunctsInUnsatCore, 7 InterpolantComputations, 4 PerfectInterpolantSequences, 18/30 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, REUSE_STATISTICS: No data available RESULT: Ultimate proved your program to be incorrect! Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/dll-circular_true-unreach-call_true-valid-memsafety.i_mempurity-32bit-Automizer_Camel+AI_EQ.epf_AutomizerC.xml/Csv-Benchmark-0-2018-01-20_22-27-15-909.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/dll-circular_true-unreach-call_true-valid-memsafety.i_mempurity-32bit-Automizer_Camel+AI_EQ.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-0-2018-01-20_22-27-15-909.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/dll-circular_true-unreach-call_true-valid-memsafety.i_mempurity-32bit-Automizer_Camel+AI_EQ.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-1-2018-01-20_22-27-15-909.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/dll-circular_true-unreach-call_true-valid-memsafety.i_mempurity-32bit-Automizer_Camel+AI_EQ.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-2-2018-01-20_22-27-15-909.csv Completed graceful shutdown