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-rb-sentinel_true-unreach-call_true-valid-memsafety.i -------------------------------------------------------------------------------- This is Ultimate 0.1.23-47db877 [2018-01-23 14:54:09,716 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-01-23 14:54:09,718 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-01-23 14:54:09,733 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-01-23 14:54:09,733 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-01-23 14:54:09,734 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-01-23 14:54:09,735 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-01-23 14:54:09,737 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-01-23 14:54:09,739 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-01-23 14:54:09,740 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-01-23 14:54:09,740 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-01-23 14:54:09,741 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-01-23 14:54:09,742 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-01-23 14:54:09,743 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-01-23 14:54:09,744 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-01-23 14:54:09,746 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-01-23 14:54:09,748 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-01-23 14:54:09,750 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-01-23 14:54:09,752 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-01-23 14:54:09,753 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-01-23 14:54:09,755 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-01-23 14:54:09,756 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-01-23 14:54:09,756 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-01-23 14:54:09,757 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-01-23 14:54:09,758 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-01-23 14:54:09,759 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-01-23 14:54:09,759 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-01-23 14:54:09,760 INFO L177 SettingsManager]: PEA to Boogie provides no preferences, ignoring... [2018-01-23 14:54:09,760 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-01-23 14:54:09,760 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-01-23 14:54:09,761 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-01-23 14:54:09,761 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-23 14:54:09,770 INFO L110 SettingsManager]: Loading preferences was successful [2018-01-23 14:54:09,770 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-01-23 14:54:09,771 INFO L131 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2018-01-23 14:54:09,771 INFO L133 SettingsManager]: * to procedures, called more than once=true [2018-01-23 14:54:09,771 INFO L131 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2018-01-23 14:54:09,771 INFO L133 SettingsManager]: * Abstract domain for RCFG-of-the-future=VPDomain [2018-01-23 14:54:09,771 INFO L133 SettingsManager]: * Use the RCFG-of-the-future interface=true [2018-01-23 14:54:09,772 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-01-23 14:54:09,772 INFO L133 SettingsManager]: * sizeof long=4 [2018-01-23 14:54:09,772 INFO L133 SettingsManager]: * Check unreachability of error function in SV-COMP mode=false [2018-01-23 14:54:09,772 INFO L133 SettingsManager]: * Check allocation purity=true [2018-01-23 14:54:09,772 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-01-23 14:54:09,772 INFO L133 SettingsManager]: * sizeof POINTER=4 [2018-01-23 14:54:09,773 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-01-23 14:54:09,773 INFO L133 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2018-01-23 14:54:09,773 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-01-23 14:54:09,773 INFO L133 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2018-01-23 14:54:09,773 INFO L133 SettingsManager]: * sizeof long double=12 [2018-01-23 14:54:09,773 INFO L133 SettingsManager]: * Check if freed pointer was valid=false [2018-01-23 14:54:09,773 INFO L133 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2018-01-23 14:54:09,774 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-01-23 14:54:09,774 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-01-23 14:54:09,774 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-01-23 14:54:09,774 INFO L133 SettingsManager]: * Add additional assume for each assert=false [2018-01-23 14:54:09,774 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-01-23 14:54:09,775 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-01-23 14:54:09,775 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-01-23 14:54:09,775 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-01-23 14:54:09,775 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-01-23 14:54:09,775 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-01-23 14:54:09,775 INFO L133 SettingsManager]: * Stop after first violation was found=false [2018-01-23 14:54:09,775 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-01-23 14:54:09,775 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-01-23 14:54:09,776 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-01-23 14:54:09,776 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-01-23 14:54:09,776 INFO L131 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2018-01-23 14:54:09,776 INFO L133 SettingsManager]: * TransformationType=HEAP_SEPARATOR [2018-01-23 14:54:09,809 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-01-23 14:54:09,820 INFO L266 ainManager$Toolchain]: [Toolchain 1]: Parser(s) successfully initialized [2018-01-23 14:54:09,823 INFO L222 ainManager$Toolchain]: [Toolchain 1]: Toolchain data selected. [2018-01-23 14:54:09,824 INFO L271 PluginConnector]: Initializing CDTParser... [2018-01-23 14:54:09,825 INFO L276 PluginConnector]: CDTParser initialized [2018-01-23 14:54:09,825 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/forester-heap/dll-rb-sentinel_true-unreach-call_true-valid-memsafety.i [2018-01-23 14:54:10,004 INFO L304 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-01-23 14:54:10,010 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2018-01-23 14:54:10,010 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2018-01-23 14:54:10,010 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2018-01-23 14:54:10,015 INFO L276 PluginConnector]: CACSL2BoogieTranslator initialized [2018-01-23 14:54:10,016 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 23.01 02:54:09" (1/1) ... [2018-01-23 14:54:10,019 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@6b83b4c1 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.01 02:54:10, skipping insertion in model container [2018-01-23 14:54:10,019 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 23.01 02:54:09" (1/1) ... [2018-01-23 14:54:10,038 INFO L153 Dispatcher]: Using SV-COMP mode [2018-01-23 14:54:10,080 INFO L153 Dispatcher]: Using SV-COMP mode [2018-01-23 14:54:10,200 INFO L450 PostProcessor]: Settings: Checked method=main [2018-01-23 14:54:10,228 INFO L450 PostProcessor]: Settings: Checked method=main [2018-01-23 14:54:10,235 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.01 02:54:10 WrapperNode [2018-01-23 14:54:10,235 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2018-01-23 14:54:10,235 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-01-23 14:54:10,235 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-01-23 14:54:10,235 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-01-23 14:54:10,250 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.01 02:54:10" (1/1) ... [2018-01-23 14:54:10,251 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.01 02:54:10" (1/1) ... [2018-01-23 14:54:10,263 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.01 02:54:10" (1/1) ... [2018-01-23 14:54:10,263 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.01 02:54:10" (1/1) ... [2018-01-23 14:54:10,270 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.01 02:54:10" (1/1) ... [2018-01-23 14:54:10,276 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.01 02:54:10" (1/1) ... [2018-01-23 14:54:10,278 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.01 02:54:10" (1/1) ... [2018-01-23 14:54:10,281 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-01-23 14:54:10,281 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-01-23 14:54:10,281 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-01-23 14:54:10,282 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-01-23 14:54:10,282 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.01 02:54:10" (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-23 14:54:10,329 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2018-01-23 14:54:10,329 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-01-23 14:54:10,329 INFO L136 BoogieDeclarations]: Found implementation of procedure main [2018-01-23 14:54:10,329 INFO L128 BoogieDeclarations]: Found specification of procedure write~int [2018-01-23 14:54:10,329 INFO L128 BoogieDeclarations]: Found specification of procedure read~int [2018-01-23 14:54:10,330 INFO L128 BoogieDeclarations]: Found specification of procedure write~$Pointer$ [2018-01-23 14:54:10,330 INFO L128 BoogieDeclarations]: Found specification of procedure read~$Pointer$ [2018-01-23 14:54:10,330 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.free [2018-01-23 14:54:10,330 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2018-01-23 14:54:10,330 INFO L128 BoogieDeclarations]: Found specification of procedure #Ultimate.alloc [2018-01-23 14:54:10,330 INFO L128 BoogieDeclarations]: Found specification of procedure malloc [2018-01-23 14:54:10,331 INFO L128 BoogieDeclarations]: Found specification of procedure free [2018-01-23 14:54:10,331 INFO L128 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2018-01-23 14:54:10,331 INFO L128 BoogieDeclarations]: Found specification of procedure __VERIFIER_error [2018-01-23 14:54:10,331 INFO L128 BoogieDeclarations]: Found specification of procedure main [2018-01-23 14:54:10,331 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2018-01-23 14:54:10,331 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-01-23 14:54:10,745 INFO L257 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-01-23 14:54:10,746 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 23.01 02:54:10 BoogieIcfgContainer [2018-01-23 14:54:10,746 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-01-23 14:54:10,747 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-01-23 14:54:10,747 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-01-23 14:54:10,750 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-01-23 14:54:10,750 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 23.01 02:54:09" (1/3) ... [2018-01-23 14:54:10,751 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@75d181e9 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 23.01 02:54:10, skipping insertion in model container [2018-01-23 14:54:10,751 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.01 02:54:10" (2/3) ... [2018-01-23 14:54:10,752 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@75d181e9 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 23.01 02:54:10, skipping insertion in model container [2018-01-23 14:54:10,752 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 23.01 02:54:10" (3/3) ... [2018-01-23 14:54:10,753 INFO L105 eAbstractionObserver]: Analyzing ICFG dll-rb-sentinel_true-unreach-call_true-valid-memsafety.i [2018-01-23 14:54:10,759 INFO L130 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-01-23 14:54:10,765 INFO L142 ceAbstractionStarter]: Appying trace abstraction to program that has 3 error locations. [2018-01-23 14:54:10,800 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-23 14:54:10,800 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-23 14:54:10,800 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-23 14:54:10,801 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-23 14:54:10,801 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-23 14:54:10,801 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-23 14:54:10,801 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-23 14:54:10,801 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == ULTIMATE.initErr0EnsuresViolation======== [2018-01-23 14:54:10,802 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-23 14:54:10,823 INFO L276 IsEmpty]: Start isEmpty. Operand 97 states. [2018-01-23 14:54:10,827 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 4 [2018-01-23 14:54:10,827 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:54:10,828 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1] [2018-01-23 14:54:10,828 INFO L371 AbstractCegarLoop]: === Iteration 1 === [ULTIMATE.initErr0EnsuresViolation]=== [2018-01-23 14:54:10,831 INFO L82 PathProgramCache]: Analyzing trace with hash 267889, now seen corresponding path program 1 times [2018-01-23 14:54:10,833 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:54:10,833 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:54:10,876 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:54:10,876 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:54:10,876 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:54:10,904 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2018-01-23 14:54:10,911 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2018-01-23 14:54:10,930 INFO L381 BasicCegarLoop]: Counterexample might be feasible [2018-01-23 14:54:10,935 WARN L343 cessorBacktranslator]: Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) [2018-01-23 14:54:10,940 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-23 14:54:10,940 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-23 14:54:10,940 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-23 14:54:10,940 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-23 14:54:10,940 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-23 14:54:10,941 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-23 14:54:10,941 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-23 14:54:10,941 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == ULTIMATE.startErr0EnsuresViolation======== [2018-01-23 14:54:10,941 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-23 14:54:10,944 INFO L276 IsEmpty]: Start isEmpty. Operand 97 states. [2018-01-23 14:54:10,946 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2018-01-23 14:54:10,946 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:54:10,946 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] [2018-01-23 14:54:10,946 INFO L371 AbstractCegarLoop]: === Iteration 1 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-23 14:54:10,947 INFO L82 PathProgramCache]: Analyzing trace with hash 2122179741, now seen corresponding path program 1 times [2018-01-23 14:54:10,947 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:54:10,947 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:54:10,948 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:54:10,948 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:54:10,948 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:54:10,978 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:54:10,989 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:54:11,128 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-23 14:54:11,130 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-23 14:54:11,131 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-01-23 14:54:11,132 INFO L409 AbstractCegarLoop]: Interpolant automaton has 2 states [2018-01-23 14:54:11,141 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2018-01-23 14:54:11,142 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-01-23 14:54:11,144 INFO L87 Difference]: Start difference. First operand 97 states. Second operand 2 states. [2018-01-23 14:54:11,167 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:54:11,167 INFO L93 Difference]: Finished difference Result 177 states and 235 transitions. [2018-01-23 14:54:11,168 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2018-01-23 14:54:11,169 INFO L78 Accepts]: Start accepts. Automaton has 2 states. Word has length 27 [2018-01-23 14:54:11,169 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:54:11,180 INFO L225 Difference]: With dead ends: 177 [2018-01-23 14:54:11,180 INFO L226 Difference]: Without dead ends: 94 [2018-01-23 14:54:11,182 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-23 14:54:11,195 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 94 states. [2018-01-23 14:54:11,212 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 94 to 94. [2018-01-23 14:54:11,213 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 94 states. [2018-01-23 14:54:11,215 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 94 states to 94 states and 99 transitions. [2018-01-23 14:54:11,217 INFO L78 Accepts]: Start accepts. Automaton has 94 states and 99 transitions. Word has length 27 [2018-01-23 14:54:11,217 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:54:11,217 INFO L432 AbstractCegarLoop]: Abstraction has 94 states and 99 transitions. [2018-01-23 14:54:11,217 INFO L433 AbstractCegarLoop]: Interpolant automaton has 2 states. [2018-01-23 14:54:11,218 INFO L276 IsEmpty]: Start isEmpty. Operand 94 states and 99 transitions. [2018-01-23 14:54:11,219 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2018-01-23 14:54:11,219 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:54:11,220 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] [2018-01-23 14:54:11,220 INFO L371 AbstractCegarLoop]: === Iteration 2 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-23 14:54:11,220 INFO L82 PathProgramCache]: Analyzing trace with hash 798686160, now seen corresponding path program 1 times [2018-01-23 14:54:11,220 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:54:11,220 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:54:11,222 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:54:11,222 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:54:11,222 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:54:11,252 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:54:11,253 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:54:11,377 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-23 14:54:11,377 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-23 14:54:11,377 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2018-01-23 14:54:11,379 INFO L409 AbstractCegarLoop]: Interpolant automaton has 8 states [2018-01-23 14:54:11,380 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2018-01-23 14:54:11,380 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=43, Unknown=0, NotChecked=0, Total=56 [2018-01-23 14:54:11,380 INFO L87 Difference]: Start difference. First operand 94 states and 99 transitions. Second operand 8 states. [2018-01-23 14:54:11,718 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:54:11,719 INFO L93 Difference]: Finished difference Result 155 states and 168 transitions. [2018-01-23 14:54:11,719 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-01-23 14:54:11,719 INFO L78 Accepts]: Start accepts. Automaton has 8 states. Word has length 36 [2018-01-23 14:54:11,719 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:54:11,723 INFO L225 Difference]: With dead ends: 155 [2018-01-23 14:54:11,723 INFO L226 Difference]: Without dead ends: 135 [2018-01-23 14:54:11,725 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 14 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=63, Invalid=119, Unknown=0, NotChecked=0, Total=182 [2018-01-23 14:54:11,725 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 135 states. [2018-01-23 14:54:11,736 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 135 to 96. [2018-01-23 14:54:11,736 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 96 states. [2018-01-23 14:54:11,738 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 96 states to 96 states and 101 transitions. [2018-01-23 14:54:11,738 INFO L78 Accepts]: Start accepts. Automaton has 96 states and 101 transitions. Word has length 36 [2018-01-23 14:54:11,739 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:54:11,739 INFO L432 AbstractCegarLoop]: Abstraction has 96 states and 101 transitions. [2018-01-23 14:54:11,739 INFO L433 AbstractCegarLoop]: Interpolant automaton has 8 states. [2018-01-23 14:54:11,739 INFO L276 IsEmpty]: Start isEmpty. Operand 96 states and 101 transitions. [2018-01-23 14:54:11,741 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2018-01-23 14:54:11,741 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:54:11,741 INFO L322 BasicCegarLoop]: trace histogram [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] [2018-01-23 14:54:11,741 INFO L371 AbstractCegarLoop]: === Iteration 3 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-23 14:54:11,741 INFO L82 PathProgramCache]: Analyzing trace with hash -611659746, now seen corresponding path program 1 times [2018-01-23 14:54:11,742 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:54:11,742 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:54:11,743 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:54:11,744 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:54:11,744 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:54:11,768 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:54:11,769 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:54:11,879 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-01-23 14:54:11,879 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-23 14:54:11,879 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2018-01-23 14:54:11,880 INFO L409 AbstractCegarLoop]: Interpolant automaton has 8 states [2018-01-23 14:54:11,880 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2018-01-23 14:54:11,880 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=43, Unknown=0, NotChecked=0, Total=56 [2018-01-23 14:54:11,880 INFO L87 Difference]: Start difference. First operand 96 states and 101 transitions. Second operand 8 states. [2018-01-23 14:54:12,122 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:54:12,123 INFO L93 Difference]: Finished difference Result 132 states and 140 transitions. [2018-01-23 14:54:12,123 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-01-23 14:54:12,123 INFO L78 Accepts]: Start accepts. Automaton has 8 states. Word has length 42 [2018-01-23 14:54:12,124 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:54:12,126 INFO L225 Difference]: With dead ends: 132 [2018-01-23 14:54:12,126 INFO L226 Difference]: Without dead ends: 126 [2018-01-23 14:54:12,126 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 14 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=64, Invalid=118, Unknown=0, NotChecked=0, Total=182 [2018-01-23 14:54:12,127 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 126 states. [2018-01-23 14:54:12,134 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 126 to 98. [2018-01-23 14:54:12,134 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 98 states. [2018-01-23 14:54:12,136 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 98 states to 98 states and 103 transitions. [2018-01-23 14:54:12,136 INFO L78 Accepts]: Start accepts. Automaton has 98 states and 103 transitions. Word has length 42 [2018-01-23 14:54:12,136 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:54:12,136 INFO L432 AbstractCegarLoop]: Abstraction has 98 states and 103 transitions. [2018-01-23 14:54:12,137 INFO L433 AbstractCegarLoop]: Interpolant automaton has 8 states. [2018-01-23 14:54:12,137 INFO L276 IsEmpty]: Start isEmpty. Operand 98 states and 103 transitions. [2018-01-23 14:54:12,138 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2018-01-23 14:54:12,139 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:54:12,139 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-23 14:54:12,139 INFO L371 AbstractCegarLoop]: === Iteration 4 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-23 14:54:12,139 INFO L82 PathProgramCache]: Analyzing trace with hash 1884398603, now seen corresponding path program 1 times [2018-01-23 14:54:12,139 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:54:12,139 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:54:12,141 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:54:12,141 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:54:12,141 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:54:12,169 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2018-01-23 14:54:12,192 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2018-01-23 14:54:12,206 INFO L381 BasicCegarLoop]: Counterexample might be feasible [2018-01-23 14:54:12,217 WARN L343 cessorBacktranslator]: Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) [2018-01-23 14:54:12,228 WARN L343 cessorBacktranslator]: Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) [2018-01-23 14:54:12,228 WARN L343 cessorBacktranslator]: Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) [2018-01-23 14:54:12,246 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-23 14:54:12,246 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-23 14:54:12,246 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-23 14:54:12,246 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-23 14:54:12,247 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-23 14:54:12,247 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-23 14:54:12,247 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-23 14:54:12,247 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == mainErr0EnsuresViolation======== [2018-01-23 14:54:12,247 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-23 14:54:12,249 INFO L276 IsEmpty]: Start isEmpty. Operand 97 states. [2018-01-23 14:54:12,251 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2018-01-23 14:54:12,251 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:54:12,251 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-23 14:54:12,251 INFO L371 AbstractCegarLoop]: === Iteration 1 === [mainErr0EnsuresViolation]=== [2018-01-23 14:54:12,252 INFO L82 PathProgramCache]: Analyzing trace with hash 1342988930, now seen corresponding path program 1 times [2018-01-23 14:54:12,252 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:54:12,252 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:54:12,253 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:54:12,254 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:54:12,254 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:54:12,265 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:54:12,267 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:54:12,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-23 14:54:12,282 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-23 14:54:12,282 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-01-23 14:54:12,283 INFO L409 AbstractCegarLoop]: Interpolant automaton has 2 states [2018-01-23 14:54:12,283 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2018-01-23 14:54:12,283 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-01-23 14:54:12,284 INFO L87 Difference]: Start difference. First operand 97 states. Second operand 2 states. [2018-01-23 14:54:12,295 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:54:12,295 INFO L93 Difference]: Finished difference Result 177 states and 235 transitions. [2018-01-23 14:54:12,296 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2018-01-23 14:54:12,296 INFO L78 Accepts]: Start accepts. Automaton has 2 states. Word has length 25 [2018-01-23 14:54:12,296 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:54:12,297 INFO L225 Difference]: With dead ends: 177 [2018-01-23 14:54:12,297 INFO L226 Difference]: Without dead ends: 92 [2018-01-23 14:54:12,298 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-23 14:54:12,298 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 92 states. [2018-01-23 14:54:12,303 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 92 to 92. [2018-01-23 14:54:12,303 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 92 states. [2018-01-23 14:54:12,304 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 92 states to 92 states and 97 transitions. [2018-01-23 14:54:12,304 INFO L78 Accepts]: Start accepts. Automaton has 92 states and 97 transitions. Word has length 25 [2018-01-23 14:54:12,305 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:54:12,305 INFO L432 AbstractCegarLoop]: Abstraction has 92 states and 97 transitions. [2018-01-23 14:54:12,305 INFO L433 AbstractCegarLoop]: Interpolant automaton has 2 states. [2018-01-23 14:54:12,305 INFO L276 IsEmpty]: Start isEmpty. Operand 92 states and 97 transitions. [2018-01-23 14:54:12,306 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2018-01-23 14:54:12,306 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:54:12,306 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] [2018-01-23 14:54:12,306 INFO L371 AbstractCegarLoop]: === Iteration 2 === [mainErr0EnsuresViolation]=== [2018-01-23 14:54:12,307 INFO L82 PathProgramCache]: Analyzing trace with hash -1210340747, now seen corresponding path program 1 times [2018-01-23 14:54:12,307 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:54:12,307 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:54:12,308 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:54:12,309 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:54:12,309 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:54:12,322 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:54:12,324 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:54:12,406 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-23 14:54:12,406 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-23 14:54:12,406 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2018-01-23 14:54:12,407 INFO L409 AbstractCegarLoop]: Interpolant automaton has 8 states [2018-01-23 14:54:12,407 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2018-01-23 14:54:12,407 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=43, Unknown=0, NotChecked=0, Total=56 [2018-01-23 14:54:12,407 INFO L87 Difference]: Start difference. First operand 92 states and 97 transitions. Second operand 8 states. [2018-01-23 14:54:12,652 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:54:12,652 INFO L93 Difference]: Finished difference Result 151 states and 163 transitions. [2018-01-23 14:54:12,653 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-01-23 14:54:12,653 INFO L78 Accepts]: Start accepts. Automaton has 8 states. Word has length 34 [2018-01-23 14:54:12,653 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:54:12,654 INFO L225 Difference]: With dead ends: 151 [2018-01-23 14:54:12,655 INFO L226 Difference]: Without dead ends: 133 [2018-01-23 14:54:12,655 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 14 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=63, Invalid=119, Unknown=0, NotChecked=0, Total=182 [2018-01-23 14:54:12,656 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 133 states. [2018-01-23 14:54:12,664 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 133 to 94. [2018-01-23 14:54:12,664 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 94 states. [2018-01-23 14:54:12,665 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 94 states to 94 states and 99 transitions. [2018-01-23 14:54:12,665 INFO L78 Accepts]: Start accepts. Automaton has 94 states and 99 transitions. Word has length 34 [2018-01-23 14:54:12,666 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:54:12,666 INFO L432 AbstractCegarLoop]: Abstraction has 94 states and 99 transitions. [2018-01-23 14:54:12,666 INFO L433 AbstractCegarLoop]: Interpolant automaton has 8 states. [2018-01-23 14:54:12,666 INFO L276 IsEmpty]: Start isEmpty. Operand 94 states and 99 transitions. [2018-01-23 14:54:12,667 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2018-01-23 14:54:12,667 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:54:12,667 INFO L322 BasicCegarLoop]: trace histogram [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] [2018-01-23 14:54:12,667 INFO L371 AbstractCegarLoop]: === Iteration 3 === [mainErr0EnsuresViolation]=== [2018-01-23 14:54:12,668 INFO L82 PathProgramCache]: Analyzing trace with hash -961529277, now seen corresponding path program 1 times [2018-01-23 14:54:12,668 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:54:12,668 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:54:12,669 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:54:12,669 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:54:12,669 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:54:12,681 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:54:12,682 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:54:12,775 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-01-23 14:54:12,775 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-23 14:54:12,775 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2018-01-23 14:54:12,776 INFO L409 AbstractCegarLoop]: Interpolant automaton has 8 states [2018-01-23 14:54:12,776 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2018-01-23 14:54:12,777 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=43, Unknown=0, NotChecked=0, Total=56 [2018-01-23 14:54:12,777 INFO L87 Difference]: Start difference. First operand 94 states and 99 transitions. Second operand 8 states. [2018-01-23 14:54:12,929 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:54:12,929 INFO L93 Difference]: Finished difference Result 128 states and 136 transitions. [2018-01-23 14:54:12,929 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-01-23 14:54:12,929 INFO L78 Accepts]: Start accepts. Automaton has 8 states. Word has length 40 [2018-01-23 14:54:12,930 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:54:12,931 INFO L225 Difference]: With dead ends: 128 [2018-01-23 14:54:12,931 INFO L226 Difference]: Without dead ends: 124 [2018-01-23 14:54:12,931 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 14 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=64, Invalid=118, Unknown=0, NotChecked=0, Total=182 [2018-01-23 14:54:12,932 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 124 states. [2018-01-23 14:54:12,938 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 124 to 96. [2018-01-23 14:54:12,938 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 96 states. [2018-01-23 14:54:12,939 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 96 states to 96 states and 101 transitions. [2018-01-23 14:54:12,939 INFO L78 Accepts]: Start accepts. Automaton has 96 states and 101 transitions. Word has length 40 [2018-01-23 14:54:12,939 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:54:12,939 INFO L432 AbstractCegarLoop]: Abstraction has 96 states and 101 transitions. [2018-01-23 14:54:12,940 INFO L433 AbstractCegarLoop]: Interpolant automaton has 8 states. [2018-01-23 14:54:12,940 INFO L276 IsEmpty]: Start isEmpty. Operand 96 states and 101 transitions. [2018-01-23 14:54:12,941 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 49 [2018-01-23 14:54:12,941 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:54:12,941 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-23 14:54:12,941 INFO L371 AbstractCegarLoop]: === Iteration 4 === [mainErr0EnsuresViolation]=== [2018-01-23 14:54:12,941 INFO L82 PathProgramCache]: Analyzing trace with hash -1660607120, now seen corresponding path program 1 times [2018-01-23 14:54:12,942 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:54:12,942 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:54:12,943 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:54:12,943 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:54:12,943 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:54:12,958 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:54:12,959 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:54:13,348 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-01-23 14:54:13,349 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-23 14:54:13,349 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-23 14:54:13,355 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:54:13,395 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:54:13,401 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-23 14:54:13,706 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-23 14:54:13,742 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-23 14:54:13,742 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 9] total 17 [2018-01-23 14:54:13,742 INFO L409 AbstractCegarLoop]: Interpolant automaton has 18 states [2018-01-23 14:54:13,742 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2018-01-23 14:54:13,743 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=44, Invalid=250, Unknown=12, NotChecked=0, Total=306 [2018-01-23 14:54:13,743 INFO L87 Difference]: Start difference. First operand 96 states and 101 transitions. Second operand 18 states. [2018-01-23 14:54:14,657 WARN L146 SmtUtils]: Spent 106ms on a formula simplification. DAG size of input: 46 DAG size of output 39 [2018-01-23 14:54:15,149 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:54:15,150 INFO L93 Difference]: Finished difference Result 165 states and 177 transitions. [2018-01-23 14:54:15,151 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2018-01-23 14:54:15,151 INFO L78 Accepts]: Start accepts. Automaton has 18 states. Word has length 48 [2018-01-23 14:54:15,151 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:54:15,152 INFO L225 Difference]: With dead ends: 165 [2018-01-23 14:54:15,152 INFO L226 Difference]: Without dead ends: 161 [2018-01-23 14:54:15,153 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 71 GetRequests, 44 SyntacticMatches, 1 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 100 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=131, Invalid=613, Unknown=12, NotChecked=0, Total=756 [2018-01-23 14:54:15,154 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 161 states. [2018-01-23 14:54:15,163 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 161 to 132. [2018-01-23 14:54:15,164 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 132 states. [2018-01-23 14:54:15,165 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 132 states to 132 states and 141 transitions. [2018-01-23 14:54:15,165 INFO L78 Accepts]: Start accepts. Automaton has 132 states and 141 transitions. Word has length 48 [2018-01-23 14:54:15,165 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:54:15,165 INFO L432 AbstractCegarLoop]: Abstraction has 132 states and 141 transitions. [2018-01-23 14:54:15,166 INFO L433 AbstractCegarLoop]: Interpolant automaton has 18 states. [2018-01-23 14:54:15,166 INFO L276 IsEmpty]: Start isEmpty. Operand 132 states and 141 transitions. [2018-01-23 14:54:15,166 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2018-01-23 14:54:15,166 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:54:15,167 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-23 14:54:15,167 INFO L371 AbstractCegarLoop]: === Iteration 5 === [mainErr0EnsuresViolation]=== [2018-01-23 14:54:15,167 INFO L82 PathProgramCache]: Analyzing trace with hash 882290359, now seen corresponding path program 1 times [2018-01-23 14:54:15,167 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:54:15,167 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:54:15,169 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:54:15,169 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:54:15,169 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:54:15,181 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:54:15,182 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:54:15,284 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-23 14:54:15,284 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-23 14:54:15,285 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-23 14:54:15,297 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:54:15,328 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:54:15,333 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-23 14:54:15,362 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-23 14:54:15,365 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-23 14:54:15,365 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:15,367 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:15,369 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:15,370 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:13, output treesize:9 [2018-01-23 14:54:15,376 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 19 treesize of output 15 [2018-01-23 14:54:15,379 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 15 treesize of output 3 [2018-01-23 14:54:15,379 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:15,381 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:15,383 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-23 14:54:15,383 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:19, output treesize:3 [2018-01-23 14:54:15,398 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-01-23 14:54:15,433 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-01-23 14:54:15,434 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [8] total 9 [2018-01-23 14:54:15,434 INFO L409 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-01-23 14:54:15,435 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-01-23 14:54:15,435 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2018-01-23 14:54:15,435 INFO L87 Difference]: Start difference. First operand 132 states and 141 transitions. Second operand 9 states. [2018-01-23 14:54:15,771 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:54:15,771 INFO L93 Difference]: Finished difference Result 224 states and 243 transitions. [2018-01-23 14:54:15,772 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-01-23 14:54:15,772 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 50 [2018-01-23 14:54:15,772 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:54:15,773 INFO L225 Difference]: With dead ends: 224 [2018-01-23 14:54:15,773 INFO L226 Difference]: Without dead ends: 181 [2018-01-23 14:54:15,774 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 64 GetRequests, 49 SyntacticMatches, 1 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 37 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=61, Invalid=179, Unknown=0, NotChecked=0, Total=240 [2018-01-23 14:54:15,774 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 181 states. [2018-01-23 14:54:15,784 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 181 to 155. [2018-01-23 14:54:15,784 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 155 states. [2018-01-23 14:54:15,786 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 155 states to 155 states and 166 transitions. [2018-01-23 14:54:15,786 INFO L78 Accepts]: Start accepts. Automaton has 155 states and 166 transitions. Word has length 50 [2018-01-23 14:54:15,787 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:54:15,798 INFO L432 AbstractCegarLoop]: Abstraction has 155 states and 166 transitions. [2018-01-23 14:54:15,798 INFO L433 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-01-23 14:54:15,799 INFO L276 IsEmpty]: Start isEmpty. Operand 155 states and 166 transitions. [2018-01-23 14:54:15,800 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2018-01-23 14:54:15,800 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:54:15,801 INFO L322 BasicCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-23 14:54:15,801 INFO L371 AbstractCegarLoop]: === Iteration 6 === [mainErr0EnsuresViolation]=== [2018-01-23 14:54:15,801 INFO L82 PathProgramCache]: Analyzing trace with hash -1052339299, now seen corresponding path program 2 times [2018-01-23 14:54:15,802 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:54:15,802 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:54:15,803 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:54:15,803 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:54:15,803 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:54:15,816 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:54:15,818 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:54:15,958 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 10 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-23 14:54:15,958 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-23 14:54:15,958 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-23 14:54:15,965 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-01-23 14:54:15,983 INFO L201 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-23 14:54:16,018 INFO L214 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-23 14:54:16,019 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-23 14:54:16,023 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-23 14:54:16,089 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 15 treesize of output 11 [2018-01-23 14:54:16,091 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-23 14:54:16,091 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:16,092 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:16,093 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-23 14:54:16,093 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:15, output treesize:3 [2018-01-23 14:54:16,150 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 0 proven. 14 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-23 14:54:16,171 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-23 14:54:16,171 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 13] total 21 [2018-01-23 14:54:16,172 INFO L409 AbstractCegarLoop]: Interpolant automaton has 21 states [2018-01-23 14:54:16,172 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2018-01-23 14:54:16,172 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=49, Invalid=371, Unknown=0, NotChecked=0, Total=420 [2018-01-23 14:54:16,172 INFO L87 Difference]: Start difference. First operand 155 states and 166 transitions. Second operand 21 states. [2018-01-23 14:54:16,872 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:54:16,872 INFO L93 Difference]: Finished difference Result 238 states and 256 transitions. [2018-01-23 14:54:16,872 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2018-01-23 14:54:16,873 INFO L78 Accepts]: Start accepts. Automaton has 21 states. Word has length 56 [2018-01-23 14:54:16,873 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:54:16,873 INFO L225 Difference]: With dead ends: 238 [2018-01-23 14:54:16,873 INFO L226 Difference]: Without dead ends: 169 [2018-01-23 14:54:16,874 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 82 GetRequests, 48 SyntacticMatches, 0 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 151 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=198, Invalid=1062, Unknown=0, NotChecked=0, Total=1260 [2018-01-23 14:54:16,875 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 169 states. [2018-01-23 14:54:16,881 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 169 to 134. [2018-01-23 14:54:16,881 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 134 states. [2018-01-23 14:54:16,882 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 134 states to 134 states and 143 transitions. [2018-01-23 14:54:16,882 INFO L78 Accepts]: Start accepts. Automaton has 134 states and 143 transitions. Word has length 56 [2018-01-23 14:54:16,883 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:54:16,883 INFO L432 AbstractCegarLoop]: Abstraction has 134 states and 143 transitions. [2018-01-23 14:54:16,883 INFO L433 AbstractCegarLoop]: Interpolant automaton has 21 states. [2018-01-23 14:54:16,883 INFO L276 IsEmpty]: Start isEmpty. Operand 134 states and 143 transitions. [2018-01-23 14:54:16,884 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2018-01-23 14:54:16,884 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:54:16,884 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-23 14:54:16,884 INFO L371 AbstractCegarLoop]: === Iteration 7 === [mainErr0EnsuresViolation]=== [2018-01-23 14:54:16,884 INFO L82 PathProgramCache]: Analyzing trace with hash -18262224, now seen corresponding path program 1 times [2018-01-23 14:54:16,885 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:54:16,885 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:54:16,886 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:54:16,886 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-01-23 14:54:16,886 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:54:16,906 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:54:16,907 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:54:17,273 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 5 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-01-23 14:54:17,273 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-23 14:54:17,273 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-23 14:54:17,278 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:54:17,300 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:54:17,305 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-23 14:54:17,308 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-23 14:54:17,308 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:17,309 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:17,310 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:6, output treesize:5 [2018-01-23 14:54:17,353 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:17,354 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:17,356 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-23 14:54:17,356 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:17,361 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:17,361 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:20, output treesize:14 [2018-01-23 14:54:17,383 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-23 14:54:17,385 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-23 14:54:17,385 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:17,386 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:17,393 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-23 14:54:17,394 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-23 14:54:17,394 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:17,395 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:17,400 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-23 14:54:17,400 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 3 variables, input treesize:33, output treesize:22 [2018-01-23 14:54:17,440 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:17,444 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-23 14:54:17,446 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-23 14:54:17,446 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:17,451 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:17,465 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:17,468 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-23 14:54:17,471 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-23 14:54:17,471 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:17,477 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:17,485 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-23 14:54:17,486 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 3 variables, input treesize:64, output treesize:48 [2018-01-23 14:54:17,547 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-23 14:54:17,552 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-23 14:54:17,552 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:17,559 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-23 14:54:17,559 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:17,562 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:17,567 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-23 14:54:17,567 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 2 variables, input treesize:56, output treesize:32 [2018-01-23 14:54:17,630 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-23 14:54:17,654 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 2 case distinctions, treesize of input 16 treesize of output 23 [2018-01-23 14:54:17,654 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-23 14:54:17,667 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-23 14:54:17,684 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 2 xjuncts. [2018-01-23 14:54:17,684 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:43, output treesize:62 [2018-01-23 14:54:17,736 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:17,739 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-23 14:54:17,743 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:17,744 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-23 14:54:17,745 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:17,751 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:17,756 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:17,756 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:45, output treesize:26 [2018-01-23 14:54:17,802 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 35 treesize of output 23 [2018-01-23 14:54:17,810 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 9 [2018-01-23 14:54:17,810 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:17,817 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-23 14:54:17,817 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:17,820 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:17,843 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 31 treesize of output 21 [2018-01-23 14:54:17,846 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-23 14:54:17,846 INFO L267 ElimStorePlain]: Start of recursive call 6: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:17,851 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-23 14:54:17,851 INFO L267 ElimStorePlain]: Start of recursive call 7: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:17,856 INFO L267 ElimStorePlain]: Start of recursive call 5: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:17,862 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 2 dim-2 vars, End of recursive call: and 2 xjuncts. [2018-01-23 14:54:17,863 INFO L202 ElimStorePlain]: Needed 7 recursive calls to eliminate 4 variables, input treesize:67, output treesize:9 [2018-01-23 14:54:17,949 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 5 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-01-23 14:54:17,970 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-23 14:54:17,970 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 17] total 32 [2018-01-23 14:54:17,970 INFO L409 AbstractCegarLoop]: Interpolant automaton has 32 states [2018-01-23 14:54:17,971 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2018-01-23 14:54:17,971 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=88, Invalid=904, Unknown=0, NotChecked=0, Total=992 [2018-01-23 14:54:17,971 INFO L87 Difference]: Start difference. First operand 134 states and 143 transitions. Second operand 32 states. [2018-01-23 14:54:19,549 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:54:19,549 INFO L93 Difference]: Finished difference Result 283 states and 304 transitions. [2018-01-23 14:54:19,550 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2018-01-23 14:54:19,550 INFO L78 Accepts]: Start accepts. Automaton has 32 states. Word has length 73 [2018-01-23 14:54:19,550 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:54:19,551 INFO L225 Difference]: With dead ends: 283 [2018-01-23 14:54:19,551 INFO L226 Difference]: Without dead ends: 269 [2018-01-23 14:54:19,552 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 118 GetRequests, 61 SyntacticMatches, 2 SemanticMatches, 55 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 615 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=473, Invalid=2719, Unknown=0, NotChecked=0, Total=3192 [2018-01-23 14:54:19,552 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 269 states. [2018-01-23 14:54:19,560 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 269 to 217. [2018-01-23 14:54:19,560 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 217 states. [2018-01-23 14:54:19,561 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 217 states to 217 states and 234 transitions. [2018-01-23 14:54:19,561 INFO L78 Accepts]: Start accepts. Automaton has 217 states and 234 transitions. Word has length 73 [2018-01-23 14:54:19,561 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:54:19,561 INFO L432 AbstractCegarLoop]: Abstraction has 217 states and 234 transitions. [2018-01-23 14:54:19,562 INFO L433 AbstractCegarLoop]: Interpolant automaton has 32 states. [2018-01-23 14:54:19,562 INFO L276 IsEmpty]: Start isEmpty. Operand 217 states and 234 transitions. [2018-01-23 14:54:19,563 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 83 [2018-01-23 14:54:19,563 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:54:19,563 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, 1, 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-23 14:54:19,563 INFO L371 AbstractCegarLoop]: === Iteration 8 === [mainErr0EnsuresViolation]=== [2018-01-23 14:54:19,563 INFO L82 PathProgramCache]: Analyzing trace with hash 1978964382, now seen corresponding path program 1 times [2018-01-23 14:54:19,563 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:54:19,564 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:54:19,565 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:54:19,565 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:54:19,565 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:54:19,588 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:54:19,589 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:54:20,565 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 5 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-01-23 14:54:20,565 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-23 14:54:20,565 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-23 14:54:20,571 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:54:20,607 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:54:20,611 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-23 14:54:20,614 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-23 14:54:20,615 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:20,616 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:20,616 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:6, output treesize:5 [2018-01-23 14:54:20,654 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 12 treesize of output 11 [2018-01-23 14:54:20,655 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:20,658 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:20,658 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:12, output treesize:11 [2018-01-23 14:54:20,706 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:20,708 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:20,708 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:20,709 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 3 select indices, 3 select index equivalence classes, 3 disjoint index pairs (out of 3 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 30 [2018-01-23 14:54:20,710 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:20,718 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:20,718 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:28, output treesize:30 [2018-01-23 14:54:20,751 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-23 14:54:20,753 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 2 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-23 14:54:20,754 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:20,755 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:20,765 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-23 14:54:20,766 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:41, output treesize:42 [2018-01-23 14:54:20,830 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:20,833 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 47 treesize of output 51 [2018-01-23 14:54:20,836 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-23 14:54:20,836 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:20,844 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:20,855 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-23 14:54:20,855 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:63, output treesize:55 [2018-01-23 14:54:21,055 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 2 disjoint index pairs (out of 3 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 57 treesize of output 52 [2018-01-23 14:54:21,065 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 2 case distinctions, treesize of input 16 treesize of output 23 [2018-01-23 14:54:21,065 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-23 14:54:21,080 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-23 14:54:21,105 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 2 xjuncts. [2018-01-23 14:54:21,105 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:67, output treesize:110 [2018-01-23 14:54:21,175 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:21,179 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 59 treesize of output 58 [2018-01-23 14:54:21,182 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:21,183 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-23 14:54:21,184 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:21,192 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:21,201 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:21,201 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:69, output treesize:50 [2018-01-23 14:54:21,205 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:21,206 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:21,206 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:21,207 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:21,208 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 4 select indices, 4 select index equivalence classes, 6 disjoint index pairs (out of 6 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 25 treesize of output 33 [2018-01-23 14:54:21,208 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:21,216 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:21,217 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:55, output treesize:47 [2018-01-23 14:54:21,254 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:21,255 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:21,256 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 50 treesize of output 55 [2018-01-23 14:54:21,259 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 3 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 20 treesize of output 12 [2018-01-23 14:54:21,259 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:21,267 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:21,274 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-23 14:54:21,275 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:58, output treesize:52 [2018-01-23 14:54:21,361 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:21,366 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 4 disjoint index pairs (out of 3 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 73 treesize of output 81 [2018-01-23 14:54:21,368 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 14 treesize of output 13 [2018-01-23 14:54:21,368 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:21,379 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:21,387 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-23 14:54:21,387 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:73, output treesize:61 [2018-01-23 14:54:21,525 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 5 disjoint index pairs (out of 6 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 100 treesize of output 90 [2018-01-23 14:54:21,536 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 2 case distinctions, treesize of input 20 treesize of output 27 [2018-01-23 14:54:21,537 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-23 14:54:21,556 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-23 14:54:21,585 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: 3 dim-0 vars, and 2 xjuncts. [2018-01-23 14:54:21,586 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:100, output treesize:148 [2018-01-23 14:54:21,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, 5 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 115 treesize of output 84 [2018-01-23 14:54:21,667 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:21,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, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 38 treesize of output 22 [2018-01-23 14:54:21,668 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:21,676 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:21,683 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-23 14:54:21,684 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:115, output treesize:72 [2018-01-23 14:54:21,893 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 19 treesize of output 15 [2018-01-23 14:54:21,896 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 15 treesize of output 3 [2018-01-23 14:54:21,896 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:21,898 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:21,906 INFO L267 ElimStorePlain]: Start of recursive call 1: 4 dim-0 vars, 1 dim-2 vars, End of recursive call: 2 dim-0 vars, and 1 xjuncts. [2018-01-23 14:54:21,906 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 5 variables, input treesize:90, output treesize:75 [2018-01-23 14:54:22,006 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 5 disjoint index pairs (out of 3 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 79 treesize of output 48 [2018-01-23 14:54:22,009 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 3 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 21 treesize of output 15 [2018-01-23 14:54:22,009 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:22,022 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-23 14:54:22,023 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:22,033 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 9 [2018-01-23 14:54:22,033 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:22,036 INFO L267 ElimStorePlain]: Start of recursive call 2: 3 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:22,038 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:22,038 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 4 variables, input treesize:79, output treesize:4 [2018-01-23 14:54:22,120 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-23 14:54:22,141 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-23 14:54:22,141 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [24, 28] total 47 [2018-01-23 14:54:22,141 INFO L409 AbstractCegarLoop]: Interpolant automaton has 47 states [2018-01-23 14:54:22,142 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 47 interpolants. [2018-01-23 14:54:22,142 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=217, Invalid=1945, Unknown=0, NotChecked=0, Total=2162 [2018-01-23 14:54:22,142 INFO L87 Difference]: Start difference. First operand 217 states and 234 transitions. Second operand 47 states. [2018-01-23 14:54:25,584 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:54:25,584 INFO L93 Difference]: Finished difference Result 384 states and 414 transitions. [2018-01-23 14:54:25,584 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 46 states. [2018-01-23 14:54:25,585 INFO L78 Accepts]: Start accepts. Automaton has 47 states. Word has length 82 [2018-01-23 14:54:25,585 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:54:25,586 INFO L225 Difference]: With dead ends: 384 [2018-01-23 14:54:25,586 INFO L226 Difference]: Without dead ends: 339 [2018-01-23 14:54:25,587 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 149 GetRequests, 57 SyntacticMatches, 6 SemanticMatches, 86 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1832 ImplicationChecksByTransitivity, 3.6s TimeCoverageRelationStatistics Valid=1072, Invalid=6584, Unknown=0, NotChecked=0, Total=7656 [2018-01-23 14:54:25,588 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 339 states. [2018-01-23 14:54:25,597 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 339 to 253. [2018-01-23 14:54:25,597 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 253 states. [2018-01-23 14:54:25,599 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 253 states to 253 states and 271 transitions. [2018-01-23 14:54:25,599 INFO L78 Accepts]: Start accepts. Automaton has 253 states and 271 transitions. Word has length 82 [2018-01-23 14:54:25,600 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:54:25,600 INFO L432 AbstractCegarLoop]: Abstraction has 253 states and 271 transitions. [2018-01-23 14:54:25,600 INFO L433 AbstractCegarLoop]: Interpolant automaton has 47 states. [2018-01-23 14:54:25,600 INFO L276 IsEmpty]: Start isEmpty. Operand 253 states and 271 transitions. [2018-01-23 14:54:25,601 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 85 [2018-01-23 14:54:25,601 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:54:25,601 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, 1, 1, 1, 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-23 14:54:25,601 INFO L371 AbstractCegarLoop]: === Iteration 9 === [mainErr0EnsuresViolation]=== [2018-01-23 14:54:25,602 INFO L82 PathProgramCache]: Analyzing trace with hash 1174000766, now seen corresponding path program 1 times [2018-01-23 14:54:25,602 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:54:25,602 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:54:25,603 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:54:25,603 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:54:25,603 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:54:25,616 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:54:25,617 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:54:25,742 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2018-01-23 14:54:25,742 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-23 14:54:25,742 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-01-23 14:54:25,743 INFO L409 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-01-23 14:54:25,743 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-01-23 14:54:25,743 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-01-23 14:54:25,743 INFO L87 Difference]: Start difference. First operand 253 states and 271 transitions. Second operand 5 states. [2018-01-23 14:54:25,833 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:54:25,833 INFO L93 Difference]: Finished difference Result 277 states and 296 transitions. [2018-01-23 14:54:25,833 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-01-23 14:54:25,833 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 84 [2018-01-23 14:54:25,833 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:54:25,834 INFO L225 Difference]: With dead ends: 277 [2018-01-23 14:54:25,834 INFO L226 Difference]: Without dead ends: 219 [2018-01-23 14:54:25,834 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 0 SyntacticMatches, 2 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2018-01-23 14:54:25,835 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 219 states. [2018-01-23 14:54:25,842 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 219 to 193. [2018-01-23 14:54:25,843 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 193 states. [2018-01-23 14:54:25,844 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 193 states to 193 states and 203 transitions. [2018-01-23 14:54:25,844 INFO L78 Accepts]: Start accepts. Automaton has 193 states and 203 transitions. Word has length 84 [2018-01-23 14:54:25,844 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:54:25,844 INFO L432 AbstractCegarLoop]: Abstraction has 193 states and 203 transitions. [2018-01-23 14:54:25,845 INFO L433 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-01-23 14:54:25,845 INFO L276 IsEmpty]: Start isEmpty. Operand 193 states and 203 transitions. [2018-01-23 14:54:25,846 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 88 [2018-01-23 14:54:25,846 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:54:25,846 INFO L322 BasicCegarLoop]: trace histogram [3, 3, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-23 14:54:25,846 INFO L371 AbstractCegarLoop]: === Iteration 10 === [mainErr0EnsuresViolation]=== [2018-01-23 14:54:25,846 INFO L82 PathProgramCache]: Analyzing trace with hash 1214863019, now seen corresponding path program 2 times [2018-01-23 14:54:25,847 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:54:25,847 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:54:25,848 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:54:25,848 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:54:25,848 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:54:25,871 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:54:25,873 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:54:26,755 WARN L146 SmtUtils]: Spent 109ms on a formula simplification. DAG size of input: 56 DAG size of output 26 [2018-01-23 14:54:27,477 WARN L146 SmtUtils]: Spent 237ms on a formula simplification. DAG size of input: 57 DAG size of output 41 [2018-01-23 14:54:28,195 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 0 proven. 22 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-01-23 14:54:28,196 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-23 14:54:28,196 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-23 14:54:28,201 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-01-23 14:54:28,218 INFO L201 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-23 14:54:28,254 INFO L214 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-23 14:54:28,261 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-23 14:54:28,267 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-23 14:54:28,483 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-23 14:54:28,486 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-23 14:54:28,486 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:28,487 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:28,501 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-23 14:54:28,502 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:69, output treesize:70 [2018-01-23 14:54:28,609 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:28,612 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 61 treesize of output 65 [2018-01-23 14:54:28,614 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-23 14:54:28,614 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:28,621 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:28,636 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-23 14:54:28,636 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:91, output treesize:83 [2018-01-23 14:54:28,836 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:28,841 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 3 disjoint index pairs (out of 3 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 71 treesize of output 70 [2018-01-23 14:54:28,845 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:28,850 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 2 case distinctions, treesize of input 16 treesize of output 27 [2018-01-23 14:54:28,850 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-23 14:54:28,868 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-23 14:54:28,899 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 2 xjuncts. [2018-01-23 14:54:28,899 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:95, output treesize:166 [2018-01-23 14:54:28,999 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:29,006 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 82 treesize of output 80 [2018-01-23 14:54:29,010 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:29,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 30 treesize of output 18 [2018-01-23 14:54:29,012 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:29,021 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:29,034 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-23 14:54:29,035 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:106, output treesize:75 [2018-01-23 14:54:29,355 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:29,357 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 58 treesize of output 50 [2018-01-23 14:54:29,359 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-23 14:54:29,360 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:29,372 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 39 treesize of output 28 [2018-01-23 14:54:29,373 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:29,377 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:29,386 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-23 14:54:29,387 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 2 variables, input treesize:79, output treesize:49 [2018-01-23 14:54:29,970 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-01-23 14:54:29,991 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-23 14:54:29,992 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [24, 22] total 44 [2018-01-23 14:54:29,992 INFO L409 AbstractCegarLoop]: Interpolant automaton has 45 states [2018-01-23 14:54:29,992 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 45 interpolants. [2018-01-23 14:54:29,993 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=120, Invalid=1812, Unknown=48, NotChecked=0, Total=1980 [2018-01-23 14:54:29,993 INFO L87 Difference]: Start difference. First operand 193 states and 203 transitions. Second operand 45 states. [2018-01-23 14:54:33,070 WARN L146 SmtUtils]: Spent 103ms on a formula simplification. DAG size of input: 96 DAG size of output 53 [2018-01-23 14:54:34,391 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:54:34,391 INFO L93 Difference]: Finished difference Result 275 states and 290 transitions. [2018-01-23 14:54:34,407 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 29 states. [2018-01-23 14:54:34,408 INFO L78 Accepts]: Start accepts. Automaton has 45 states. Word has length 87 [2018-01-23 14:54:34,408 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:54:34,409 INFO L225 Difference]: With dead ends: 275 [2018-01-23 14:54:34,409 INFO L226 Difference]: Without dead ends: 271 [2018-01-23 14:54:34,410 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 145 GetRequests, 71 SyntacticMatches, 5 SemanticMatches, 69 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 926 ImplicationChecksByTransitivity, 5.5s TimeCoverageRelationStatistics Valid=388, Invalid=4520, Unknown=62, NotChecked=0, Total=4970 [2018-01-23 14:54:34,410 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 271 states. [2018-01-23 14:54:34,421 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 271 to 250. [2018-01-23 14:54:34,422 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 250 states. [2018-01-23 14:54:34,423 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 250 states to 250 states and 264 transitions. [2018-01-23 14:54:34,424 INFO L78 Accepts]: Start accepts. Automaton has 250 states and 264 transitions. Word has length 87 [2018-01-23 14:54:34,424 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:54:34,424 INFO L432 AbstractCegarLoop]: Abstraction has 250 states and 264 transitions. [2018-01-23 14:54:34,424 INFO L433 AbstractCegarLoop]: Interpolant automaton has 45 states. [2018-01-23 14:54:34,424 INFO L276 IsEmpty]: Start isEmpty. Operand 250 states and 264 transitions. [2018-01-23 14:54:34,426 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 90 [2018-01-23 14:54:34,426 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:54:34,426 INFO L322 BasicCegarLoop]: trace histogram [3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 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-23 14:54:34,426 INFO L371 AbstractCegarLoop]: === Iteration 11 === [mainErr0EnsuresViolation]=== [2018-01-23 14:54:34,426 INFO L82 PathProgramCache]: Analyzing trace with hash -1749844686, now seen corresponding path program 1 times [2018-01-23 14:54:34,427 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:54:34,427 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:54:34,428 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:54:34,428 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-01-23 14:54:34,428 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:54:34,442 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:54:34,444 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:54:34,796 INFO L134 CoverageAnalysis]: Checked inductivity of 21 backedges. 0 proven. 18 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-01-23 14:54:34,797 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-23 14:54:34,797 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-23 14:54:34,802 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:54:34,827 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:54:34,831 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-23 14:54:34,861 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 39 treesize of output 33 [2018-01-23 14:54:34,863 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 33 treesize of output 24 [2018-01-23 14:54:34,864 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:34,868 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:34,877 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-23 14:54:34,877 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:46, output treesize:31 [2018-01-23 14:54:34,988 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 3 new quantified variables, introduced 1 case distinctions, treesize of input 35 treesize of output 30 [2018-01-23 14:54:34,996 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 17 treesize of output 8 [2018-01-23 14:54:34,997 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:35,013 INFO L267 ElimStorePlain]: Start of recursive call 2: 3 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:35,020 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-23 14:54:35,021 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:35, output treesize:8 [2018-01-23 14:54:35,058 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-23 14:54:35,058 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:35,061 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:35,061 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:11, output treesize:10 [2018-01-23 14:54:35,073 INFO L134 CoverageAnalysis]: Checked inductivity of 21 backedges. 0 proven. 18 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-01-23 14:54:35,094 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-23 14:54:35,095 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 17] total 22 [2018-01-23 14:54:35,095 INFO L409 AbstractCegarLoop]: Interpolant automaton has 22 states [2018-01-23 14:54:35,095 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2018-01-23 14:54:35,096 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=67, Invalid=395, Unknown=0, NotChecked=0, Total=462 [2018-01-23 14:54:35,096 INFO L87 Difference]: Start difference. First operand 250 states and 264 transitions. Second operand 22 states. [2018-01-23 14:54:36,306 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:54:36,307 INFO L93 Difference]: Finished difference Result 396 states and 427 transitions. [2018-01-23 14:54:36,307 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 29 states. [2018-01-23 14:54:36,307 INFO L78 Accepts]: Start accepts. Automaton has 22 states. Word has length 89 [2018-01-23 14:54:36,307 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:54:36,309 INFO L225 Difference]: With dead ends: 396 [2018-01-23 14:54:36,309 INFO L226 Difference]: Without dead ends: 354 [2018-01-23 14:54:36,310 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 132 GetRequests, 79 SyntacticMatches, 7 SemanticMatches, 46 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 402 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=339, Invalid=1917, Unknown=0, NotChecked=0, Total=2256 [2018-01-23 14:54:36,310 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 354 states. [2018-01-23 14:54:36,323 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 354 to 294. [2018-01-23 14:54:36,323 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 294 states. [2018-01-23 14:54:36,325 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 294 states to 294 states and 315 transitions. [2018-01-23 14:54:36,325 INFO L78 Accepts]: Start accepts. Automaton has 294 states and 315 transitions. Word has length 89 [2018-01-23 14:54:36,326 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:54:36,326 INFO L432 AbstractCegarLoop]: Abstraction has 294 states and 315 transitions. [2018-01-23 14:54:36,326 INFO L433 AbstractCegarLoop]: Interpolant automaton has 22 states. [2018-01-23 14:54:36,326 INFO L276 IsEmpty]: Start isEmpty. Operand 294 states and 315 transitions. [2018-01-23 14:54:36,327 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 96 [2018-01-23 14:54:36,327 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:54:36,328 INFO L322 BasicCegarLoop]: trace histogram [4, 3, 3, 3, 3, 3, 3, 3, 3, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-23 14:54:36,328 INFO L371 AbstractCegarLoop]: === Iteration 12 === [mainErr0EnsuresViolation]=== [2018-01-23 14:54:36,328 INFO L82 PathProgramCache]: Analyzing trace with hash 229595608, now seen corresponding path program 3 times [2018-01-23 14:54:36,328 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:54:36,328 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:54:36,329 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:54:36,329 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:54:36,329 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:54:36,342 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:54:36,343 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:54:36,755 INFO L134 CoverageAnalysis]: Checked inductivity of 43 backedges. 18 proven. 22 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-01-23 14:54:36,755 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-23 14:54:36,755 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-23 14:54:36,764 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-01-23 14:54:36,787 INFO L254 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued a check-sat command [2018-01-23 14:54:36,843 INFO L254 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued a check-sat command [2018-01-23 14:54:37,205 INFO L254 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued a check-sat command [2018-01-23 14:54:37,237 INFO L254 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued a check-sat command [2018-01-23 14:54:37,240 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-23 14:54:37,245 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-23 14:54:37,248 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-23 14:54:37,249 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:37,252 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:37,253 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:10, output treesize:9 [2018-01-23 14:54:37,369 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:37,378 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:37,379 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-23 14:54:37,380 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:37,388 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:37,389 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:23, output treesize:17 [2018-01-23 14:54:37,431 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-23 14:54:37,435 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-23 14:54:37,435 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:37,446 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:37,459 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-23 14:54:37,461 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-23 14:54:37,461 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:37,463 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:37,478 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-23 14:54:37,479 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 3 variables, input treesize:36, output treesize:25 [2018-01-23 14:54:37,591 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:37,596 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-23 14:54:37,599 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-23 14:54:37,599 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:37,609 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:37,627 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:37,631 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-23 14:54:37,633 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-23 14:54:37,634 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:37,639 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:37,651 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-23 14:54:37,651 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 3 variables, input treesize:67, output treesize:51 [2018-01-23 14:54:37,728 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-23 14:54:37,731 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 15 [2018-01-23 14:54:37,732 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:37,739 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 15 treesize of output 3 [2018-01-23 14:54:37,740 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:37,741 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:37,760 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-23 14:54:37,760 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 2 variables, input treesize:59, output treesize:35 [2018-01-23 14:54:37,883 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-23 14:54:37,897 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 2 case distinctions, treesize of input 16 treesize of output 23 [2018-01-23 14:54:37,897 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-23 14:54:37,913 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-23 14:54:37,936 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 2 xjuncts. [2018-01-23 14:54:37,936 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:46, output treesize:68 [2018-01-23 14:54:38,042 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 47 treesize of output 37 [2018-01-23 14:54:38,051 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-23 14:54:38,051 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:38,055 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:38,060 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:38,060 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:50, output treesize:23 [2018-01-23 14:54:38,182 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 3 new quantified variables, introduced 0 case distinctions, treesize of input 31 treesize of output 22 [2018-01-23 14:54:38,184 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 1 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 4 [2018-01-23 14:54:38,184 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:38,191 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 11 treesize of output 8 [2018-01-23 14:54:38,192 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 2 xjuncts. [2018-01-23 14:54:38,194 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-23 14:54:38,196 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-23 14:54:38,196 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 2 variables, input treesize:31, output treesize:8 [2018-01-23 14:54:38,343 INFO L134 CoverageAnalysis]: Checked inductivity of 43 backedges. 0 proven. 33 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-01-23 14:54:38,365 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-23 14:54:38,365 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 22] total 35 [2018-01-23 14:54:38,365 INFO L409 AbstractCegarLoop]: Interpolant automaton has 35 states [2018-01-23 14:54:38,366 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 35 interpolants. [2018-01-23 14:54:38,366 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=85, Invalid=1105, Unknown=0, NotChecked=0, Total=1190 [2018-01-23 14:54:38,366 INFO L87 Difference]: Start difference. First operand 294 states and 315 transitions. Second operand 35 states. [2018-01-23 14:54:41,381 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:54:41,381 INFO L93 Difference]: Finished difference Result 414 states and 442 transitions. [2018-01-23 14:54:41,382 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 46 states. [2018-01-23 14:54:41,382 INFO L78 Accepts]: Start accepts. Automaton has 35 states. Word has length 95 [2018-01-23 14:54:41,382 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:54:41,383 INFO L225 Difference]: With dead ends: 414 [2018-01-23 14:54:41,383 INFO L226 Difference]: Without dead ends: 341 [2018-01-23 14:54:41,385 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 155 GetRequests, 81 SyntacticMatches, 0 SemanticMatches, 74 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1072 ImplicationChecksByTransitivity, 2.6s TimeCoverageRelationStatistics Valid=528, Invalid=5172, Unknown=0, NotChecked=0, Total=5700 [2018-01-23 14:54:41,385 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 341 states. [2018-01-23 14:54:41,393 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 341 to 282. [2018-01-23 14:54:41,393 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 282 states. [2018-01-23 14:54:41,394 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 282 states to 282 states and 300 transitions. [2018-01-23 14:54:41,394 INFO L78 Accepts]: Start accepts. Automaton has 282 states and 300 transitions. Word has length 95 [2018-01-23 14:54:41,395 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:54:41,395 INFO L432 AbstractCegarLoop]: Abstraction has 282 states and 300 transitions. [2018-01-23 14:54:41,395 INFO L433 AbstractCegarLoop]: Interpolant automaton has 35 states. [2018-01-23 14:54:41,395 INFO L276 IsEmpty]: Start isEmpty. Operand 282 states and 300 transitions. [2018-01-23 14:54:41,396 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 97 [2018-01-23 14:54:41,396 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:54:41,396 INFO L322 BasicCegarLoop]: trace histogram [3, 3, 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, 1, 1, 1, 1, 1, 1, 1, 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-23 14:54:41,396 INFO L371 AbstractCegarLoop]: === Iteration 13 === [mainErr0EnsuresViolation]=== [2018-01-23 14:54:41,396 INFO L82 PathProgramCache]: Analyzing trace with hash 1038139545, now seen corresponding path program 2 times [2018-01-23 14:54:41,396 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:54:41,396 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:54:41,397 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:54:41,397 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-01-23 14:54:41,397 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:54:41,410 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:54:41,411 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:54:42,780 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 0 proven. 23 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-01-23 14:54:42,780 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-23 14:54:42,780 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-23 14:54:42,785 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-01-23 14:54:42,801 INFO L201 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-23 14:54:42,842 INFO L214 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-23 14:54:42,847 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-23 14:54:42,851 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-23 14:54:42,853 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-23 14:54:42,853 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:42,857 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:42,857 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:10, output treesize:9 [2018-01-23 14:54:42,983 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:42,983 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:42,984 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 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 17 treesize of output 21 [2018-01-23 14:54:42,984 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:43,048 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:43,049 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:29, output treesize:27 [2018-01-23 14:54:43,096 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-23 14:54:43,098 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-23 14:54:43,098 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:43,099 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:43,110 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-23 14:54:43,111 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-23 14:54:43,111 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:43,113 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:43,121 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-23 14:54:43,121 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 3 variables, input treesize:46, output treesize:39 [2018-01-23 14:54:43,201 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:43,205 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-23 14:54:43,207 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-23 14:54:43,207 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:43,211 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:43,225 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:43,228 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 52 treesize of output 56 [2018-01-23 14:54:43,229 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-23 14:54:43,230 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:43,235 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:43,246 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-23 14:54:43,246 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 3 variables, input treesize:81, output treesize:65 [2018-01-23 14:54:43,302 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-23 14:54:43,304 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 15 [2018-01-23 14:54:43,305 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:43,310 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 15 treesize of output 3 [2018-01-23 14:54:43,310 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:43,312 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:43,319 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-23 14:54:43,319 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 2 variables, input treesize:73, output treesize:49 [2018-01-23 14:54:43,419 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 49 treesize of output 44 [2018-01-23 14:54:43,427 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 2 case distinctions, treesize of input 16 treesize of output 23 [2018-01-23 14:54:43,428 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-23 14:54:43,440 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-23 14:54:43,461 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 2 xjuncts. [2018-01-23 14:54:43,461 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:60, output treesize:96 [2018-01-23 14:54:43,526 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:43,529 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 51 treesize of output 50 [2018-01-23 14:54:43,531 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:43,532 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-23 14:54:43,533 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:43,539 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:43,546 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:43,546 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:62, output treesize:43 [2018-01-23 14:54:43,549 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:43,550 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:43,550 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:43,551 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 4 disjoint index pairs (out of 3 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 20 treesize of output 21 [2018-01-23 14:54:43,551 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:43,559 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:43,559 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:51, output treesize:44 [2018-01-23 14:54:43,603 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:43,606 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:43,606 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 42 treesize of output 50 [2018-01-23 14:54:43,609 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 19 [2018-01-23 14:54:43,609 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:43,616 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:43,626 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 12 [2018-01-23 14:54:43,628 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-23 14:54:43,628 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:43,629 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:43,636 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-23 14:54:43,637 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 3 variables, input treesize:63, output treesize:45 [2018-01-23 14:54:43,725 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:43,726 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:43,727 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:43,728 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:43,733 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 5 disjoint index pairs (out of 3 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 81 treesize of output 105 [2018-01-23 14:54:43,735 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 14 treesize of output 13 [2018-01-23 14:54:43,735 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:43,747 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:43,759 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:43,762 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 38 [2018-01-23 14:54:43,764 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-23 14:54:43,764 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:43,769 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:43,779 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-23 14:54:43,779 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 3 variables, input treesize:87, output treesize:71 [2018-01-23 14:54:43,837 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 40 treesize of output 34 [2018-01-23 14:54:43,839 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-23 14:54:43,839 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:43,843 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 7 [2018-01-23 14:54:43,844 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:43,846 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:43,852 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-23 14:54:43,853 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 2 variables, input treesize:103, output treesize:67 [2018-01-23 14:54:43,955 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:43,960 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:43,963 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 4 disjoint index pairs (out of 6 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 72 treesize of output 82 [2018-01-23 14:54:43,971 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 2 case distinctions, treesize of input 20 treesize of output 27 [2018-01-23 14:54:43,972 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-23 14:54:43,988 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-23 14:54:44,006 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 2 xjuncts. [2018-01-23 14:54:44,007 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:78, output treesize:104 [2018-01-23 14:54:44,075 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:44,076 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:44,079 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:44,081 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 4 disjoint index pairs (out of 3 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 58 treesize of output 72 [2018-01-23 14:54:44,084 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:44,085 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-23 14:54:44,085 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:44,093 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:44,099 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:44,099 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:64, output treesize:45 [2018-01-23 14:54:44,396 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:44,397 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:44,398 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:44,399 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 6 disjoint index pairs (out of 3 index pairs), introduced 5 new quantified variables, introduced 0 case distinctions, treesize of input 67 treesize of output 55 [2018-01-23 14:54:44,409 INFO L477 Elim1Store]: Elim1 applied some preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 3 new quantified variables, introduced 1 case distinctions, treesize of input 19 treesize of output 25 [2018-01-23 14:54:44,410 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:44,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-23 14:54:44,420 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:44,436 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 1 new quantified variables, introduced 1 case distinctions, treesize of input 18 treesize of output 17 [2018-01-23 14:54:44,437 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 2 xjuncts. [2018-01-23 14:54:44,471 INFO L267 ElimStorePlain]: Start of recursive call 2: 3 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-23 14:54:44,490 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:44,493 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:44,495 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 4 disjoint index pairs (out of 3 index pairs), introduced 5 new quantified variables, introduced 0 case distinctions, treesize of input 59 treesize of output 49 [2018-01-23 14:54:44,517 INFO L477 Elim1Store]: Elim1 applied some preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 3 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 24 treesize of output 41 [2018-01-23 14:54:44,519 INFO L267 ElimStorePlain]: Start of recursive call 7: 5 dim-0 vars, End of recursive call: 5 dim-0 vars, and 7 xjuncts. [2018-01-23 14:54:44,538 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 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 9 [2018-01-23 14:54:44,538 INFO L267 ElimStorePlain]: Start of recursive call 8: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:44,540 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 2 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-23 14:54:44,540 INFO L267 ElimStorePlain]: Start of recursive call 9: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:44,546 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-23 14:54:44,546 INFO L267 ElimStorePlain]: Start of recursive call 10: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:44,550 INFO L267 ElimStorePlain]: Start of recursive call 6: 3 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-23 14:54:44,558 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 2 dim-2 vars, End of recursive call: and 3 xjuncts. [2018-01-23 14:54:44,558 INFO L202 ElimStorePlain]: Needed 10 recursive calls to eliminate 4 variables, input treesize:127, output treesize:13 [2018-01-23 14:54:44,806 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-01-23 14:54:44,826 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-23 14:54:44,826 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [33, 28] total 59 [2018-01-23 14:54:44,827 INFO L409 AbstractCegarLoop]: Interpolant automaton has 59 states [2018-01-23 14:54:44,827 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 59 interpolants. [2018-01-23 14:54:44,828 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=168, Invalid=3254, Unknown=0, NotChecked=0, Total=3422 [2018-01-23 14:54:44,828 INFO L87 Difference]: Start difference. First operand 282 states and 300 transitions. Second operand 59 states. [2018-01-23 14:54:48,600 WARN L146 SmtUtils]: Spent 106ms on a formula simplification. DAG size of input: 91 DAG size of output 57 [2018-01-23 14:54:50,800 WARN L146 SmtUtils]: Spent 112ms on a formula simplification. DAG size of input: 124 DAG size of output 93 [2018-01-23 14:54:51,070 WARN L146 SmtUtils]: Spent 115ms on a formula simplification. DAG size of input: 132 DAG size of output 100 [2018-01-23 14:54:52,541 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:54:52,541 INFO L93 Difference]: Finished difference Result 355 states and 376 transitions. [2018-01-23 14:54:52,541 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 58 states. [2018-01-23 14:54:52,541 INFO L78 Accepts]: Start accepts. Automaton has 59 states. Word has length 96 [2018-01-23 14:54:52,541 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:54:52,542 INFO L225 Difference]: With dead ends: 355 [2018-01-23 14:54:52,542 INFO L226 Difference]: Without dead ends: 333 [2018-01-23 14:54:52,545 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 188 GetRequests, 73 SyntacticMatches, 3 SemanticMatches, 112 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2947 ImplicationChecksByTransitivity, 7.3s TimeCoverageRelationStatistics Valid=1139, Invalid=11743, Unknown=0, NotChecked=0, Total=12882 [2018-01-23 14:54:52,545 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 333 states. [2018-01-23 14:54:52,556 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 333 to 282. [2018-01-23 14:54:52,556 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 282 states. [2018-01-23 14:54:52,558 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 282 states to 282 states and 300 transitions. [2018-01-23 14:54:52,558 INFO L78 Accepts]: Start accepts. Automaton has 282 states and 300 transitions. Word has length 96 [2018-01-23 14:54:52,558 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:54:52,559 INFO L432 AbstractCegarLoop]: Abstraction has 282 states and 300 transitions. [2018-01-23 14:54:52,559 INFO L433 AbstractCegarLoop]: Interpolant automaton has 59 states. [2018-01-23 14:54:52,559 INFO L276 IsEmpty]: Start isEmpty. Operand 282 states and 300 transitions. [2018-01-23 14:54:52,560 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 99 [2018-01-23 14:54:52,560 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:54:52,560 INFO L322 BasicCegarLoop]: trace histogram [3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 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-23 14:54:52,561 INFO L371 AbstractCegarLoop]: === Iteration 14 === [mainErr0EnsuresViolation]=== [2018-01-23 14:54:52,561 INFO L82 PathProgramCache]: Analyzing trace with hash -1625479587, now seen corresponding path program 1 times [2018-01-23 14:54:52,561 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:54:52,561 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:54:52,562 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:54:52,562 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-01-23 14:54:52,562 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:54:52,577 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:54:52,578 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:54:53,159 INFO L134 CoverageAnalysis]: Checked inductivity of 21 backedges. 4 proven. 17 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-23 14:54:53,159 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-23 14:54:53,159 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-23 14:54:53,164 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:54:53,191 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:54:53,195 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-23 14:54:53,197 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-23 14:54:53,197 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:53,198 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:53,198 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:6, output treesize:5 [2018-01-23 14:54:53,247 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:53,247 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:53,248 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-23 14:54:53,248 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:53,252 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:53,252 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:20, output treesize:14 [2018-01-23 14:54:53,271 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-23 14:54:53,273 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-23 14:54:53,273 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:53,275 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:53,282 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-23 14:54:53,284 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-23 14:54:53,284 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:53,285 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:53,291 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-23 14:54:53,292 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 3 variables, input treesize:33, output treesize:22 [2018-01-23 14:54:53,336 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:53,340 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-23 14:54:53,341 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-23 14:54:53,341 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:53,346 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:53,355 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:53,357 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-23 14:54:53,359 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-23 14:54:53,359 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:53,363 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:53,369 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-23 14:54:53,370 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 3 variables, input treesize:64, output treesize:48 [2018-01-23 14:54:53,403 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-23 14:54:53,404 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-23 14:54:53,404 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:53,409 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-23 14:54:53,409 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:53,410 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:53,414 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-23 14:54:53,414 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 2 variables, input treesize:56, output treesize:32 [2018-01-23 14:54:53,473 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-23 14:54:53,480 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 2 case distinctions, treesize of input 16 treesize of output 23 [2018-01-23 14:54:53,481 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-23 14:54:53,490 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-23 14:54:53,505 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 2 xjuncts. [2018-01-23 14:54:53,505 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:43, output treesize:62 [2018-01-23 14:54:53,544 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:53,547 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-23 14:54:53,549 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:54:53,550 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-23 14:54:53,550 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:53,555 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:53,559 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:53,559 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:45, output treesize:26 [2018-01-23 14:54:53,787 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 47 treesize of output 31 [2018-01-23 14:54:53,789 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 2 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 13 [2018-01-23 14:54:53,789 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:53,794 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-23 14:54:53,794 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:53,797 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:53,806 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 39 treesize of output 33 [2018-01-23 14:54:53,808 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 26 treesize of output 17 [2018-01-23 14:54:53,808 INFO L267 ElimStorePlain]: Start of recursive call 6: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:53,811 INFO L267 ElimStorePlain]: Start of recursive call 5: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:53,819 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-23 14:54:53,820 INFO L202 ElimStorePlain]: Needed 6 recursive calls to eliminate 4 variables, input treesize:87, output treesize:45 [2018-01-23 14:54:54,014 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 27 treesize of output 25 [2018-01-23 14:54:54,016 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-23 14:54:54,016 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:54,022 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-23 14:54:54,022 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:54,024 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:54,033 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 31 treesize of output 23 [2018-01-23 14:54:54,035 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 14 treesize of output 10 [2018-01-23 14:54:54,035 INFO L267 ElimStorePlain]: Start of recursive call 6: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:54,039 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-23 14:54:54,039 INFO L267 ElimStorePlain]: Start of recursive call 7: End of recursive call: and 1 xjuncts. [2018-01-23 14:54:54,042 INFO L267 ElimStorePlain]: Start of recursive call 5: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:54:54,047 INFO L267 ElimStorePlain]: Start of recursive call 1: 4 dim-0 vars, 2 dim-2 vars, End of recursive call: and 2 xjuncts. [2018-01-23 14:54:54,047 INFO L202 ElimStorePlain]: Needed 7 recursive calls to eliminate 6 variables, input treesize:59, output treesize:9 [2018-01-23 14:54:54,192 INFO L134 CoverageAnalysis]: Checked inductivity of 21 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-23 14:54:54,213 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-23 14:54:54,213 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [28, 28] total 54 [2018-01-23 14:54:54,213 INFO L409 AbstractCegarLoop]: Interpolant automaton has 54 states [2018-01-23 14:54:54,213 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 54 interpolants. [2018-01-23 14:54:54,214 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=149, Invalid=2713, Unknown=0, NotChecked=0, Total=2862 [2018-01-23 14:54:54,214 INFO L87 Difference]: Start difference. First operand 282 states and 300 transitions. Second operand 54 states. [2018-01-23 14:54:56,724 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:54:56,724 INFO L93 Difference]: Finished difference Result 332 states and 351 transitions. [2018-01-23 14:54:56,724 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2018-01-23 14:54:56,724 INFO L78 Accepts]: Start accepts. Automaton has 54 states. Word has length 98 [2018-01-23 14:54:56,725 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:54:56,725 INFO L225 Difference]: With dead ends: 332 [2018-01-23 14:54:56,726 INFO L226 Difference]: Without dead ends: 252 [2018-01-23 14:54:56,727 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 156 GetRequests, 76 SyntacticMatches, 1 SemanticMatches, 79 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1492 ImplicationChecksByTransitivity, 2.4s TimeCoverageRelationStatistics Valid=601, Invalid=5879, Unknown=0, NotChecked=0, Total=6480 [2018-01-23 14:54:56,727 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 252 states. [2018-01-23 14:54:56,736 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 252 to 237. [2018-01-23 14:54:56,736 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 237 states. [2018-01-23 14:54:56,737 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 237 states to 237 states and 252 transitions. [2018-01-23 14:54:56,737 INFO L78 Accepts]: Start accepts. Automaton has 237 states and 252 transitions. Word has length 98 [2018-01-23 14:54:56,738 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:54:56,738 INFO L432 AbstractCegarLoop]: Abstraction has 237 states and 252 transitions. [2018-01-23 14:54:56,738 INFO L433 AbstractCegarLoop]: Interpolant automaton has 54 states. [2018-01-23 14:54:56,738 INFO L276 IsEmpty]: Start isEmpty. Operand 237 states and 252 transitions. [2018-01-23 14:54:56,739 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 99 [2018-01-23 14:54:56,739 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:54:56,739 INFO L322 BasicCegarLoop]: trace histogram [3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 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-23 14:54:56,739 INFO L371 AbstractCegarLoop]: === Iteration 15 === [mainErr0EnsuresViolation]=== [2018-01-23 14:54:56,740 INFO L82 PathProgramCache]: Analyzing trace with hash -1049846416, now seen corresponding path program 4 times [2018-01-23 14:54:56,740 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:54:56,740 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:54:56,741 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:54:56,741 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:54:56,741 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:54:56,759 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:54:56,760 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:54:57,359 INFO L134 CoverageAnalysis]: Checked inductivity of 35 backedges. 0 proven. 33 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-01-23 14:54:57,359 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-23 14:54:57,359 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-23 14:54:57,364 INFO L101 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST Received shutdown request... [2018-01-23 14:55:01,456 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-23 14:55:01,463 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-23 14:55:01,465 INFO L175 TraceCheckSpWp]: Timeout while computing interpolants [2018-01-23 14:55:01,465 WARN L491 AbstractCegarLoop]: Verification canceled [2018-01-23 14:55:01,468 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 23.01 02:55:01 BoogieIcfgContainer [2018-01-23 14:55:01,468 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-01-23 14:55:01,469 INFO L168 Benchmark]: Toolchain (without parser) took 51464.23 ms. Allocated memory was 307.2 MB in the beginning and 778.0 MB in the end (delta: 470.8 MB). Free memory was 264.5 MB in the beginning and 465.3 MB in the end (delta: -200.7 MB). Peak memory consumption was 270.1 MB. Max. memory is 5.3 GB. [2018-01-23 14:55:01,471 INFO L168 Benchmark]: CDTParser took 0.15 ms. Allocated memory is still 307.2 MB. Free memory is still 270.5 MB. There was no memory consumed. Max. memory is 5.3 GB. [2018-01-23 14:55:01,471 INFO L168 Benchmark]: CACSL2BoogieTranslator took 224.66 ms. Allocated memory is still 307.2 MB. Free memory was 264.5 MB in the beginning and 252.6 MB in the end (delta: 12.0 MB). Peak memory consumption was 12.0 MB. Max. memory is 5.3 GB. [2018-01-23 14:55:01,471 INFO L168 Benchmark]: Boogie Preprocessor took 45.58 ms. Allocated memory is still 307.2 MB. Free memory was 252.6 MB in the beginning and 250.6 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 5.3 GB. [2018-01-23 14:55:01,472 INFO L168 Benchmark]: RCFGBuilder took 465.00 ms. Allocated memory is still 307.2 MB. Free memory was 250.6 MB in the beginning and 220.1 MB in the end (delta: 30.5 MB). Peak memory consumption was 30.5 MB. Max. memory is 5.3 GB. [2018-01-23 14:55:01,472 INFO L168 Benchmark]: TraceAbstraction took 50720.97 ms. Allocated memory was 307.2 MB in the beginning and 778.0 MB in the end (delta: 470.8 MB). Free memory was 220.1 MB in the beginning and 465.3 MB in the end (delta: -245.2 MB). Peak memory consumption was 225.6 MB. Max. memory is 5.3 GB. [2018-01-23 14:55:01,474 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.15 ms. Allocated memory is still 307.2 MB. Free memory is still 270.5 MB. There was no memory consumed. Max. memory is 5.3 GB. * CACSL2BoogieTranslator took 224.66 ms. Allocated memory is still 307.2 MB. Free memory was 264.5 MB in the beginning and 252.6 MB in the end (delta: 12.0 MB). Peak memory consumption was 12.0 MB. Max. memory is 5.3 GB. * Boogie Preprocessor took 45.58 ms. Allocated memory is still 307.2 MB. Free memory was 252.6 MB in the beginning and 250.6 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 5.3 GB. * RCFGBuilder took 465.00 ms. Allocated memory is still 307.2 MB. Free memory was 250.6 MB in the beginning and 220.1 MB in the end (delta: 30.5 MB). Peak memory consumption was 30.5 MB. Max. memory is 5.3 GB. * TraceAbstraction took 50720.97 ms. Allocated memory was 307.2 MB in the beginning and 778.0 MB in the end (delta: 470.8 MB). Free memory was 220.1 MB in the beginning and 465.3 MB in the end (delta: -245.2 MB). Peak memory consumption was 225.6 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, 97 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=97occurred 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: [L995] EXPR, FCALL malloc(sizeof(struct TSLL)) VAL [malloc(sizeof(struct TSLL))={19:0}] [L995] struct TSLL* null = malloc(sizeof(struct TSLL)); VAL [malloc(sizeof(struct TSLL))={19:0}, null={19:0}] [L996] FCALL null->next = ((void*)0) VAL [malloc(sizeof(struct TSLL))={19:0}, null={19:0}] [L997] FCALL null->prev = ((void*)0) VAL [malloc(sizeof(struct TSLL))={19:0}, null={19:0}] [L998] FCALL null->colour = BLACK VAL [malloc(sizeof(struct TSLL))={19:0}, null={19:0}] [L1000] EXPR, FCALL malloc(sizeof(struct TSLL)) VAL [malloc(sizeof(struct TSLL))={17:0}, malloc(sizeof(struct TSLL))={19:0}, null={19:0}] [L1000] struct TSLL* list = malloc(sizeof(struct TSLL)); VAL [list={17:0}, malloc(sizeof(struct TSLL))={17:0}, malloc(sizeof(struct TSLL))={19:0}, null={19:0}] [L1001] FCALL list->next = null VAL [list={17:0}, malloc(sizeof(struct TSLL))={17:0}, malloc(sizeof(struct TSLL))={19:0}, null={19:0}] [L1002] FCALL list->prev = null VAL [list={17:0}, malloc(sizeof(struct TSLL))={17:0}, malloc(sizeof(struct TSLL))={19:0}, null={19:0}] [L1003] FCALL list->colour = BLACK VAL [list={17:0}, malloc(sizeof(struct TSLL))={17:0}, malloc(sizeof(struct TSLL))={19:0}, null={19:0}] [L1005] struct TSLL* end = list; VAL [end={17:0}, list={17:0}, malloc(sizeof(struct TSLL))={17:0}, malloc(sizeof(struct TSLL))={19:0}, null={19:0}] [L1008] COND FALSE !(__VERIFIER_nondet_int()) [L1034] end = null [L1035] end = list VAL [end={17:0}, list={17:0}, malloc(sizeof(struct TSLL))={17:0}, malloc(sizeof(struct TSLL))={19:0}, null={19:0}] [L1038] COND FALSE !(!(null != end)) VAL [end={17:0}, list={17:0}, malloc(sizeof(struct TSLL))={17:0}, malloc(sizeof(struct TSLL))={19:0}, null={19:0}] [L1038] COND FALSE !(0) VAL [end={17:0}, list={17:0}, malloc(sizeof(struct TSLL))={17:0}, malloc(sizeof(struct TSLL))={19:0}, null={19:0}] [L1039] EXPR, FCALL end->colour VAL [end={17:0}, end->colour=1, list={17:0}, malloc(sizeof(struct TSLL))={17:0}, malloc(sizeof(struct TSLL))={19:0}, null={19:0}] [L1039] COND FALSE !(!(BLACK == end->colour)) [L1039] COND FALSE !(0) VAL [end={17:0}, list={17:0}, malloc(sizeof(struct TSLL))={17:0}, malloc(sizeof(struct TSLL))={19:0}, null={19:0}] [L1040] COND TRUE null != end VAL [end={17:0}, list={17:0}, malloc(sizeof(struct TSLL))={17:0}, malloc(sizeof(struct TSLL))={19:0}, null={19:0}] [L1042] EXPR, FCALL end->colour VAL [end={17:0}, end->colour=1, list={17:0}, malloc(sizeof(struct TSLL))={17:0}, malloc(sizeof(struct TSLL))={19:0}, null={19:0}] [L1042] COND FALSE !(RED == end->colour) [L1049] EXPR, FCALL end->next VAL [end={17:0}, end->next={19:0}, list={17:0}, malloc(sizeof(struct TSLL))={17:0}, malloc(sizeof(struct TSLL))={19:0}, null={19:0}] [L1049] end = end->next [L1040] COND FALSE !(null != end) VAL [end={19:0}, list={17:0}, malloc(sizeof(struct TSLL))={17:0}, malloc(sizeof(struct TSLL))={19:0}, null={19:0}] [L1053] COND TRUE null != list VAL [end={19:0}, list={17:0}, malloc(sizeof(struct TSLL))={17:0}, malloc(sizeof(struct TSLL))={19:0}, null={19:0}] [L1055] EXPR, FCALL list->colour VAL [end={19:0}, list={17:0}, list->colour=1, malloc(sizeof(struct TSLL))={17:0}, malloc(sizeof(struct TSLL))={19:0}, null={19:0}] [L1055] COND FALSE !(RED == list->colour) [L1064] EXPR, FCALL list->next VAL [end={19:0}, list={17:0}, list->next={19:0}, malloc(sizeof(struct TSLL))={17:0}, malloc(sizeof(struct TSLL))={19:0}, null={19:0}] [L1064] end = list->next [L1065] FCALL free(list) VAL [end={19:0}, list={17:0}, malloc(sizeof(struct TSLL))={17:0}, malloc(sizeof(struct TSLL))={19:0}, null={19:0}] [L1066] list = end VAL [end={19:0}, list={19:0}, malloc(sizeof(struct TSLL))={17:0}, malloc(sizeof(struct TSLL))={19:0}, null={19:0}] [L1053] COND FALSE !(null != list) VAL [end={19:0}, list={19:0}, malloc(sizeof(struct TSLL))={17:0}, malloc(sizeof(struct TSLL))={19:0}, null={19:0}] [L1070] FCALL free(null) VAL [end={19:0}, list={19:0}, malloc(sizeof(struct TSLL))={17:0}, malloc(sizeof(struct TSLL))={19:0}, null={19:0}] [L1072] return 0; - StatisticsResult: Ultimate Automizer benchmark data for error location: ULTIMATE.startErr0EnsuresViolation CFG has 3 procedures, 97 locations, 3 error locations. UNSAFE Result, 1.3s OverallTime, 4 OverallIterations, 2 TraceHistogramMax, 0.6s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 232 SDtfs, 1017 SDslu, 255 SDs, 0 SdLazy, 273 SolverSat, 18 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.3s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 30 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.2s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=98occurred in iteration=3, 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, 3 MinimizatonAttempts, 67 StatesRemovedByMinimization, 2 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.0s SatisfiabilityAnalysisTime, 0.3s InterpolantComputationTime, 155 NumberOfCodeBlocks, 155 NumberOfCodeBlocksAsserted, 4 NumberOfCheckSat, 102 ConstructedInterpolants, 0 QuantifiedInterpolants, 8922 SizeOfPredicates, 0 NumberOfNonLiveVariables, 0 ConjunctsInSsa, 0 ConjunctsInUnsatCore, 3 InterpolantComputations, 3 PerfectInterpolantSequences, 2/2 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, REUSE_STATISTICS: No data available - TimeoutResultAtElement [Line: 993]: Timeout (TraceAbstraction) Unable to prove that all allocated memory was freed (line 993). Cancelled while BasicCegarLoop was analyzing trace of length 99 with TraceHistMax 3, while TraceCheckSpWp was constructing forward predicates, while XnfDer was eliminating 1 quantified variables from 1 xjuncts. - StatisticsResult: Ultimate Automizer benchmark data for error location: mainErr0EnsuresViolation CFG has 3 procedures, 97 locations, 3 error locations. TIMEOUT Result, 49.2s OverallTime, 15 OverallIterations, 4 TraceHistogramMax, 26.8s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 1101 SDtfs, 8104 SDslu, 14370 SDs, 0 SdLazy, 18497 SolverSat, 1181 SolverUnsat, 136 SolverUnknown, 0 SolverNotchecked, 10.4s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 1296 GetRequests, 645 SyntacticMatches, 28 SemanticMatches, 623 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9580 ImplicationChecksByTransitivity, 25.7s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=294occurred in iteration=11, 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, 14 MinimizatonAttempts, 527 StatesRemovedByMinimization, 13 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.1s SsaConstructionTime, 0.9s SatisfiabilityAnalysisTime, 15.8s InterpolantComputationTime, 1731 NumberOfCodeBlocks, 1731 NumberOfCodeBlocksAsserted, 30 NumberOfCheckSat, 1707 ConstructedInterpolants, 161 QuantifiedInterpolants, 3102483 SizeOfPredicates, 177 NumberOfNonLiveVariables, 2199 ConjunctsInSsa, 456 ConjunctsInUnsatCore, 24 InterpolantComputations, 5 PerfectInterpolantSequences, 99/351 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-rb-sentinel_true-unreach-call_true-valid-memsafety.i_mempurity-32bit-Automizer_Camel+AI_EQ.epf_AutomizerC.xml/Csv-Benchmark-0-2018-01-23_14-55-01-483.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/dll-rb-sentinel_true-unreach-call_true-valid-memsafety.i_mempurity-32bit-Automizer_Camel+AI_EQ.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-0-2018-01-23_14-55-01-483.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/dll-rb-sentinel_true-unreach-call_true-valid-memsafety.i_mempurity-32bit-Automizer_Camel+AI_EQ.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-1-2018-01-23_14-55-01-483.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/dll-rb-sentinel_true-unreach-call_true-valid-memsafety.i_mempurity-32bit-Automizer_Camel+AI_EQ.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-2-2018-01-23_14-55-01-483.csv Completed graceful shutdown