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/list-ext-properties/test-0513_1_true-valid-memsafety.i -------------------------------------------------------------------------------- This is Ultimate 0.1.23-2f49842 [2018-01-20 22:10:31,876 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-01-20 22:10:31,878 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-01-20 22:10:31,891 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-01-20 22:10:31,892 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-01-20 22:10:31,892 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-01-20 22:10:31,893 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-01-20 22:10:31,894 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-01-20 22:10:31,896 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-01-20 22:10:31,896 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-01-20 22:10:31,897 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-01-20 22:10:31,897 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-01-20 22:10:31,898 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-01-20 22:10:31,898 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-01-20 22:10:31,899 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-01-20 22:10:31,901 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-01-20 22:10:31,904 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-01-20 22:10:31,906 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-01-20 22:10:31,907 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-01-20 22:10:31,908 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-01-20 22:10:31,910 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-01-20 22:10:31,911 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-01-20 22:10:31,911 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-01-20 22:10:31,912 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-01-20 22:10:31,913 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-01-20 22:10:31,914 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-01-20 22:10:31,914 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-01-20 22:10:31,915 INFO L177 SettingsManager]: PEA to Boogie provides no preferences, ignoring... [2018-01-20 22:10:31,915 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-01-20 22:10:31,915 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-01-20 22:10:31,916 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-01-20 22:10:31,916 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/ai/eq-bench/mempurity-32bit-Automizer_Camel+AI_EQ.epf [2018-01-20 22:10:31,926 INFO L110 SettingsManager]: Loading preferences was successful [2018-01-20 22:10:31,926 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-01-20 22:10:31,927 INFO L131 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2018-01-20 22:10:31,927 INFO L133 SettingsManager]: * to procedures, called more than once=true [2018-01-20 22:10:31,928 INFO L131 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2018-01-20 22:10:31,928 INFO L133 SettingsManager]: * Abstract domain for RCFG-of-the-future=VPDomain [2018-01-20 22:10:31,928 INFO L133 SettingsManager]: * Use the RCFG-of-the-future interface=true [2018-01-20 22:10:31,929 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-01-20 22:10:31,929 INFO L133 SettingsManager]: * sizeof long=4 [2018-01-20 22:10:31,929 INFO L133 SettingsManager]: * Check unreachability of error function in SV-COMP mode=false [2018-01-20 22:10:31,929 INFO L133 SettingsManager]: * Check allocation purity=true [2018-01-20 22:10:31,929 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-01-20 22:10:31,930 INFO L133 SettingsManager]: * sizeof POINTER=4 [2018-01-20 22:10:31,930 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-01-20 22:10:31,930 INFO L133 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2018-01-20 22:10:31,930 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-01-20 22:10:31,930 INFO L133 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2018-01-20 22:10:31,931 INFO L133 SettingsManager]: * sizeof long double=12 [2018-01-20 22:10:31,931 INFO L133 SettingsManager]: * Check if freed pointer was valid=false [2018-01-20 22:10:31,931 INFO L133 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2018-01-20 22:10:31,931 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-01-20 22:10:31,931 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-01-20 22:10:31,932 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-01-20 22:10:31,932 INFO L133 SettingsManager]: * Add additional assume for each assert=false [2018-01-20 22:10:31,932 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-01-20 22:10:31,932 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-01-20 22:10:31,932 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-01-20 22:10:31,933 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-01-20 22:10:31,933 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-01-20 22:10:31,933 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-01-20 22:10:31,933 INFO L133 SettingsManager]: * Stop after first violation was found=false [2018-01-20 22:10:31,933 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-01-20 22:10:31,934 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-01-20 22:10:31,934 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-01-20 22:10:31,934 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-01-20 22:10:31,935 INFO L131 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2018-01-20 22:10:31,935 INFO L133 SettingsManager]: * TransformationType=HEAP_SEPARATOR [2018-01-20 22:10:31,969 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-01-20 22:10:31,982 INFO L266 ainManager$Toolchain]: [Toolchain 1]: Parser(s) successfully initialized [2018-01-20 22:10:31,987 INFO L222 ainManager$Toolchain]: [Toolchain 1]: Toolchain data selected. [2018-01-20 22:10:31,988 INFO L271 PluginConnector]: Initializing CDTParser... [2018-01-20 22:10:31,989 INFO L276 PluginConnector]: CDTParser initialized [2018-01-20 22:10:31,990 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/list-ext-properties/test-0513_1_true-valid-memsafety.i [2018-01-20 22:10:32,183 INFO L304 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-01-20 22:10:32,188 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2018-01-20 22:10:32,189 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2018-01-20 22:10:32,189 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2018-01-20 22:10:32,193 INFO L276 PluginConnector]: CACSL2BoogieTranslator initialized [2018-01-20 22:10:32,194 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.01 10:10:32" (1/1) ... [2018-01-20 22:10:32,197 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@41741684 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 10:10:32, skipping insertion in model container [2018-01-20 22:10:32,197 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.01 10:10:32" (1/1) ... [2018-01-20 22:10:32,211 INFO L153 Dispatcher]: Using SV-COMP mode [2018-01-20 22:10:32,249 INFO L153 Dispatcher]: Using SV-COMP mode [2018-01-20 22:10:32,371 INFO L450 PostProcessor]: Settings: Checked method=main [2018-01-20 22:10:32,396 INFO L450 PostProcessor]: Settings: Checked method=main [2018-01-20 22:10:32,406 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 10:10:32 WrapperNode [2018-01-20 22:10:32,406 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2018-01-20 22:10:32,407 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-01-20 22:10:32,407 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-01-20 22:10:32,407 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-01-20 22:10:32,423 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 10:10:32" (1/1) ... [2018-01-20 22:10:32,423 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 10:10:32" (1/1) ... [2018-01-20 22:10:32,436 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 10:10:32" (1/1) ... [2018-01-20 22:10:32,436 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 10:10:32" (1/1) ... [2018-01-20 22:10:32,443 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 10:10:32" (1/1) ... [2018-01-20 22:10:32,448 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 10:10:32" (1/1) ... [2018-01-20 22:10:32,450 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 10:10:32" (1/1) ... [2018-01-20 22:10:32,452 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-01-20 22:10:32,452 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-01-20 22:10:32,452 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-01-20 22:10:32,453 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-01-20 22:10:32,454 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 10:10:32" (1/1) ... No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-01-20 22:10:32,498 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2018-01-20 22:10:32,498 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-01-20 22:10:32,498 INFO L136 BoogieDeclarations]: Found implementation of procedure main [2018-01-20 22:10:32,498 INFO L128 BoogieDeclarations]: Found specification of procedure write~int [2018-01-20 22:10:32,499 INFO L128 BoogieDeclarations]: Found specification of procedure read~int [2018-01-20 22:10:32,499 INFO L128 BoogieDeclarations]: Found specification of procedure write~$Pointer$ [2018-01-20 22:10:32,499 INFO L128 BoogieDeclarations]: Found specification of procedure read~$Pointer$ [2018-01-20 22:10:32,499 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.free [2018-01-20 22:10:32,499 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2018-01-20 22:10:32,499 INFO L128 BoogieDeclarations]: Found specification of procedure #Ultimate.alloc [2018-01-20 22:10:32,499 INFO L128 BoogieDeclarations]: Found specification of procedure malloc [2018-01-20 22:10:32,499 INFO L128 BoogieDeclarations]: Found specification of procedure free [2018-01-20 22:10:32,499 INFO L128 BoogieDeclarations]: Found specification of procedure abort [2018-01-20 22:10:32,500 INFO L128 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2018-01-20 22:10:32,500 INFO L128 BoogieDeclarations]: Found specification of procedure main [2018-01-20 22:10:32,500 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2018-01-20 22:10:32,500 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-01-20 22:10:32,899 INFO L257 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-01-20 22:10:32,900 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.01 10:10:32 BoogieIcfgContainer [2018-01-20 22:10:32,900 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-01-20 22:10:32,900 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-01-20 22:10:32,900 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-01-20 22:10:32,902 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-01-20 22:10:32,903 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 20.01 10:10:32" (1/3) ... [2018-01-20 22:10:32,904 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@532eec50 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.01 10:10:32, skipping insertion in model container [2018-01-20 22:10:32,904 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.01 10:10:32" (2/3) ... [2018-01-20 22:10:32,904 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@532eec50 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.01 10:10:32, skipping insertion in model container [2018-01-20 22:10:32,904 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.01 10:10:32" (3/3) ... [2018-01-20 22:10:32,907 INFO L105 eAbstractionObserver]: Analyzing ICFG test-0513_1_true-valid-memsafety.i [2018-01-20 22:10:32,915 INFO L130 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-01-20 22:10:32,921 INFO L142 ceAbstractionStarter]: Appying trace abstraction to program that has 3 error locations. [2018-01-20 22:10:32,975 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-20 22:10:32,975 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-20 22:10:32,976 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-20 22:10:32,976 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-20 22:10:32,976 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-20 22:10:32,976 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-20 22:10:32,976 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-20 22:10:32,977 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == ULTIMATE.initErr0EnsuresViolation======== [2018-01-20 22:10:32,978 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-20 22:10:33,002 INFO L276 IsEmpty]: Start isEmpty. Operand 91 states. [2018-01-20 22:10:33,009 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 4 [2018-01-20 22:10:33,009 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:10:33,010 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1] [2018-01-20 22:10:33,011 INFO L371 AbstractCegarLoop]: === Iteration 1 === [ULTIMATE.initErr0EnsuresViolation]=== [2018-01-20 22:10:33,017 INFO L82 PathProgramCache]: Analyzing trace with hash 217246, now seen corresponding path program 1 times [2018-01-20 22:10:33,019 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:10:33,020 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:10:33,083 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:10:33,083 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:10:33,083 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:10:33,121 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2018-01-20 22:10:33,128 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2018-01-20 22:10:33,150 INFO L381 BasicCegarLoop]: Counterexample might be feasible [2018-01-20 22:10:33,158 WARN L343 cessorBacktranslator]: Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) [2018-01-20 22:10:33,167 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-20 22:10:33,168 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-20 22:10:33,168 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-20 22:10:33,168 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-20 22:10:33,168 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-20 22:10:33,168 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-20 22:10:33,168 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-20 22:10:33,169 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == ULTIMATE.startErr0EnsuresViolation======== [2018-01-20 22:10:33,169 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-20 22:10:33,172 INFO L276 IsEmpty]: Start isEmpty. Operand 91 states. [2018-01-20 22:10:33,173 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2018-01-20 22:10:33,173 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:10:33,174 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 22:10:33,174 INFO L371 AbstractCegarLoop]: === Iteration 1 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-20 22:10:33,174 INFO L82 PathProgramCache]: Analyzing trace with hash 843511722, now seen corresponding path program 1 times [2018-01-20 22:10:33,174 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:10:33,175 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:10:33,176 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:10:33,176 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:10:33,176 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:10:33,185 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:10:33,195 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:10:33,227 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 22:10:33,229 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-20 22:10:33,229 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-01-20 22:10:33,231 INFO L409 AbstractCegarLoop]: Interpolant automaton has 2 states [2018-01-20 22:10:33,334 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2018-01-20 22:10:33,335 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-01-20 22:10:33,337 INFO L87 Difference]: Start difference. First operand 91 states. Second operand 2 states. [2018-01-20 22:10:33,364 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:10:33,364 INFO L93 Difference]: Finished difference Result 175 states and 213 transitions. [2018-01-20 22:10:33,365 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2018-01-20 22:10:33,366 INFO L78 Accepts]: Start accepts. Automaton has 2 states. Word has length 11 [2018-01-20 22:10:33,367 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:10:33,378 INFO L225 Difference]: With dead ends: 175 [2018-01-20 22:10:33,378 INFO L226 Difference]: Without dead ends: 88 [2018-01-20 22:10:33,381 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-01-20 22:10:33,394 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 88 states. [2018-01-20 22:10:33,413 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 88 to 88. [2018-01-20 22:10:33,414 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 88 states. [2018-01-20 22:10:33,417 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 88 states to 88 states and 102 transitions. [2018-01-20 22:10:33,418 INFO L78 Accepts]: Start accepts. Automaton has 88 states and 102 transitions. Word has length 11 [2018-01-20 22:10:33,418 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:10:33,418 INFO L432 AbstractCegarLoop]: Abstraction has 88 states and 102 transitions. [2018-01-20 22:10:33,418 INFO L433 AbstractCegarLoop]: Interpolant automaton has 2 states. [2018-01-20 22:10:33,419 INFO L276 IsEmpty]: Start isEmpty. Operand 88 states and 102 transitions. [2018-01-20 22:10:33,419 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2018-01-20 22:10:33,419 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:10:33,419 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 22:10:33,419 INFO L371 AbstractCegarLoop]: === Iteration 2 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-20 22:10:33,420 INFO L82 PathProgramCache]: Analyzing trace with hash -578790635, now seen corresponding path program 1 times [2018-01-20 22:10:33,420 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:10:33,420 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:10:33,421 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:10:33,421 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:10:33,421 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:10:33,438 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2018-01-20 22:10:33,450 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2018-01-20 22:10:33,455 INFO L381 BasicCegarLoop]: Counterexample might be feasible [2018-01-20 22:10:33,459 WARN L343 cessorBacktranslator]: Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) [2018-01-20 22:10:33,461 WARN L343 cessorBacktranslator]: Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) [2018-01-20 22:10:33,461 WARN L343 cessorBacktranslator]: Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) [2018-01-20 22:10:33,469 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-20 22:10:33,469 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-20 22:10:33,469 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-20 22:10:33,469 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-20 22:10:33,469 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-20 22:10:33,470 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-20 22:10:33,470 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-20 22:10:33,470 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == mainErr0EnsuresViolation======== [2018-01-20 22:10:33,470 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-20 22:10:33,472 INFO L276 IsEmpty]: Start isEmpty. Operand 91 states. [2018-01-20 22:10:33,473 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2018-01-20 22:10:33,473 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:10:33,473 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 22:10:33,473 INFO L371 AbstractCegarLoop]: === Iteration 1 === [mainErr0EnsuresViolation]=== [2018-01-20 22:10:33,474 INFO L82 PathProgramCache]: Analyzing trace with hash 1681322799, now seen corresponding path program 1 times [2018-01-20 22:10:33,474 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:10:33,474 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:10:33,475 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:10:33,475 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:10:33,475 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:10:33,482 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:10:33,483 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:10:33,493 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 22:10:33,494 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-20 22:10:33,494 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-01-20 22:10:33,494 INFO L409 AbstractCegarLoop]: Interpolant automaton has 2 states [2018-01-20 22:10:33,494 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2018-01-20 22:10:33,495 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-01-20 22:10:33,495 INFO L87 Difference]: Start difference. First operand 91 states. Second operand 2 states. [2018-01-20 22:10:33,505 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:10:33,505 INFO L93 Difference]: Finished difference Result 175 states and 213 transitions. [2018-01-20 22:10:33,505 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2018-01-20 22:10:33,506 INFO L78 Accepts]: Start accepts. Automaton has 2 states. Word has length 9 [2018-01-20 22:10:33,506 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:10:33,507 INFO L225 Difference]: With dead ends: 175 [2018-01-20 22:10:33,507 INFO L226 Difference]: Without dead ends: 86 [2018-01-20 22:10:33,508 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-01-20 22:10:33,509 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 86 states. [2018-01-20 22:10:33,515 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 86 to 86. [2018-01-20 22:10:33,515 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 86 states. [2018-01-20 22:10:33,517 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 86 states to 86 states and 100 transitions. [2018-01-20 22:10:33,517 INFO L78 Accepts]: Start accepts. Automaton has 86 states and 100 transitions. Word has length 9 [2018-01-20 22:10:33,518 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:10:33,518 INFO L432 AbstractCegarLoop]: Abstraction has 86 states and 100 transitions. [2018-01-20 22:10:33,518 INFO L433 AbstractCegarLoop]: Interpolant automaton has 2 states. [2018-01-20 22:10:33,518 INFO L276 IsEmpty]: Start isEmpty. Operand 86 states and 100 transitions. [2018-01-20 22:10:33,519 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2018-01-20 22:10:33,519 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:10:33,519 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 22:10:33,519 INFO L371 AbstractCegarLoop]: === Iteration 2 === [mainErr0EnsuresViolation]=== [2018-01-20 22:10:33,519 INFO L82 PathProgramCache]: Analyzing trace with hash -1430768294, now seen corresponding path program 1 times [2018-01-20 22:10:33,519 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:10:33,520 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:10:33,521 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:10:33,521 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:10:33,521 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:10:33,532 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:10:33,533 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:10:33,568 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 22:10:33,568 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-20 22:10:33,568 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-01-20 22:10:33,569 INFO L409 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-01-20 22:10:33,569 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-01-20 22:10:33,569 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-20 22:10:33,570 INFO L87 Difference]: Start difference. First operand 86 states and 100 transitions. Second operand 3 states. [2018-01-20 22:10:33,612 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:10:33,612 INFO L93 Difference]: Finished difference Result 111 states and 128 transitions. [2018-01-20 22:10:33,613 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-01-20 22:10:33,613 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 12 [2018-01-20 22:10:33,613 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:10:33,616 INFO L225 Difference]: With dead ends: 111 [2018-01-20 22:10:33,617 INFO L226 Difference]: Without dead ends: 109 [2018-01-20 22:10:33,618 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-20 22:10:33,618 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 109 states. [2018-01-20 22:10:33,626 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 109 to 91. [2018-01-20 22:10:33,626 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 91 states. [2018-01-20 22:10:33,628 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 91 states to 91 states and 107 transitions. [2018-01-20 22:10:33,628 INFO L78 Accepts]: Start accepts. Automaton has 91 states and 107 transitions. Word has length 12 [2018-01-20 22:10:33,628 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:10:33,629 INFO L432 AbstractCegarLoop]: Abstraction has 91 states and 107 transitions. [2018-01-20 22:10:33,629 INFO L433 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-01-20 22:10:33,629 INFO L276 IsEmpty]: Start isEmpty. Operand 91 states and 107 transitions. [2018-01-20 22:10:33,630 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2018-01-20 22:10:33,630 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:10:33,630 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] [2018-01-20 22:10:33,630 INFO L371 AbstractCegarLoop]: === Iteration 3 === [mainErr0EnsuresViolation]=== [2018-01-20 22:10:33,630 INFO L82 PathProgramCache]: Analyzing trace with hash 1220894246, now seen corresponding path program 1 times [2018-01-20 22:10:33,631 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:10:33,631 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:10:33,632 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:10:33,632 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:10:33,632 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:10:33,646 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:10:33,647 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:10:33,693 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 22:10:33,693 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-20 22:10:33,693 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-01-20 22:10:33,694 INFO L409 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-01-20 22:10:33,694 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-01-20 22:10:33,694 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-20 22:10:33,694 INFO L87 Difference]: Start difference. First operand 91 states and 107 transitions. Second operand 3 states. [2018-01-20 22:10:33,730 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:10:33,730 INFO L93 Difference]: Finished difference Result 186 states and 219 transitions. [2018-01-20 22:10:33,731 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-01-20 22:10:33,731 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 21 [2018-01-20 22:10:33,731 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:10:33,732 INFO L225 Difference]: With dead ends: 186 [2018-01-20 22:10:33,732 INFO L226 Difference]: Without dead ends: 105 [2018-01-20 22:10:33,732 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-20 22:10:33,733 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 105 states. [2018-01-20 22:10:33,737 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 105 to 103. [2018-01-20 22:10:33,737 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 103 states. [2018-01-20 22:10:33,738 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 103 states to 103 states and 121 transitions. [2018-01-20 22:10:33,738 INFO L78 Accepts]: Start accepts. Automaton has 103 states and 121 transitions. Word has length 21 [2018-01-20 22:10:33,738 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:10:33,738 INFO L432 AbstractCegarLoop]: Abstraction has 103 states and 121 transitions. [2018-01-20 22:10:33,738 INFO L433 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-01-20 22:10:33,738 INFO L276 IsEmpty]: Start isEmpty. Operand 103 states and 121 transitions. [2018-01-20 22:10:33,739 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2018-01-20 22:10:33,739 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:10:33,739 INFO L322 BasicCegarLoop]: trace histogram [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] [2018-01-20 22:10:33,739 INFO L371 AbstractCegarLoop]: === Iteration 4 === [mainErr0EnsuresViolation]=== [2018-01-20 22:10:33,739 INFO L82 PathProgramCache]: Analyzing trace with hash 354796251, now seen corresponding path program 1 times [2018-01-20 22:10:33,739 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:10:33,739 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:10:33,740 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:10:33,741 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:10:33,741 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:10:33,763 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:10:33,764 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:10:33,820 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 22:10:33,821 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-20 22:10:33,821 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-01-20 22:10:33,821 INFO L409 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-01-20 22:10:33,822 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-01-20 22:10:33,822 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-01-20 22:10:33,822 INFO L87 Difference]: Start difference. First operand 103 states and 121 transitions. Second operand 5 states. [2018-01-20 22:10:33,901 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:10:33,901 INFO L93 Difference]: Finished difference Result 265 states and 312 transitions. [2018-01-20 22:10:33,902 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-01-20 22:10:33,902 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 30 [2018-01-20 22:10:33,902 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:10:33,904 INFO L225 Difference]: With dead ends: 265 [2018-01-20 22:10:33,904 INFO L226 Difference]: Without dead ends: 182 [2018-01-20 22:10:33,905 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=14, Invalid=16, Unknown=0, NotChecked=0, Total=30 [2018-01-20 22:10:33,905 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 182 states. [2018-01-20 22:10:33,913 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 182 to 103. [2018-01-20 22:10:33,913 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 103 states. [2018-01-20 22:10:33,914 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 103 states to 103 states and 119 transitions. [2018-01-20 22:10:33,914 INFO L78 Accepts]: Start accepts. Automaton has 103 states and 119 transitions. Word has length 30 [2018-01-20 22:10:33,915 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:10:33,915 INFO L432 AbstractCegarLoop]: Abstraction has 103 states and 119 transitions. [2018-01-20 22:10:33,915 INFO L433 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-01-20 22:10:33,915 INFO L276 IsEmpty]: Start isEmpty. Operand 103 states and 119 transitions. [2018-01-20 22:10:33,916 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2018-01-20 22:10:33,916 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:10:33,916 INFO L322 BasicCegarLoop]: trace histogram [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] [2018-01-20 22:10:33,916 INFO L371 AbstractCegarLoop]: === Iteration 5 === [mainErr0EnsuresViolation]=== [2018-01-20 22:10:33,917 INFO L82 PathProgramCache]: Analyzing trace with hash -626570212, now seen corresponding path program 1 times [2018-01-20 22:10:33,917 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:10:33,917 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:10:33,918 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:10:33,918 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:10:33,918 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:10:33,937 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:10:33,938 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:10:34,004 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 22:10:34,004 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-20 22:10:34,005 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-01-20 22:10:34,005 INFO L409 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-01-20 22:10:34,005 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-01-20 22:10:34,005 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-01-20 22:10:34,006 INFO L87 Difference]: Start difference. First operand 103 states and 119 transitions. Second operand 5 states. [2018-01-20 22:10:34,108 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:10:34,109 INFO L93 Difference]: Finished difference Result 237 states and 273 transitions. [2018-01-20 22:10:34,109 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-01-20 22:10:34,109 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 31 [2018-01-20 22:10:34,109 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:10:34,110 INFO L225 Difference]: With dead ends: 237 [2018-01-20 22:10:34,111 INFO L226 Difference]: Without dead ends: 157 [2018-01-20 22:10:34,111 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 9 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=22, Invalid=34, Unknown=0, NotChecked=0, Total=56 [2018-01-20 22:10:34,112 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 157 states. [2018-01-20 22:10:34,121 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 157 to 103. [2018-01-20 22:10:34,122 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 103 states. [2018-01-20 22:10:34,123 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 103 states to 103 states and 117 transitions. [2018-01-20 22:10:34,123 INFO L78 Accepts]: Start accepts. Automaton has 103 states and 117 transitions. Word has length 31 [2018-01-20 22:10:34,123 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:10:34,123 INFO L432 AbstractCegarLoop]: Abstraction has 103 states and 117 transitions. [2018-01-20 22:10:34,124 INFO L433 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-01-20 22:10:34,124 INFO L276 IsEmpty]: Start isEmpty. Operand 103 states and 117 transitions. [2018-01-20 22:10:34,125 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2018-01-20 22:10:34,125 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:10:34,125 INFO L322 BasicCegarLoop]: trace histogram [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] [2018-01-20 22:10:34,125 INFO L371 AbstractCegarLoop]: === Iteration 6 === [mainErr0EnsuresViolation]=== [2018-01-20 22:10:34,126 INFO L82 PathProgramCache]: Analyzing trace with hash 85377444, now seen corresponding path program 1 times [2018-01-20 22:10:34,126 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:10:34,126 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:10:34,127 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:10:34,127 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:10:34,127 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:10:34,145 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:10:34,146 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:10:34,181 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 22:10:34,182 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-20 22:10:34,182 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-01-20 22:10:34,182 INFO L409 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-01-20 22:10:34,183 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-01-20 22:10:34,183 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-01-20 22:10:34,183 INFO L87 Difference]: Start difference. First operand 103 states and 117 transitions. Second operand 4 states. [2018-01-20 22:10:34,227 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:10:34,227 INFO L93 Difference]: Finished difference Result 262 states and 298 transitions. [2018-01-20 22:10:34,228 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-01-20 22:10:34,228 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 40 [2018-01-20 22:10:34,228 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:10:34,229 INFO L225 Difference]: With dead ends: 262 [2018-01-20 22:10:34,229 INFO L226 Difference]: Without dead ends: 175 [2018-01-20 22:10:34,230 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-01-20 22:10:34,231 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 175 states. [2018-01-20 22:10:34,238 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 175 to 104. [2018-01-20 22:10:34,238 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 104 states. [2018-01-20 22:10:34,239 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 104 states to 104 states and 116 transitions. [2018-01-20 22:10:34,239 INFO L78 Accepts]: Start accepts. Automaton has 104 states and 116 transitions. Word has length 40 [2018-01-20 22:10:34,240 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:10:34,240 INFO L432 AbstractCegarLoop]: Abstraction has 104 states and 116 transitions. [2018-01-20 22:10:34,240 INFO L433 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-01-20 22:10:34,240 INFO L276 IsEmpty]: Start isEmpty. Operand 104 states and 116 transitions. [2018-01-20 22:10:34,241 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2018-01-20 22:10:34,241 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:10:34,242 INFO L322 BasicCegarLoop]: trace histogram [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] [2018-01-20 22:10:34,242 INFO L371 AbstractCegarLoop]: === Iteration 7 === [mainErr0EnsuresViolation]=== [2018-01-20 22:10:34,242 INFO L82 PathProgramCache]: Analyzing trace with hash 1217411263, now seen corresponding path program 1 times [2018-01-20 22:10:34,242 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:10:34,242 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:10:34,243 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:10:34,243 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:10:34,244 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:10:34,271 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:10:34,272 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:10:34,655 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 22:10:34,655 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-20 22:10:34,656 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [10] imperfect sequences [] total 10 [2018-01-20 22:10:34,656 INFO L409 AbstractCegarLoop]: Interpolant automaton has 10 states [2018-01-20 22:10:34,656 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2018-01-20 22:10:34,656 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=25, Invalid=65, Unknown=0, NotChecked=0, Total=90 [2018-01-20 22:10:34,657 INFO L87 Difference]: Start difference. First operand 104 states and 116 transitions. Second operand 10 states. [2018-01-20 22:10:35,097 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:10:35,097 INFO L93 Difference]: Finished difference Result 168 states and 189 transitions. [2018-01-20 22:10:35,097 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-01-20 22:10:35,097 INFO L78 Accepts]: Start accepts. Automaton has 10 states. Word has length 42 [2018-01-20 22:10:35,098 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:10:35,098 INFO L225 Difference]: With dead ends: 168 [2018-01-20 22:10:35,099 INFO L226 Difference]: Without dead ends: 165 [2018-01-20 22:10:35,099 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 23 GetRequests, 5 SyntacticMatches, 1 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 49 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=98, Invalid=244, Unknown=0, NotChecked=0, Total=342 [2018-01-20 22:10:35,099 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 165 states. [2018-01-20 22:10:35,105 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 165 to 119. [2018-01-20 22:10:35,105 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 119 states. [2018-01-20 22:10:35,106 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 119 states to 119 states and 134 transitions. [2018-01-20 22:10:35,106 INFO L78 Accepts]: Start accepts. Automaton has 119 states and 134 transitions. Word has length 42 [2018-01-20 22:10:35,107 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:10:35,107 INFO L432 AbstractCegarLoop]: Abstraction has 119 states and 134 transitions. [2018-01-20 22:10:35,107 INFO L433 AbstractCegarLoop]: Interpolant automaton has 10 states. [2018-01-20 22:10:35,107 INFO L276 IsEmpty]: Start isEmpty. Operand 119 states and 134 transitions. [2018-01-20 22:10:35,109 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2018-01-20 22:10:35,109 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:10:35,109 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] [2018-01-20 22:10:35,109 INFO L371 AbstractCegarLoop]: === Iteration 8 === [mainErr0EnsuresViolation]=== [2018-01-20 22:10:35,109 INFO L82 PathProgramCache]: Analyzing trace with hash -456231378, now seen corresponding path program 1 times [2018-01-20 22:10:35,110 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:10:35,110 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:10:35,111 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:10:35,111 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:10:35,111 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:10:35,137 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:10:35,139 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:10:35,810 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 2 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 22:10:35,810 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-20 22:10:35,810 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 2 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-20 22:10:35,817 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:10:35,859 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:10:35,865 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-20 22:10:35,938 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-20 22:10:35,939 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-20 22:10:35,973 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:10:35,973 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:13, output treesize:12 [2018-01-20 22:10:36,009 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 17 treesize of output 14 [2018-01-20 22:10:36,011 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 13 [2018-01-20 22:10:36,012 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:10:36,014 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:10:36,030 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-20 22:10:36,031 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:29, output treesize:25 [2018-01-20 22:10:36,105 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:10:36,106 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:10:36,110 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 4 [2018-01-20 22:10:36,110 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-20 22:10:36,125 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-1 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-20 22:10:36,125 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 2 variables, input treesize:33, output treesize:27 [2018-01-20 22:10:36,246 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 30 [2018-01-20 22:10:36,250 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 1 [2018-01-20 22:10:36,251 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:10:36,260 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:10:36,271 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-20 22:10:36,271 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:42, output treesize:27 [2018-01-20 22:10:36,333 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 27 treesize of output 28 [2018-01-20 22:10:36,335 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 1 [2018-01-20 22:10:36,336 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:10:36,339 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:10:36,350 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 8 [2018-01-20 22:10:36,352 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-01-20 22:10:36,352 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-20 22:10:36,354 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:10:36,363 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 8 [2018-01-20 22:10:36,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 8 treesize of output 7 [2018-01-20 22:10:36,365 INFO L267 ElimStorePlain]: Start of recursive call 7: End of recursive call: and 1 xjuncts. [2018-01-20 22:10:36,366 INFO L267 ElimStorePlain]: Start of recursive call 6: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:10:36,373 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 3 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-20 22:10:36,373 INFO L202 ElimStorePlain]: Needed 7 recursive calls to eliminate 5 variables, input treesize:56, output treesize:34 [2018-01-20 22:10:36,412 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 33 treesize of output 27 [2018-01-20 22:10:36,429 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 1 new quantified variables, introduced 1 case distinctions, treesize of input 27 treesize of output 26 [2018-01-20 22:10:36,432 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-0 vars, End of recursive call: 1 dim-0 vars, and 2 xjuncts. [2018-01-20 22:10:36,444 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: 1 dim-0 vars, and 2 xjuncts. [2018-01-20 22:10:36,461 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 13 [2018-01-20 22:10:36,467 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 1 case distinctions, treesize of input 13 treesize of output 10 [2018-01-20 22:10:36,468 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 2 xjuncts. [2018-01-20 22:10:36,471 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-20 22:10:36,488 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 2 dim-2 vars, End of recursive call: 6 dim-0 vars, and 4 xjuncts. [2018-01-20 22:10:36,488 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 4 variables, input treesize:52, output treesize:85 [2018-01-20 22:10:36,678 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-20 22:10:36,681 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 7 [2018-01-20 22:10:36,681 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:10:36,683 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:10:36,687 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-20 22:10:36,687 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:22, output treesize:11 [2018-01-20 22:10:36,744 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 2 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 22:10:36,765 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-20 22:10:36,765 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 17] total 29 [2018-01-20 22:10:36,766 INFO L409 AbstractCegarLoop]: Interpolant automaton has 29 states [2018-01-20 22:10:36,766 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2018-01-20 22:10:36,767 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=110, Invalid=702, Unknown=0, NotChecked=0, Total=812 [2018-01-20 22:10:36,767 INFO L87 Difference]: Start difference. First operand 119 states and 134 transitions. Second operand 29 states. [2018-01-20 22:10:38,155 WARN L146 SmtUtils]: Spent 298ms on a formula simplification. DAG size of input: 56 DAG size of output 44 [2018-01-20 22:10:38,722 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:10:38,722 INFO L93 Difference]: Finished difference Result 223 states and 251 transitions. [2018-01-20 22:10:38,723 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2018-01-20 22:10:38,723 INFO L78 Accepts]: Start accepts. Automaton has 29 states. Word has length 50 [2018-01-20 22:10:38,723 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:10:38,724 INFO L225 Difference]: With dead ends: 223 [2018-01-20 22:10:38,724 INFO L226 Difference]: Without dead ends: 209 [2018-01-20 22:10:38,726 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 92 GetRequests, 39 SyntacticMatches, 4 SemanticMatches, 49 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 589 ImplicationChecksByTransitivity, 2.0s TimeCoverageRelationStatistics Valid=421, Invalid=2129, Unknown=0, NotChecked=0, Total=2550 [2018-01-20 22:10:38,726 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 209 states. [2018-01-20 22:10:38,734 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 209 to 124. [2018-01-20 22:10:38,734 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 124 states. [2018-01-20 22:10:38,735 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 124 states to 124 states and 139 transitions. [2018-01-20 22:10:38,736 INFO L78 Accepts]: Start accepts. Automaton has 124 states and 139 transitions. Word has length 50 [2018-01-20 22:10:38,736 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:10:38,736 INFO L432 AbstractCegarLoop]: Abstraction has 124 states and 139 transitions. [2018-01-20 22:10:38,736 INFO L433 AbstractCegarLoop]: Interpolant automaton has 29 states. [2018-01-20 22:10:38,736 INFO L276 IsEmpty]: Start isEmpty. Operand 124 states and 139 transitions. [2018-01-20 22:10:38,737 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 53 [2018-01-20 22:10:38,738 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:10:38,738 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] [2018-01-20 22:10:38,738 INFO L371 AbstractCegarLoop]: === Iteration 9 === [mainErr0EnsuresViolation]=== [2018-01-20 22:10:38,738 INFO L82 PathProgramCache]: Analyzing trace with hash 1428924497, now seen corresponding path program 1 times [2018-01-20 22:10:38,738 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:10:38,738 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:10:38,739 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:10:38,740 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:10:38,740 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:10:38,762 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:10:38,763 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:10:39,328 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 22:10:39,328 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-20 22:10:39,328 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [19] imperfect sequences [] total 19 [2018-01-20 22:10:39,328 INFO L409 AbstractCegarLoop]: Interpolant automaton has 19 states [2018-01-20 22:10:39,329 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2018-01-20 22:10:39,329 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=48, Invalid=294, Unknown=0, NotChecked=0, Total=342 [2018-01-20 22:10:39,329 INFO L87 Difference]: Start difference. First operand 124 states and 139 transitions. Second operand 19 states. [2018-01-20 22:10:40,532 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:10:40,532 INFO L93 Difference]: Finished difference Result 239 states and 266 transitions. [2018-01-20 22:10:40,532 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2018-01-20 22:10:40,532 INFO L78 Accepts]: Start accepts. Automaton has 19 states. Word has length 52 [2018-01-20 22:10:40,533 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:10:40,534 INFO L225 Difference]: With dead ends: 239 [2018-01-20 22:10:40,534 INFO L226 Difference]: Without dead ends: 225 [2018-01-20 22:10:40,535 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 49 GetRequests, 5 SyntacticMatches, 2 SemanticMatches, 42 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 346 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=315, Invalid=1577, Unknown=0, NotChecked=0, Total=1892 [2018-01-20 22:10:40,535 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 225 states. [2018-01-20 22:10:40,540 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 225 to 127. [2018-01-20 22:10:40,540 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 127 states. [2018-01-20 22:10:40,541 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 127 states to 127 states and 142 transitions. [2018-01-20 22:10:40,541 INFO L78 Accepts]: Start accepts. Automaton has 127 states and 142 transitions. Word has length 52 [2018-01-20 22:10:40,541 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:10:40,541 INFO L432 AbstractCegarLoop]: Abstraction has 127 states and 142 transitions. [2018-01-20 22:10:40,541 INFO L433 AbstractCegarLoop]: Interpolant automaton has 19 states. [2018-01-20 22:10:40,542 INFO L276 IsEmpty]: Start isEmpty. Operand 127 states and 142 transitions. [2018-01-20 22:10:40,542 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 54 [2018-01-20 22:10:40,543 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:10:40,543 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] [2018-01-20 22:10:40,543 INFO L371 AbstractCegarLoop]: === Iteration 10 === [mainErr0EnsuresViolation]=== [2018-01-20 22:10:40,543 INFO L82 PathProgramCache]: Analyzing trace with hash 1281273386, now seen corresponding path program 1 times [2018-01-20 22:10:40,543 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:10:40,543 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:10:40,544 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:10:40,544 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:10:40,544 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:10:40,560 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:10:40,561 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:10:41,096 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 22:10:41,096 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-20 22:10:41,097 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-20 22:10:41,104 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:10:41,126 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:10:41,131 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-20 22:10:41,221 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 8 [2018-01-20 22:10:41,223 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-01-20 22:10:41,223 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:10:41,225 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:10:41,230 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:10:41,230 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:34, output treesize:35 [2018-01-20 22:10:41,295 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 48 treesize of output 40 [2018-01-20 22:10:41,298 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:10:41,299 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 1 new quantified variables, introduced 0 case distinctions, treesize of input 36 treesize of output 29 [2018-01-20 22:10:41,300 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-0 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-20 22:10:41,308 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-20 22:10:41,313 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 48 treesize of output 40 [2018-01-20 22:10:41,320 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 1 new quantified variables, introduced 1 case distinctions, treesize of input 36 treesize of output 33 [2018-01-20 22:10:41,322 INFO L267 ElimStorePlain]: Start of recursive call 5: 1 dim-0 vars, End of recursive call: 1 dim-0 vars, and 2 xjuncts. [2018-01-20 22:10:41,335 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: 1 dim-0 vars, and 2 xjuncts. [2018-01-20 22:10:41,358 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: 2 dim-0 vars, and 3 xjuncts. [2018-01-20 22:10:41,358 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 1 variables, input treesize:97, output treesize:88 [2018-01-20 22:10:42,098 WARN L1029 $PredicateComparison]: unable to prove that (exists ((main_~data~5.base Int) (main_~item2~5.base Int)) (let ((.cse1 (store |c_old(#valid)| main_~item2~5.base 1))) (let ((.cse0 (store .cse1 main_~data~5.base 0))) (and (= |c_#valid| (store .cse0 main_~item2~5.base 0)) (not (= main_~data~5.base 0)) (= 0 (select |c_old(#valid)| main_~item2~5.base)) (= 1 (select .cse0 main_~item2~5.base)) (not (= 0 main_~item2~5.base)) (= 0 (select .cse1 main_~data~5.base)))))) is different from true [2018-01-20 22:10:42,110 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 2 not checked. [2018-01-20 22:10:42,141 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-20 22:10:42,141 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 14] total 24 [2018-01-20 22:10:42,141 INFO L409 AbstractCegarLoop]: Interpolant automaton has 25 states [2018-01-20 22:10:42,141 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2018-01-20 22:10:42,141 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=56, Invalid=492, Unknown=8, NotChecked=44, Total=600 [2018-01-20 22:10:42,142 INFO L87 Difference]: Start difference. First operand 127 states and 142 transitions. Second operand 25 states. [2018-01-20 22:10:43,449 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:10:43,449 INFO L93 Difference]: Finished difference Result 158 states and 176 transitions. [2018-01-20 22:10:43,449 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2018-01-20 22:10:43,449 INFO L78 Accepts]: Start accepts. Automaton has 25 states. Word has length 53 [2018-01-20 22:10:43,450 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:10:43,451 INFO L225 Difference]: With dead ends: 158 [2018-01-20 22:10:43,451 INFO L226 Difference]: Without dead ends: 153 [2018-01-20 22:10:43,451 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 83 GetRequests, 36 SyntacticMatches, 10 SemanticMatches, 37 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 261 ImplicationChecksByTransitivity, 1.8s TimeCoverageRelationStatistics Valid=163, Invalid=1234, Unknown=13, NotChecked=72, Total=1482 [2018-01-20 22:10:43,452 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 153 states. [2018-01-20 22:10:43,461 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 153 to 138. [2018-01-20 22:10:43,461 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 138 states. [2018-01-20 22:10:43,462 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 138 states to 138 states and 155 transitions. [2018-01-20 22:10:43,462 INFO L78 Accepts]: Start accepts. Automaton has 138 states and 155 transitions. Word has length 53 [2018-01-20 22:10:43,463 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:10:43,463 INFO L432 AbstractCegarLoop]: Abstraction has 138 states and 155 transitions. [2018-01-20 22:10:43,463 INFO L433 AbstractCegarLoop]: Interpolant automaton has 25 states. [2018-01-20 22:10:43,463 INFO L276 IsEmpty]: Start isEmpty. Operand 138 states and 155 transitions. [2018-01-20 22:10:43,464 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 63 [2018-01-20 22:10:43,464 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:10:43,464 INFO L322 BasicCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 22:10:43,464 INFO L371 AbstractCegarLoop]: === Iteration 11 === [mainErr0EnsuresViolation]=== [2018-01-20 22:10:43,465 INFO L82 PathProgramCache]: Analyzing trace with hash -1066594590, now seen corresponding path program 1 times [2018-01-20 22:10:43,465 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:10:43,465 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:10:43,466 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:10:43,466 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:10:43,466 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:10:43,477 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:10:43,478 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:10:43,498 INFO L134 CoverageAnalysis]: Checked inductivity of 17 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2018-01-20 22:10:43,498 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-20 22:10:43,498 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-01-20 22:10:43,498 INFO L409 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-01-20 22:10:43,499 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-01-20 22:10:43,499 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-20 22:10:43,499 INFO L87 Difference]: Start difference. First operand 138 states and 155 transitions. Second operand 3 states. [2018-01-20 22:10:43,517 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:10:43,517 INFO L93 Difference]: Finished difference Result 154 states and 175 transitions. [2018-01-20 22:10:43,517 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-01-20 22:10:43,517 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 62 [2018-01-20 22:10:43,517 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:10:43,518 INFO L225 Difference]: With dead ends: 154 [2018-01-20 22:10:43,518 INFO L226 Difference]: Without dead ends: 140 [2018-01-20 22:10:43,518 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-20 22:10:43,518 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 140 states. [2018-01-20 22:10:43,525 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 140 to 140. [2018-01-20 22:10:43,525 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 140 states. [2018-01-20 22:10:43,525 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 140 states to 140 states and 157 transitions. [2018-01-20 22:10:43,526 INFO L78 Accepts]: Start accepts. Automaton has 140 states and 157 transitions. Word has length 62 [2018-01-20 22:10:43,526 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:10:43,526 INFO L432 AbstractCegarLoop]: Abstraction has 140 states and 157 transitions. [2018-01-20 22:10:43,526 INFO L433 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-01-20 22:10:43,526 INFO L276 IsEmpty]: Start isEmpty. Operand 140 states and 157 transitions. [2018-01-20 22:10:43,527 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 64 [2018-01-20 22:10:43,527 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:10:43,527 INFO L322 BasicCegarLoop]: trace histogram [3, 3, 3, 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] [2018-01-20 22:10:43,527 INFO L371 AbstractCegarLoop]: === Iteration 12 === [mainErr0EnsuresViolation]=== [2018-01-20 22:10:43,527 INFO L82 PathProgramCache]: Analyzing trace with hash 1987073456, now seen corresponding path program 1 times [2018-01-20 22:10:43,527 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:10:43,527 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:10:43,528 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:10:43,528 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:10:43,528 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:10:43,538 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:10:43,539 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:10:43,577 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 24 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 22:10:43,577 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-20 22:10:43,577 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-20 22:10:43,589 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:10:43,617 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:10:43,620 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-20 22:10:43,661 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 15 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 22:10:43,683 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-20 22:10:43,683 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 5] total 5 [2018-01-20 22:10:43,683 INFO L409 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-01-20 22:10:43,683 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-01-20 22:10:43,684 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2018-01-20 22:10:43,684 INFO L87 Difference]: Start difference. First operand 140 states and 157 transitions. Second operand 5 states. [2018-01-20 22:10:43,717 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:10:43,717 INFO L93 Difference]: Finished difference Result 370 states and 418 transitions. [2018-01-20 22:10:43,717 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-01-20 22:10:43,718 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 63 [2018-01-20 22:10:43,718 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:10:43,719 INFO L225 Difference]: With dead ends: 370 [2018-01-20 22:10:43,719 INFO L226 Difference]: Without dead ends: 290 [2018-01-20 22:10:43,719 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 66 GetRequests, 63 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2018-01-20 22:10:43,720 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 290 states. [2018-01-20 22:10:43,730 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 290 to 162. [2018-01-20 22:10:43,731 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 162 states. [2018-01-20 22:10:43,732 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 162 states to 162 states and 182 transitions. [2018-01-20 22:10:43,732 INFO L78 Accepts]: Start accepts. Automaton has 162 states and 182 transitions. Word has length 63 [2018-01-20 22:10:43,732 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:10:43,732 INFO L432 AbstractCegarLoop]: Abstraction has 162 states and 182 transitions. [2018-01-20 22:10:43,732 INFO L433 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-01-20 22:10:43,733 INFO L276 IsEmpty]: Start isEmpty. Operand 162 states and 182 transitions. [2018-01-20 22:10:43,733 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 65 [2018-01-20 22:10:43,733 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:10:43,734 INFO L322 BasicCegarLoop]: trace histogram [3, 3, 3, 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] [2018-01-20 22:10:43,734 INFO L371 AbstractCegarLoop]: === Iteration 13 === [mainErr0EnsuresViolation]=== [2018-01-20 22:10:43,734 INFO L82 PathProgramCache]: Analyzing trace with hash -525585442, now seen corresponding path program 1 times [2018-01-20 22:10:43,734 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:10:43,734 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:10:43,735 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:10:43,735 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:10:43,735 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:10:43,756 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:10:43,757 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:10:43,885 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 18 proven. 8 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 22:10:43,885 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-20 22:10:43,885 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-20 22:10:43,892 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:10:43,918 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:10:43,922 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-20 22:10:43,926 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-20 22:10:43,926 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-20 22:10:43,928 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:10:43,928 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:6, output treesize:5 [2018-01-20 22:10:43,951 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:10:43,959 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:10:43,960 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-20 22:10:43,960 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-20 22:10:43,992 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:10:43,993 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:17, output treesize:15 [2018-01-20 22:10:44,067 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:10:44,068 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:10:44,069 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:10:44,069 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 16 treesize of output 13 [2018-01-20 22:10:44,070 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-20 22:10:44,074 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:10:44,074 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:20, output treesize:13 [2018-01-20 22:10:44,101 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 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 11 treesize of output 8 [2018-01-20 22:10:44,103 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-20 22:10:44,103 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:10:44,105 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:10:44,109 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:10:44,109 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:24, output treesize:20 [2018-01-20 22:10:44,130 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 38 treesize of output 34 [2018-01-20 22:10:44,132 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 14 treesize of output 13 [2018-01-20 22:10:44,133 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:10:44,137 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:10:44,142 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-20 22:10:44,142 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:42, output treesize:41 [2018-01-20 22:10:44,171 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 48 treesize of output 30 [2018-01-20 22:10:44,173 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 22 treesize of output 13 [2018-01-20 22:10:44,173 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:10:44,182 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 9 [2018-01-20 22:10:44,182 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-20 22:10:44,184 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:10:44,185 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:10:44,185 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 3 variables, input treesize:48, output treesize:4 [2018-01-20 22:10:44,198 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 18 proven. 8 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 22:10:44,229 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-20 22:10:44,229 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 12] total 18 [2018-01-20 22:10:44,229 INFO L409 AbstractCegarLoop]: Interpolant automaton has 18 states [2018-01-20 22:10:44,229 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2018-01-20 22:10:44,230 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=48, Invalid=258, Unknown=0, NotChecked=0, Total=306 [2018-01-20 22:10:44,230 INFO L87 Difference]: Start difference. First operand 162 states and 182 transitions. Second operand 18 states. [2018-01-20 22:11:00,958 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:11:00,959 INFO L93 Difference]: Finished difference Result 256 states and 284 transitions. [2018-01-20 22:11:00,959 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2018-01-20 22:11:00,959 INFO L78 Accepts]: Start accepts. Automaton has 18 states. Word has length 64 [2018-01-20 22:11:00,959 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:11:00,960 INFO L225 Difference]: With dead ends: 256 [2018-01-20 22:11:00,960 INFO L226 Difference]: Without dead ends: 238 [2018-01-20 22:11:00,960 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 97 GetRequests, 63 SyntacticMatches, 2 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 216 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=255, Invalid=867, Unknown=0, NotChecked=0, Total=1122 [2018-01-20 22:11:00,961 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 238 states. [2018-01-20 22:11:00,968 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 238 to 165. [2018-01-20 22:11:00,968 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 165 states. [2018-01-20 22:11:00,969 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 165 states to 165 states and 185 transitions. [2018-01-20 22:11:00,969 INFO L78 Accepts]: Start accepts. Automaton has 165 states and 185 transitions. Word has length 64 [2018-01-20 22:11:00,969 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:11:00,969 INFO L432 AbstractCegarLoop]: Abstraction has 165 states and 185 transitions. [2018-01-20 22:11:00,969 INFO L433 AbstractCegarLoop]: Interpolant automaton has 18 states. [2018-01-20 22:11:00,969 INFO L276 IsEmpty]: Start isEmpty. Operand 165 states and 185 transitions. [2018-01-20 22:11:00,970 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 65 [2018-01-20 22:11:00,970 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:11:00,970 INFO L322 BasicCegarLoop]: trace histogram [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] [2018-01-20 22:11:00,970 INFO L371 AbstractCegarLoop]: === Iteration 14 === [mainErr0EnsuresViolation]=== [2018-01-20 22:11:00,970 INFO L82 PathProgramCache]: Analyzing trace with hash -1325227638, now seen corresponding path program 1 times [2018-01-20 22:11:00,970 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:11:00,970 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:11:00,971 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:11:00,971 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:11:00,971 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:11:00,981 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:11:00,981 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:11:01,145 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 7 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 22:11:01,145 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-20 22:11:01,145 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [11] imperfect sequences [] total 11 [2018-01-20 22:11:01,145 INFO L409 AbstractCegarLoop]: Interpolant automaton has 11 states [2018-01-20 22:11:01,145 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2018-01-20 22:11:01,145 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=87, Unknown=0, NotChecked=0, Total=110 [2018-01-20 22:11:01,146 INFO L87 Difference]: Start difference. First operand 165 states and 185 transitions. Second operand 11 states. [2018-01-20 22:11:01,431 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:11:01,431 INFO L93 Difference]: Finished difference Result 250 states and 279 transitions. [2018-01-20 22:11:01,432 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-01-20 22:11:01,432 INFO L78 Accepts]: Start accepts. Automaton has 11 states. Word has length 64 [2018-01-20 22:11:01,432 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:11:01,433 INFO L225 Difference]: With dead ends: 250 [2018-01-20 22:11:01,433 INFO L226 Difference]: Without dead ends: 184 [2018-01-20 22:11:01,433 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 23 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 48 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=86, Invalid=294, Unknown=0, NotChecked=0, Total=380 [2018-01-20 22:11:01,433 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 184 states. [2018-01-20 22:11:01,441 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 184 to 165. [2018-01-20 22:11:01,441 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 165 states. [2018-01-20 22:11:01,442 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 165 states to 165 states and 184 transitions. [2018-01-20 22:11:01,443 INFO L78 Accepts]: Start accepts. Automaton has 165 states and 184 transitions. Word has length 64 [2018-01-20 22:11:01,443 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:11:01,443 INFO L432 AbstractCegarLoop]: Abstraction has 165 states and 184 transitions. [2018-01-20 22:11:01,443 INFO L433 AbstractCegarLoop]: Interpolant automaton has 11 states. [2018-01-20 22:11:01,443 INFO L276 IsEmpty]: Start isEmpty. Operand 165 states and 184 transitions. [2018-01-20 22:11:01,444 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 65 [2018-01-20 22:11:01,444 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:11:01,444 INFO L322 BasicCegarLoop]: trace histogram [3, 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] [2018-01-20 22:11:01,444 INFO L371 AbstractCegarLoop]: === Iteration 15 === [mainErr0EnsuresViolation]=== [2018-01-20 22:11:01,444 INFO L82 PathProgramCache]: Analyzing trace with hash -475711521, now seen corresponding path program 2 times [2018-01-20 22:11:01,445 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:11:01,445 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:11:01,445 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:11:01,445 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:11:01,445 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:11:01,463 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:11:01,464 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:11:01,949 WARN L146 SmtUtils]: Spent 171ms on a formula simplification. DAG size of input: 29 DAG size of output 22 [2018-01-20 22:11:02,171 WARN L146 SmtUtils]: Spent 170ms on a formula simplification. DAG size of input: 47 DAG size of output 31 [2018-01-20 22:11:02,343 INFO L134 CoverageAnalysis]: Checked inductivity of 19 backedges. 17 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 22:11:02,344 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-20 22:11:02,344 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-20 22:11:02,352 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-01-20 22:11:02,366 INFO L201 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-20 22:11:02,378 INFO L214 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-20 22:11:02,382 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-20 22:11:02,386 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-20 22:11:02,417 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 8 [2018-01-20 22:11:02,419 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-01-20 22:11:02,419 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:02,421 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:02,425 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:02,425 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:15, output treesize:11 [2018-01-20 22:11:02,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 27 treesize of output 22 [2018-01-20 22:11:02,434 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:11:02,435 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 14 [2018-01-20 22:11:02,435 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:02,438 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:02,441 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:02,441 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:30, output treesize:11 [2018-01-20 22:11:02,444 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 27 treesize of output 22 [2018-01-20 22:11:02,447 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:11:02,449 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 14 [2018-01-20 22:11:02,449 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:02,453 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:02,456 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:02,456 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:30, output treesize:11 [2018-01-20 22:11:02,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 23 treesize of output 18 [2018-01-20 22:11:02,461 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 18 treesize of output 7 [2018-01-20 22:11:02,462 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:02,463 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:02,464 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:02,464 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:23, output treesize:7 [2018-01-20 22:11:02,515 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 3 case distinctions, treesize of input 19 treesize of output 31 [2018-01-20 22:11:02,517 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 20 treesize of output 19 [2018-01-20 22:11:02,518 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:02,533 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 17 treesize of output 14 [2018-01-20 22:11:02,533 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:02,541 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-20 22:11:02,551 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 2 xjuncts. [2018-01-20 22:11:02,551 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 1 variables, input treesize:22, output treesize:33 [2018-01-20 22:11:02,601 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 19 treesize of output 14 [2018-01-20 22:11:02,603 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 14 treesize of output 15 [2018-01-20 22:11:02,603 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:02,605 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:02,625 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 3 case distinctions, treesize of input 26 treesize of output 36 [2018-01-20 22:11:02,628 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 25 treesize of output 26 [2018-01-20 22:11:02,629 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:02,641 INFO L267 ElimStorePlain]: Start of recursive call 4: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:02,649 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 2 dim-2 vars, End of recursive call: and 2 xjuncts. [2018-01-20 22:11:02,649 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 3 variables, input treesize:46, output treesize:35 [2018-01-20 22:11:02,699 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 37 treesize of output 35 [2018-01-20 22:11:02,701 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 1 [2018-01-20 22:11:02,701 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:02,707 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:02,709 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 41 treesize of output 39 [2018-01-20 22:11:02,711 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 1 [2018-01-20 22:11:02,711 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:02,717 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:02,720 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 41 treesize of output 39 [2018-01-20 22:11:02,726 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 1 [2018-01-20 22:11:02,727 INFO L267 ElimStorePlain]: Start of recursive call 7: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:02,738 INFO L267 ElimStorePlain]: Start of recursive call 6: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:02,740 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 37 treesize of output 35 [2018-01-20 22:11:02,742 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 1 [2018-01-20 22:11:02,743 INFO L267 ElimStorePlain]: Start of recursive call 9: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:02,748 INFO L267 ElimStorePlain]: Start of recursive call 8: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:02,769 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 3 xjuncts. [2018-01-20 22:11:02,769 INFO L202 ElimStorePlain]: Needed 9 recursive calls to eliminate 1 variables, input treesize:157, output treesize:93 [2018-01-20 22:11:02,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, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 36 treesize of output 35 [2018-01-20 22:11:02,854 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:02,869 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 32 treesize of output 31 [2018-01-20 22:11:02,870 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:02,883 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 2 dim-1 vars, End of recursive call: 2 dim-0 vars, and 2 xjuncts. [2018-01-20 22:11:02,883 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:69, output treesize:67 [2018-01-20 22:11:03,008 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:11:03,009 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:11:03,010 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 3 disjoint index pairs (out of 3 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 46 treesize of output 42 [2018-01-20 22:11:03,022 INFO L477 Elim1Store]: Elim1 applied some preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 2 disjoint index pairs (out of 3 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 15 treesize of output 27 [2018-01-20 22:11:03,025 INFO L267 ElimStorePlain]: Start of recursive call 3: 3 dim-0 vars, End of recursive call: 3 dim-0 vars, and 4 xjuncts. [2018-01-20 22:11:03,044 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:11:03,045 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 4 [2018-01-20 22:11:03,045 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:03,052 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:03,083 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:11:03,083 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:11:03,084 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 2 new quantified variables, introduced 0 case distinctions, treesize of input 46 treesize of output 42 [2018-01-20 22:11:03,090 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:11:03,098 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 2 new quantified variables, introduced 2 case distinctions, treesize of input 15 treesize of output 27 [2018-01-20 22:11:03,100 INFO L267 ElimStorePlain]: Start of recursive call 6: 2 dim-0 vars, End of recursive call: 2 dim-0 vars, and 3 xjuncts. [2018-01-20 22:11:03,118 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-20 22:11:03,118 INFO L267 ElimStorePlain]: Start of recursive call 7: End of recursive call: and 2 xjuncts. [2018-01-20 22:11:03,125 INFO L267 ElimStorePlain]: Start of recursive call 5: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-20 22:11:03,153 INFO L682 Elim1Store]: detected equality via solver [2018-01-20 22:11:03,154 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 1 new quantified variables, introduced 0 case distinctions, treesize of input 38 treesize of output 33 [2018-01-20 22:11:03,167 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 0 new quantified variables, introduced 2 case distinctions, treesize of input 21 treesize of output 20 [2018-01-20 22:11:03,167 INFO L267 ElimStorePlain]: Start of recursive call 9: End of recursive call: and 2 xjuncts. [2018-01-20 22:11:03,206 INFO L267 ElimStorePlain]: Start of recursive call 8: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-20 22:11:03,262 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 3 dim-2 vars, End of recursive call: 3 dim-0 vars, and 5 xjuncts. [2018-01-20 22:11:03,262 INFO L202 ElimStorePlain]: Needed 9 recursive calls to eliminate 6 variables, input treesize:131, output treesize:93 [2018-01-20 22:11:03,483 WARN L307 Elim1Store]: Array PQE input equivalent to false [2018-01-20 22:11:03,483 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:03,484 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:03,485 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:19, output treesize:3 [2018-01-20 22:11:03,507 INFO L134 CoverageAnalysis]: Checked inductivity of 19 backedges. 8 proven. 11 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 22:11:03,539 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-20 22:11:03,540 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 20] total 30 [2018-01-20 22:11:03,540 INFO L409 AbstractCegarLoop]: Interpolant automaton has 30 states [2018-01-20 22:11:03,540 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2018-01-20 22:11:03,540 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=98, Invalid=772, Unknown=0, NotChecked=0, Total=870 [2018-01-20 22:11:03,541 INFO L87 Difference]: Start difference. First operand 165 states and 184 transitions. Second operand 30 states. [2018-01-20 22:11:04,504 WARN L146 SmtUtils]: Spent 112ms on a formula simplification. DAG size of input: 76 DAG size of output 67 [2018-01-20 22:11:04,710 WARN L146 SmtUtils]: Spent 171ms on a formula simplification. DAG size of input: 110 DAG size of output 96 [2018-01-20 22:11:05,414 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:11:05,414 INFO L93 Difference]: Finished difference Result 213 states and 238 transitions. [2018-01-20 22:11:05,415 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2018-01-20 22:11:05,415 INFO L78 Accepts]: Start accepts. Automaton has 30 states. Word has length 64 [2018-01-20 22:11:05,415 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:11:05,416 INFO L225 Difference]: With dead ends: 213 [2018-01-20 22:11:05,416 INFO L226 Difference]: Without dead ends: 197 [2018-01-20 22:11:05,417 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 109 GetRequests, 53 SyntacticMatches, 6 SemanticMatches, 50 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 744 ImplicationChecksByTransitivity, 2.5s TimeCoverageRelationStatistics Valid=347, Invalid=2305, Unknown=0, NotChecked=0, Total=2652 [2018-01-20 22:11:05,417 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 197 states. [2018-01-20 22:11:05,431 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 197 to 174. [2018-01-20 22:11:05,431 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 174 states. [2018-01-20 22:11:05,432 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 174 states to 174 states and 194 transitions. [2018-01-20 22:11:05,432 INFO L78 Accepts]: Start accepts. Automaton has 174 states and 194 transitions. Word has length 64 [2018-01-20 22:11:05,432 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:11:05,433 INFO L432 AbstractCegarLoop]: Abstraction has 174 states and 194 transitions. [2018-01-20 22:11:05,433 INFO L433 AbstractCegarLoop]: Interpolant automaton has 30 states. [2018-01-20 22:11:05,433 INFO L276 IsEmpty]: Start isEmpty. Operand 174 states and 194 transitions. [2018-01-20 22:11:05,434 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 73 [2018-01-20 22:11:05,434 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:11:05,434 INFO L322 BasicCegarLoop]: trace histogram [4, 3, 3, 3, 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] [2018-01-20 22:11:05,434 INFO L371 AbstractCegarLoop]: === Iteration 16 === [mainErr0EnsuresViolation]=== [2018-01-20 22:11:05,434 INFO L82 PathProgramCache]: Analyzing trace with hash 1289685520, now seen corresponding path program 1 times [2018-01-20 22:11:05,435 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:11:05,435 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:11:05,435 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:11:05,436 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-01-20 22:11:05,436 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:11:05,455 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:11:05,456 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:11:06,050 INFO L134 CoverageAnalysis]: Checked inductivity of 37 backedges. 27 proven. 2 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2018-01-20 22:11:06,051 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-20 22:11:06,051 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-20 22:11:06,055 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:11:06,079 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:11:06,083 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-20 22:11:06,109 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 8 [2018-01-20 22:11:06,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, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-01-20 22:11:06,111 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:06,117 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:06,124 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 8 [2018-01-20 22:11:06,131 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-01-20 22:11:06,131 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:06,132 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:06,136 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:06,136 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 2 variables, input treesize:26, output treesize:18 [2018-01-20 22:11:06,142 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 27 treesize of output 22 [2018-01-20 22:11:06,145 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:11:06,146 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 14 [2018-01-20 22:11:06,147 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:06,150 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:06,158 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 27 treesize of output 22 [2018-01-20 22:11:06,160 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:11:06,162 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 14 [2018-01-20 22:11:06,162 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:06,164 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:06,168 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:06,168 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 2 variables, input treesize:56, output treesize:18 [2018-01-20 22:11:06,175 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 27 treesize of output 22 [2018-01-20 22:11:06,177 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:11:06,178 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 14 [2018-01-20 22:11:06,178 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:06,181 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:06,189 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 27 treesize of output 22 [2018-01-20 22:11:06,191 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:11:06,192 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 14 [2018-01-20 22:11:06,192 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:06,195 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:06,199 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:06,199 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 2 variables, input treesize:56, output treesize:18 [2018-01-20 22:11:06,207 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 27 treesize of output 22 [2018-01-20 22:11:06,210 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:11:06,211 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 14 [2018-01-20 22:11:06,211 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:06,215 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:06,223 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 27 treesize of output 22 [2018-01-20 22:11:06,225 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:11:06,226 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 14 [2018-01-20 22:11:06,226 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:06,245 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:06,254 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:06,255 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 2 variables, input treesize:56, output treesize:18 [2018-01-20 22:11:06,332 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 3 case distinctions, treesize of input 19 treesize of output 31 [2018-01-20 22:11:06,335 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 20 treesize of output 19 [2018-01-20 22:11:06,335 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:06,354 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 17 treesize of output 17 [2018-01-20 22:11:06,354 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:06,366 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-20 22:11:06,393 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 3 case distinctions, treesize of input 19 treesize of output 31 [2018-01-20 22:11:06,396 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 20 treesize of output 19 [2018-01-20 22:11:06,396 INFO L267 ElimStorePlain]: Start of recursive call 6: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:06,426 INFO L267 ElimStorePlain]: Start of recursive call 5: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:06,439 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-2 vars, End of recursive call: and 2 xjuncts. [2018-01-20 22:11:06,439 INFO L202 ElimStorePlain]: Needed 6 recursive calls to eliminate 2 variables, input treesize:43, output treesize:67 [2018-01-20 22:11:06,550 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 3 case distinctions, treesize of input 51 treesize of output 61 [2018-01-20 22:11:06,561 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 50 treesize of output 51 [2018-01-20 22:11:06,562 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:06,618 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:06,759 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 3 case distinctions, treesize of input 47 treesize of output 69 [2018-01-20 22:11:06,763 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 54 treesize of output 55 [2018-01-20 22:11:06,763 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:06,868 INFO L267 ElimStorePlain]: Start of recursive call 4: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:06,891 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 37 treesize of output 32 [2018-01-20 22:11:06,893 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 14 treesize of output 15 [2018-01-20 22:11:06,893 INFO L267 ElimStorePlain]: Start of recursive call 7: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:06,899 INFO L267 ElimStorePlain]: Start of recursive call 6: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:06,920 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 33 treesize of output 28 [2018-01-20 22:11:06,922 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 15 [2018-01-20 22:11:06,922 INFO L267 ElimStorePlain]: Start of recursive call 9: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:06,928 INFO L267 ElimStorePlain]: Start of recursive call 8: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:06,945 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 4 dim-2 vars, End of recursive call: and 2 xjuncts. [2018-01-20 22:11:06,945 INFO L202 ElimStorePlain]: Needed 9 recursive calls to eliminate 5 variables, input treesize:89, output treesize:74 [2018-01-20 22:11:07,148 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 46 treesize of output 45 [2018-01-20 22:11:07,148 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:07,174 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 61 treesize of output 60 [2018-01-20 22:11:07,175 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:07,204 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 2 dim-1 vars, End of recursive call: 2 dim-0 vars, and 2 xjuncts. [2018-01-20 22:11:07,204 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:108, output treesize:106 [2018-01-20 22:11:07,379 INFO L682 Elim1Store]: detected equality via solver [2018-01-20 22:11:07,380 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 59 treesize of output 54 [2018-01-20 22:11:07,390 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 0 new quantified variables, introduced 2 case distinctions, treesize of input 21 treesize of output 20 [2018-01-20 22:11:07,390 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-20 22:11:07,404 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-20 22:11:07,461 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:11:07,463 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 2 disjoint index pairs (out of 3 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 78 treesize of output 70 [2018-01-20 22:11:07,467 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 11 treesize of output 4 [2018-01-20 22:11:07,467 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:07,476 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:07,527 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:11:07,528 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:11:07,529 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 3 disjoint index pairs (out of 3 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 46 treesize of output 42 [2018-01-20 22:11:07,539 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:11:07,546 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 2 new quantified variables, introduced 2 case distinctions, treesize of input 15 treesize of output 27 [2018-01-20 22:11:07,547 INFO L267 ElimStorePlain]: Start of recursive call 7: 2 dim-0 vars, End of recursive call: 2 dim-0 vars, and 3 xjuncts. [2018-01-20 22:11:07,561 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 11 treesize of output 4 [2018-01-20 22:11:07,561 INFO L267 ElimStorePlain]: Start of recursive call 8: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:07,565 INFO L267 ElimStorePlain]: Start of recursive call 6: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:07,609 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 1 new quantified variables, introduced 0 case distinctions, treesize of input 42 treesize of output 36 [2018-01-20 22:11:07,612 INFO L477 Elim1Store]: Elim1 did not use 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 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 9 [2018-01-20 22:11:07,613 INFO L267 ElimStorePlain]: Start of recursive call 10: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:07,618 INFO L267 ElimStorePlain]: Start of recursive call 9: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:07,619 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 1 new quantified variables, introduced 0 case distinctions, treesize of input 37 treesize of output 31 [2018-01-20 22:11:07,629 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 0 new quantified variables, introduced 2 case distinctions, treesize of input 16 treesize of output 17 [2018-01-20 22:11:07,629 INFO L267 ElimStorePlain]: Start of recursive call 12: End of recursive call: and 2 xjuncts. [2018-01-20 22:11:07,637 INFO L267 ElimStorePlain]: Start of recursive call 11: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-20 22:11:07,686 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:11:07,688 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 3 disjoint index pairs (out of 3 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 78 treesize of output 70 [2018-01-20 22:11:07,695 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-20 22:11:07,695 INFO L267 ElimStorePlain]: Start of recursive call 14: End of recursive call: and 2 xjuncts. [2018-01-20 22:11:07,711 INFO L267 ElimStorePlain]: Start of recursive call 13: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-20 22:11:07,770 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:11:07,772 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:11:07,772 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 2 new quantified variables, introduced 0 case distinctions, treesize of input 49 treesize of output 45 [2018-01-20 22:11:07,790 INFO L477 Elim1Store]: Elim1 applied some preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 2 new quantified variables, introduced 3 case distinctions, treesize of input 15 treesize of output 31 [2018-01-20 22:11:07,793 INFO L267 ElimStorePlain]: Start of recursive call 16: 6 dim-0 vars, End of recursive call: 6 dim-0 vars, and 8 xjuncts. [2018-01-20 22:11:07,815 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:11:07,816 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 4 [2018-01-20 22:11:07,816 INFO L267 ElimStorePlain]: Start of recursive call 17: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:07,825 INFO L267 ElimStorePlain]: Start of recursive call 15: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-20 22:11:07,827 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:11:07,828 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:11:07,829 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 2 new quantified variables, introduced 0 case distinctions, treesize of input 50 treesize of output 46 [2018-01-20 22:11:07,841 INFO L477 Elim1Store]: Elim1 applied some preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 2 disjoint index pairs (out of 3 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 15 treesize of output 27 [2018-01-20 22:11:07,843 INFO L267 ElimStorePlain]: Start of recursive call 19: 3 dim-0 vars, End of recursive call: 3 dim-0 vars, and 4 xjuncts. [2018-01-20 22:11:07,861 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:11:07,861 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 4 [2018-01-20 22:11:07,862 INFO L267 ElimStorePlain]: Start of recursive call 20: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:07,868 INFO L267 ElimStorePlain]: Start of recursive call 18: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:07,906 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 6 dim-2 vars, End of recursive call: 3 dim-0 vars, and 5 xjuncts. [2018-01-20 22:11:07,906 INFO L202 ElimStorePlain]: Needed 20 recursive calls to eliminate 9 variables, input treesize:216, output treesize:99 [2018-01-20 22:11:08,090 WARN L307 Elim1Store]: Array PQE input equivalent to false [2018-01-20 22:11:08,091 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:08,095 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:08,095 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:26, output treesize:7 [2018-01-20 22:11:08,144 INFO L134 CoverageAnalysis]: Checked inductivity of 37 backedges. 27 proven. 2 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2018-01-20 22:11:08,170 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-20 22:11:08,170 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 18] total 28 [2018-01-20 22:11:08,170 INFO L409 AbstractCegarLoop]: Interpolant automaton has 28 states [2018-01-20 22:11:08,170 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2018-01-20 22:11:08,171 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=94, Invalid=658, Unknown=4, NotChecked=0, Total=756 [2018-01-20 22:11:08,171 INFO L87 Difference]: Start difference. First operand 174 states and 194 transitions. Second operand 28 states. [2018-01-20 22:11:09,302 WARN L146 SmtUtils]: Spent 101ms on a formula simplification. DAG size of input: 92 DAG size of output 72 [2018-01-20 22:11:09,526 WARN L146 SmtUtils]: Spent 160ms on a formula simplification. DAG size of input: 101 DAG size of output 84 [2018-01-20 22:11:09,805 WARN L146 SmtUtils]: Spent 252ms on a formula simplification. DAG size of input: 132 DAG size of output 113 [2018-01-20 22:11:09,954 WARN L146 SmtUtils]: Spent 128ms on a formula simplification. DAG size of input: 86 DAG size of output 83 [2018-01-20 22:11:10,432 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:11:10,432 INFO L93 Difference]: Finished difference Result 193 states and 215 transitions. [2018-01-20 22:11:10,433 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2018-01-20 22:11:10,433 INFO L78 Accepts]: Start accepts. Automaton has 28 states. Word has length 72 [2018-01-20 22:11:10,433 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:11:10,433 INFO L225 Difference]: With dead ends: 193 [2018-01-20 22:11:10,433 INFO L226 Difference]: Without dead ends: 140 [2018-01-20 22:11:10,434 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 113 GetRequests, 57 SyntacticMatches, 11 SemanticMatches, 45 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 581 ImplicationChecksByTransitivity, 2.7s TimeCoverageRelationStatistics Valid=305, Invalid=1851, Unknown=6, NotChecked=0, Total=2162 [2018-01-20 22:11:10,434 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 140 states. [2018-01-20 22:11:10,441 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 140 to 136. [2018-01-20 22:11:10,441 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 136 states. [2018-01-20 22:11:10,443 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 136 states to 136 states and 152 transitions. [2018-01-20 22:11:10,443 INFO L78 Accepts]: Start accepts. Automaton has 136 states and 152 transitions. Word has length 72 [2018-01-20 22:11:10,443 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:11:10,443 INFO L432 AbstractCegarLoop]: Abstraction has 136 states and 152 transitions. [2018-01-20 22:11:10,443 INFO L433 AbstractCegarLoop]: Interpolant automaton has 28 states. [2018-01-20 22:11:10,443 INFO L276 IsEmpty]: Start isEmpty. Operand 136 states and 152 transitions. [2018-01-20 22:11:10,444 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 87 [2018-01-20 22:11:10,444 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:11:10,445 INFO L322 BasicCegarLoop]: trace histogram [3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 22:11:10,445 INFO L371 AbstractCegarLoop]: === Iteration 17 === [mainErr0EnsuresViolation]=== [2018-01-20 22:11:10,445 INFO L82 PathProgramCache]: Analyzing trace with hash 270658409, now seen corresponding path program 1 times [2018-01-20 22:11:10,445 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:11:10,445 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:11:10,446 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:11:10,446 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:11:10,446 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:11:10,473 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:11:10,474 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:11:11,245 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 12 proven. 17 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 22:11:11,246 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-20 22:11:11,246 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-20 22:11:11,251 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:11:11,294 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:11:11,299 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-20 22:11:11,323 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-20 22:11:11,323 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:11,326 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:11,327 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:14, output treesize:13 [2018-01-20 22:11:11,387 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 10 [2018-01-20 22:11:11,388 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 10 treesize of output 9 [2018-01-20 22:11:11,388 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:11,390 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:11,394 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:11,395 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:26, output treesize:19 [2018-01-20 22:11:11,418 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:11:11,419 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:11:11,420 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-20 22:11:11,420 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:11,427 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:11,427 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:30, output treesize:28 [2018-01-20 22:11:11,485 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 22 treesize of output 23 [2018-01-20 22:11:11,489 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-01-20 22:11:11,490 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:11,494 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:11,505 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:11,506 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:39, output treesize:35 [2018-01-20 22:11:11,542 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 37 treesize of output 36 [2018-01-20 22:11:11,544 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:11:11,545 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 14 [2018-01-20 22:11:11,546 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:11,551 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:11,560 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:11,560 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:54, output treesize:35 [2018-01-20 22:11:11,567 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 37 treesize of output 36 [2018-01-20 22:11:11,569 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:11:11,571 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 14 [2018-01-20 22:11:11,571 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:11,576 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:11,584 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-20 22:11:11,584 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:54, output treesize:35 [2018-01-20 22:11:11,622 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:11:11,623 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:11:11,626 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:11:11,627 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 16 treesize of output 13 [2018-01-20 22:11:11,628 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:11,657 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-1 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-20 22:11:11,657 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 2 variables, input treesize:40, output treesize:33 [2018-01-20 22:11:11,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, 3 disjoint index pairs (out of 3 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 38 [2018-01-20 22:11:11,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, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-01-20 22:11:11,736 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:11,742 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:11,750 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-20 22:11:11,751 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:44, output treesize:33 [2018-01-20 22:11:11,757 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 29 treesize of output 28 [2018-01-20 22:11:11,759 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:11:11,760 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 4 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 24 [2018-01-20 22:11:11,760 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:11,766 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:11,774 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-20 22:11:11,774 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:44, output treesize:40 [2018-01-20 22:11:11,816 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 2 new quantified variables, introduced 0 case distinctions, treesize of input 55 treesize of output 55 [2018-01-20 22:11:11,818 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 14 treesize of output 13 [2018-01-20 22:11:11,818 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:11,825 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:11,834 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-2 vars, End of recursive call: 2 dim-0 vars, and 1 xjuncts. [2018-01-20 22:11:11,834 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:62, output treesize:71 [2018-01-20 22:11:11,885 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 3 disjoint index pairs (out of 3 index pairs), introduced 5 new quantified variables, introduced 0 case distinctions, treesize of input 73 treesize of output 53 [2018-01-20 22:11:11,888 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 4 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 28 treesize of output 17 [2018-01-20 22:11:11,888 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:11,892 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 8 treesize of output 4 [2018-01-20 22:11:11,893 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:11,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 5 treesize of output 1 [2018-01-20 22:11:11,896 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:11,897 INFO L267 ElimStorePlain]: Start of recursive call 2: 3 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:11,898 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-20 22:11:11,898 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 4 variables, input treesize:73, output treesize:4 [2018-01-20 22:11:11,932 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 12 proven. 17 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 22:11:11,959 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-20 22:11:11,959 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 18] total 36 [2018-01-20 22:11:11,959 INFO L409 AbstractCegarLoop]: Interpolant automaton has 36 states [2018-01-20 22:11:11,959 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 36 interpolants. [2018-01-20 22:11:11,960 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=108, Invalid=1152, Unknown=0, NotChecked=0, Total=1260 [2018-01-20 22:11:11,960 INFO L87 Difference]: Start difference. First operand 136 states and 152 transitions. Second operand 36 states. [2018-01-20 22:11:12,979 WARN L146 SmtUtils]: Spent 103ms on a formula simplification. DAG size of input: 110 DAG size of output 78 [2018-01-20 22:11:14,508 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-20 22:11:14,508 INFO L93 Difference]: Finished difference Result 310 states and 349 transitions. [2018-01-20 22:11:14,509 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 44 states. [2018-01-20 22:11:14,509 INFO L78 Accepts]: Start accepts. Automaton has 36 states. Word has length 86 [2018-01-20 22:11:14,509 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-20 22:11:14,510 INFO L225 Difference]: With dead ends: 310 [2018-01-20 22:11:14,510 INFO L226 Difference]: Without dead ends: 255 [2018-01-20 22:11:14,511 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 154 GetRequests, 74 SyntacticMatches, 6 SemanticMatches, 74 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1492 ImplicationChecksByTransitivity, 2.6s TimeCoverageRelationStatistics Valid=917, Invalid=4783, Unknown=0, NotChecked=0, Total=5700 [2018-01-20 22:11:14,511 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 255 states. [2018-01-20 22:11:14,518 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 255 to 176. [2018-01-20 22:11:14,518 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 176 states. [2018-01-20 22:11:14,518 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 176 states to 176 states and 198 transitions. [2018-01-20 22:11:14,519 INFO L78 Accepts]: Start accepts. Automaton has 176 states and 198 transitions. Word has length 86 [2018-01-20 22:11:14,519 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-20 22:11:14,519 INFO L432 AbstractCegarLoop]: Abstraction has 176 states and 198 transitions. [2018-01-20 22:11:14,519 INFO L433 AbstractCegarLoop]: Interpolant automaton has 36 states. [2018-01-20 22:11:14,519 INFO L276 IsEmpty]: Start isEmpty. Operand 176 states and 198 transitions. [2018-01-20 22:11:14,520 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 98 [2018-01-20 22:11:14,520 INFO L314 BasicCegarLoop]: Found error trace [2018-01-20 22:11:14,520 INFO L322 BasicCegarLoop]: trace histogram [3, 3, 3, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-20 22:11:14,520 INFO L371 AbstractCegarLoop]: === Iteration 18 === [mainErr0EnsuresViolation]=== [2018-01-20 22:11:14,520 INFO L82 PathProgramCache]: Analyzing trace with hash -1459535802, now seen corresponding path program 1 times [2018-01-20 22:11:14,520 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-20 22:11:14,521 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-20 22:11:14,521 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:11:14,521 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:11:14,521 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-20 22:11:14,572 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:11:14,585 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-20 22:11:16,740 WARN L146 SmtUtils]: Spent 123ms on a formula simplification. DAG size of input: 84 DAG size of output 59 [2018-01-20 22:11:17,013 WARN L146 SmtUtils]: Spent 103ms on a formula simplification. DAG size of input: 71 DAG size of output 48 [2018-01-20 22:11:17,656 INFO L134 CoverageAnalysis]: Checked inductivity of 31 backedges. 9 proven. 22 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-20 22:11:17,656 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-20 22:11:17,656 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-20 22:11:17,662 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-20 22:11:17,702 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-20 22:11:17,707 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-20 22:11:17,711 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-20 22:11:17,711 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:17,715 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:17,715 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:14, output treesize:13 [2018-01-20 22:11:17,770 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 8 [2018-01-20 22:11:17,772 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-01-20 22:11:17,772 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:17,774 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:17,780 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:17,780 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:24, output treesize:20 [2018-01-20 22:11:17,857 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 21 treesize of output 16 [2018-01-20 22:11:17,858 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:11:17,860 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 23 [2018-01-20 22:11:17,860 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:17,863 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:17,869 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:17,870 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:33, output treesize:20 [2018-01-20 22:11:17,877 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:11:17,878 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:11:17,878 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 21 [2018-01-20 22:11:17,879 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:17,886 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:17,886 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:31, output treesize:29 [2018-01-20 22:11:17,984 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 20 [2018-01-20 22:11:17,987 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-01-20 22:11:17,987 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:17,991 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:17,999 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:17,999 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:40, output treesize:36 [2018-01-20 22:11:18,049 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 34 treesize of output 33 [2018-01-20 22:11:18,052 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:11:18,054 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 14 [2018-01-20 22:11:18,054 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:18,059 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:18,068 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:18,068 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:55, output treesize:36 [2018-01-20 22:11:18,074 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 34 treesize of output 33 [2018-01-20 22:11:18,076 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:11:18,078 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 14 [2018-01-20 22:11:18,078 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:18,083 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:18,091 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-20 22:11:18,091 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:55, output treesize:36 [2018-01-20 22:11:18,158 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:11:18,160 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:11:18,168 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:11:18,169 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 5 disjoint index pairs (out of 3 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 13 [2018-01-20 22:11:18,169 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:18,217 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-1 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-20 22:11:18,218 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 2 variables, input treesize:44, output treesize:37 [2018-01-20 22:11:18,384 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 1 new quantified variables, introduced 0 case distinctions, treesize of input 30 treesize of output 39 [2018-01-20 22:11:18,386 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 11 [2018-01-20 22:11:18,386 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:18,392 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:18,402 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-20 22:11:18,402 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:52, output treesize:48 [2018-01-20 22:11:18,453 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:11:18,454 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:11:18,455 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 6 disjoint index pairs (out of 3 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 37 treesize of output 57 [2018-01-20 22:11:18,457 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 38 treesize of output 31 [2018-01-20 22:11:18,457 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:18,465 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:18,475 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-20 22:11:18,475 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:59, output treesize:44 [2018-01-20 22:11:18,526 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:11:18,528 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:11:18,531 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 6 disjoint index pairs (out of 3 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 54 treesize of output 63 [2018-01-20 22:11:18,545 INFO L477 Elim1Store]: Elim1 applied some preprocessing eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 4 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 3 case distinctions, treesize of input 33 treesize of output 58 [2018-01-20 22:11:18,546 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-0 vars, End of recursive call: 1 dim-0 vars, and 2 xjuncts. [2018-01-20 22:11:18,561 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:18,570 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-20 22:11:18,571 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:65, output treesize:70 [2018-01-20 22:11:18,681 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 5 [2018-01-20 22:11:18,682 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 1 [2018-01-20 22:11:18,682 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:18,683 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:18,692 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-20 22:11:18,693 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:84, output treesize:77 [2018-01-20 22:11:18,863 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:11:18,866 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 82 treesize of output 69 [2018-01-20 22:11:18,886 INFO L477 Elim1Store]: Elim1 applied some 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 3 new quantified variables, introduced 3 case distinctions, treesize of input 73 treesize of output 77 [2018-01-20 22:11:18,889 INFO L267 ElimStorePlain]: Start of recursive call 3: 4 dim-0 vars, End of recursive call: 4 dim-0 vars, and 3 xjuncts. [2018-01-20 22:11:18,928 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: 4 dim-0 vars, and 3 xjuncts. [2018-01-20 22:11:18,963 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 7 dim-0 vars, and 3 xjuncts. [2018-01-20 22:11:18,964 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:89, output treesize:224 [2018-01-20 22:11:19,692 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:11:19,708 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 99 treesize of output 101 [2018-01-20 22:11:19,712 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:11:19,714 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 18 treesize of output 25 [2018-01-20 22:11:19,715 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:19,741 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:19,978 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:11:19,990 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 99 treesize of output 101 [2018-01-20 22:11:19,994 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:11:19,996 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 18 treesize of output 25 [2018-01-20 22:11:19,996 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:20,020 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:20,156 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 99 treesize of output 96 [2018-01-20 22:11:20,158 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 9 [2018-01-20 22:11:20,159 INFO L267 ElimStorePlain]: Start of recursive call 7: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:20,179 INFO L267 ElimStorePlain]: Start of recursive call 6: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:20,182 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 99 treesize of output 96 [2018-01-20 22:11:20,184 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 9 [2018-01-20 22:11:20,185 INFO L267 ElimStorePlain]: Start of recursive call 9: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:20,205 INFO L267 ElimStorePlain]: Start of recursive call 8: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:20,208 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 93 treesize of output 90 [2018-01-20 22:11:20,210 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 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 9 [2018-01-20 22:11:20,210 INFO L267 ElimStorePlain]: Start of recursive call 11: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:20,228 INFO L267 ElimStorePlain]: Start of recursive call 10: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:20,231 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 93 treesize of output 90 [2018-01-20 22:11:20,233 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 9 [2018-01-20 22:11:20,233 INFO L267 ElimStorePlain]: Start of recursive call 13: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:20,250 INFO L267 ElimStorePlain]: Start of recursive call 12: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:20,370 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:11:20,377 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 97 treesize of output 99 [2018-01-20 22:11:20,380 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:11:20,381 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 18 treesize of output 25 [2018-01-20 22:11:20,381 INFO L267 ElimStorePlain]: Start of recursive call 15: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:20,403 INFO L267 ElimStorePlain]: Start of recursive call 14: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:20,507 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:11:20,515 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 97 treesize of output 99 [2018-01-20 22:11:20,518 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:11:20,519 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 18 treesize of output 25 [2018-01-20 22:11:20,519 INFO L267 ElimStorePlain]: Start of recursive call 17: End of recursive call: and 1 xjuncts. [2018-01-20 22:11:20,544 INFO L267 ElimStorePlain]: Start of recursive call 16: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-20 22:11:20,634 INFO L267 ElimStorePlain]: Start of recursive call 1: 8 dim-0 vars, 5 dim-2 vars, End of recursive call: 8 dim-0 vars, and 4 xjuncts. [2018-01-20 22:11:20,634 INFO L202 ElimStorePlain]: Needed 17 recursive calls to eliminate 13 variables, input treesize:397, output treesize:373 [2018-01-20 22:11:21,746 INFO L700 Elim1Store]: detected not equals via solver [2018-01-20 22:11:21,785 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 6 new quantified variables, introduced 9 case distinctions, treesize of input 171 treesize of output 189 [2018-01-20 22:11:21,785 WARN L130 XnfTransformerHelper]: expecting exponential blowup for input size 6 [2018-01-20 22:11:21,806 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 192 treesize of output 180 [2018-01-20 22:11:21,806 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. Received shutdown request... [2018-01-20 22:11:24,626 INFO L175 TraceCheckSpWp]: Timeout while computing interpolants [2018-01-20 22:11:24,644 WARN L491 AbstractCegarLoop]: Verification canceled [2018-01-20 22:11:24,646 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 20.01 10:11:24 BoogieIcfgContainer [2018-01-20 22:11:24,646 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-01-20 22:11:24,647 INFO L168 Benchmark]: Toolchain (without parser) took 52463.79 ms. Allocated memory was 298.3 MB in the beginning and 700.4 MB in the end (delta: 402.1 MB). Free memory was 256.3 MB in the beginning and 354.2 MB in the end (delta: -98.0 MB). Peak memory consumption was 304.2 MB. Max. memory is 5.3 GB. [2018-01-20 22:11:24,648 INFO L168 Benchmark]: CDTParser took 0.21 ms. Allocated memory is still 298.3 MB. Free memory is still 262.2 MB. There was no memory consumed. Max. memory is 5.3 GB. [2018-01-20 22:11:24,648 INFO L168 Benchmark]: CACSL2BoogieTranslator took 217.70 ms. Allocated memory is still 298.3 MB. Free memory was 255.3 MB in the beginning and 244.2 MB in the end (delta: 11.0 MB). Peak memory consumption was 11.0 MB. Max. memory is 5.3 GB. [2018-01-20 22:11:24,648 INFO L168 Benchmark]: Boogie Preprocessor took 45.29 ms. Allocated memory is still 298.3 MB. Free memory was 244.2 MB in the beginning and 242.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 5.3 GB. [2018-01-20 22:11:24,649 INFO L168 Benchmark]: RCFGBuilder took 447.56 ms. Allocated memory is still 298.3 MB. Free memory was 242.2 MB in the beginning and 213.1 MB in the end (delta: 29.1 MB). Peak memory consumption was 29.1 MB. Max. memory is 5.3 GB. [2018-01-20 22:11:24,649 INFO L168 Benchmark]: TraceAbstraction took 51746.03 ms. Allocated memory was 298.3 MB in the beginning and 700.4 MB in the end (delta: 402.1 MB). Free memory was 213.1 MB in the beginning and 354.2 MB in the end (delta: -141.1 MB). Peak memory consumption was 261.0 MB. Max. memory is 5.3 GB. [2018-01-20 22:11:24,650 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.21 ms. Allocated memory is still 298.3 MB. Free memory is still 262.2 MB. There was no memory consumed. Max. memory is 5.3 GB. * CACSL2BoogieTranslator took 217.70 ms. Allocated memory is still 298.3 MB. Free memory was 255.3 MB in the beginning and 244.2 MB in the end (delta: 11.0 MB). Peak memory consumption was 11.0 MB. Max. memory is 5.3 GB. * Boogie Preprocessor took 45.29 ms. Allocated memory is still 298.3 MB. Free memory was 244.2 MB in the beginning and 242.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 5.3 GB. * RCFGBuilder took 447.56 ms. Allocated memory is still 298.3 MB. Free memory was 242.2 MB in the beginning and 213.1 MB in the end (delta: 29.1 MB). Peak memory consumption was 29.1 MB. Max. memory is 5.3 GB. * TraceAbstraction took 51746.03 ms. Allocated memory was 298.3 MB in the beginning and 700.4 MB in the end (delta: 402.1 MB). Free memory was 213.1 MB in the beginning and 354.2 MB in the end (delta: -141.1 MB). Peak memory consumption was 261.0 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, 91 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=91occurred 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: [L629] struct TLItem* data = ((void *)0); [L630] struct DItem* item, * item2; [L631] struct TLItem *lItem; [L632] int c1 = 0; VAL [c1=0, data={0:0}] [L633] c1 < 5 && __VERIFIER_nondet_int() [L633] c1 < 5 && __VERIFIER_nondet_int() VAL [__VERIFIER_nondet_int()=0, c1=0, c1 < 5 && __VERIFIER_nondet_int()=0, data={0:0}] [L633] COND FALSE !(c1 < 5 && __VERIFIER_nondet_int()) [L657] COND TRUE !data [L658] return 0; - StatisticsResult: Ultimate Automizer benchmark data for error location: ULTIMATE.startErr0EnsuresViolation CFG has 3 procedures, 91 locations, 3 error locations. UNSAFE Result, 0.2s OverallTime, 2 OverallIterations, 1 TraceHistogramMax, 0.1s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 105 SDtfs, 0 SDslu, 0 SDs, 0 SdLazy, 0 SolverSat, 0 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.0s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=91occurred 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: 0.0s AutomataMinimizationTime, 1 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.0s SatisfiabilityAnalysisTime, 0.0s InterpolantComputationTime, 25 NumberOfCodeBlocks, 25 NumberOfCodeBlocksAsserted, 2 NumberOfCheckSat, 10 ConstructedInterpolants, 0 QuantifiedInterpolants, 100 SizeOfPredicates, 0 NumberOfNonLiveVariables, 0 ConjunctsInSsa, 0 ConjunctsInUnsatCore, 1 InterpolantComputations, 1 PerfectInterpolantSequences, 0/0 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, REUSE_STATISTICS: No data available - TimeoutResultAtElement [Line: 628]: Timeout (TraceAbstraction) Unable to prove that all allocated memory was freed (line 628). Cancelled while BasicCegarLoop was analyzing trace of length 98 with TraceHistMax 3, while TraceCheckSpWp was constructing forward predicates, while PartialQuantifierElimination was eliminating quantifiers from formula with 0 quantifier alternations, while SimplifyDDAWithTimeout was simplifying term of DAG size 410. - StatisticsResult: Ultimate Automizer benchmark data for error location: mainErr0EnsuresViolation CFG has 3 procedures, 91 locations, 3 error locations. TIMEOUT Result, 51.1s OverallTime, 18 OverallIterations, 4 TraceHistogramMax, 29.0s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 1540 SDtfs, 4211 SDslu, 7785 SDs, 0 SdLazy, 7056 SolverSat, 632 SolverUnsat, 37 SolverUnknown, 0 SolverNotchecked, 20.4s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 838 GetRequests, 414 SyntacticMatches, 42 SemanticMatches, 382 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 4331 ImplicationChecksByTransitivity, 14.1s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=176occurred in iteration=17, 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, 17 MinimizatonAttempts, 794 StatesRemovedByMinimization, 15 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.4s SatisfiabilityAnalysisTime, 10.9s InterpolantComputationTime, 1267 NumberOfCodeBlocks, 1267 NumberOfCodeBlocksAsserted, 25 NumberOfCheckSat, 1243 ConstructedInterpolants, 89 QuantifiedInterpolants, 950642 SizeOfPredicates, 93 NumberOfNonLiveVariables, 1452 ConjunctsInSsa, 234 ConjunctsInUnsatCore, 24 InterpolantComputations, 10 PerfectInterpolantSequences, 244/342 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/test-0513_1_true-valid-memsafety.i_mempurity-32bit-Automizer_Camel+AI_EQ.epf_AutomizerC.xml/Csv-Benchmark-0-2018-01-20_22-11-24-659.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/test-0513_1_true-valid-memsafety.i_mempurity-32bit-Automizer_Camel+AI_EQ.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-0-2018-01-20_22-11-24-659.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/test-0513_1_true-valid-memsafety.i_mempurity-32bit-Automizer_Camel+AI_EQ.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-1-2018-01-20_22-11-24-659.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/test-0513_1_true-valid-memsafety.i_mempurity-32bit-Automizer_Camel+AI_EQ.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-2-2018-01-20_22-11-24-659.csv Completed graceful shutdown