java -Xmx6000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data ./data --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -tc ../../../trunk/examples/toolchains/AutomizerC.xml -s ../../../trunk/examples/settings/ai/eq-bench/mempurity-32bit-Automizer_Camel+AI_EQ.epf -i ../../../trunk/examples/svcomp/forester-heap/sll-sorted_true-unreach-call_true-valid-memsafety.i -------------------------------------------------------------------------------- This is Ultimate 0.1.23-47db877 [2018-01-23 14:57:55,442 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-01-23 14:57:55,444 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-01-23 14:57:55,459 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-01-23 14:57:55,459 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-01-23 14:57:55,460 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-01-23 14:57:55,461 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-01-23 14:57:55,463 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-01-23 14:57:55,465 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-01-23 14:57:55,465 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-01-23 14:57:55,466 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-01-23 14:57:55,467 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-01-23 14:57:55,467 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-01-23 14:57:55,469 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-01-23 14:57:55,470 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-01-23 14:57:55,472 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-01-23 14:57:55,474 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-01-23 14:57:55,476 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-01-23 14:57:55,478 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-01-23 14:57:55,479 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-01-23 14:57:55,481 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-01-23 14:57:55,481 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-01-23 14:57:55,482 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-01-23 14:57:55,483 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-01-23 14:57:55,484 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-01-23 14:57:55,485 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-01-23 14:57:55,485 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-01-23 14:57:55,486 INFO L177 SettingsManager]: PEA to Boogie provides no preferences, ignoring... [2018-01-23 14:57:55,486 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-01-23 14:57:55,486 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-01-23 14:57:55,487 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-01-23 14:57:55,487 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/ai/eq-bench/mempurity-32bit-Automizer_Camel+AI_EQ.epf [2018-01-23 14:57:55,496 INFO L110 SettingsManager]: Loading preferences was successful [2018-01-23 14:57:55,496 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-01-23 14:57:55,497 INFO L131 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2018-01-23 14:57:55,497 INFO L133 SettingsManager]: * to procedures, called more than once=true [2018-01-23 14:57:55,497 INFO L131 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2018-01-23 14:57:55,498 INFO L133 SettingsManager]: * Abstract domain for RCFG-of-the-future=VPDomain [2018-01-23 14:57:55,498 INFO L133 SettingsManager]: * Use the RCFG-of-the-future interface=true [2018-01-23 14:57:55,498 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-01-23 14:57:55,498 INFO L133 SettingsManager]: * sizeof long=4 [2018-01-23 14:57:55,498 INFO L133 SettingsManager]: * Check unreachability of error function in SV-COMP mode=false [2018-01-23 14:57:55,498 INFO L133 SettingsManager]: * Check allocation purity=true [2018-01-23 14:57:55,499 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-01-23 14:57:55,499 INFO L133 SettingsManager]: * sizeof POINTER=4 [2018-01-23 14:57:55,499 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-01-23 14:57:55,499 INFO L133 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2018-01-23 14:57:55,499 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-01-23 14:57:55,499 INFO L133 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2018-01-23 14:57:55,499 INFO L133 SettingsManager]: * sizeof long double=12 [2018-01-23 14:57:55,500 INFO L133 SettingsManager]: * Check if freed pointer was valid=false [2018-01-23 14:57:55,500 INFO L133 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2018-01-23 14:57:55,500 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-01-23 14:57:55,500 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-01-23 14:57:55,500 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-01-23 14:57:55,500 INFO L133 SettingsManager]: * Add additional assume for each assert=false [2018-01-23 14:57:55,501 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-01-23 14:57:55,501 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-01-23 14:57:55,501 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-01-23 14:57:55,501 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-01-23 14:57:55,501 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-01-23 14:57:55,501 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-01-23 14:57:55,502 INFO L133 SettingsManager]: * Stop after first violation was found=false [2018-01-23 14:57:55,502 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-01-23 14:57:55,502 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-01-23 14:57:55,502 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-01-23 14:57:55,502 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-01-23 14:57:55,503 INFO L131 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2018-01-23 14:57:55,503 INFO L133 SettingsManager]: * TransformationType=HEAP_SEPARATOR [2018-01-23 14:57:55,535 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-01-23 14:57:55,546 INFO L266 ainManager$Toolchain]: [Toolchain 1]: Parser(s) successfully initialized [2018-01-23 14:57:55,549 INFO L222 ainManager$Toolchain]: [Toolchain 1]: Toolchain data selected. [2018-01-23 14:57:55,550 INFO L271 PluginConnector]: Initializing CDTParser... [2018-01-23 14:57:55,550 INFO L276 PluginConnector]: CDTParser initialized [2018-01-23 14:57:55,551 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/forester-heap/sll-sorted_true-unreach-call_true-valid-memsafety.i [2018-01-23 14:57:55,711 INFO L304 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-01-23 14:57:55,716 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2018-01-23 14:57:55,716 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2018-01-23 14:57:55,717 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2018-01-23 14:57:55,722 INFO L276 PluginConnector]: CACSL2BoogieTranslator initialized [2018-01-23 14:57:55,723 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 23.01 02:57:55" (1/1) ... [2018-01-23 14:57:55,725 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@7c517b10 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.01 02:57:55, skipping insertion in model container [2018-01-23 14:57:55,726 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 23.01 02:57:55" (1/1) ... [2018-01-23 14:57:55,739 INFO L153 Dispatcher]: Using SV-COMP mode [2018-01-23 14:57:55,779 INFO L153 Dispatcher]: Using SV-COMP mode [2018-01-23 14:57:55,911 INFO L450 PostProcessor]: Settings: Checked method=main [2018-01-23 14:57:55,936 INFO L450 PostProcessor]: Settings: Checked method=main [2018-01-23 14:57:55,946 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.01 02:57:55 WrapperNode [2018-01-23 14:57:55,947 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2018-01-23 14:57:55,947 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-01-23 14:57:55,947 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-01-23 14:57:55,948 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-01-23 14:57:55,959 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.01 02:57:55" (1/1) ... [2018-01-23 14:57:55,959 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.01 02:57:55" (1/1) ... [2018-01-23 14:57:55,970 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.01 02:57:55" (1/1) ... [2018-01-23 14:57:55,970 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.01 02:57:55" (1/1) ... [2018-01-23 14:57:55,979 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.01 02:57:55" (1/1) ... [2018-01-23 14:57:55,985 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.01 02:57:55" (1/1) ... [2018-01-23 14:57:55,987 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.01 02:57:55" (1/1) ... [2018-01-23 14:57:55,990 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-01-23 14:57:55,991 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-01-23 14:57:55,991 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-01-23 14:57:55,991 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-01-23 14:57:55,992 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.01 02:57:55" (1/1) ... No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-01-23 14:57:56,043 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2018-01-23 14:57:56,043 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-01-23 14:57:56,043 INFO L136 BoogieDeclarations]: Found implementation of procedure main [2018-01-23 14:57:56,043 INFO L128 BoogieDeclarations]: Found specification of procedure write~int [2018-01-23 14:57:56,044 INFO L128 BoogieDeclarations]: Found specification of procedure read~int [2018-01-23 14:57:56,044 INFO L128 BoogieDeclarations]: Found specification of procedure write~$Pointer$ [2018-01-23 14:57:56,044 INFO L128 BoogieDeclarations]: Found specification of procedure read~$Pointer$ [2018-01-23 14:57:56,044 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.free [2018-01-23 14:57:56,044 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2018-01-23 14:57:56,044 INFO L128 BoogieDeclarations]: Found specification of procedure #Ultimate.alloc [2018-01-23 14:57:56,044 INFO L128 BoogieDeclarations]: Found specification of procedure malloc [2018-01-23 14:57:56,044 INFO L128 BoogieDeclarations]: Found specification of procedure free [2018-01-23 14:57:56,044 INFO L128 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2018-01-23 14:57:56,045 INFO L128 BoogieDeclarations]: Found specification of procedure __VERIFIER_error [2018-01-23 14:57:56,045 INFO L128 BoogieDeclarations]: Found specification of procedure main [2018-01-23 14:57:56,045 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2018-01-23 14:57:56,045 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-01-23 14:57:56,457 INFO L257 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-01-23 14:57:56,458 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 23.01 02:57:56 BoogieIcfgContainer [2018-01-23 14:57:56,458 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-01-23 14:57:56,459 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-01-23 14:57:56,459 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-01-23 14:57:56,461 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-01-23 14:57:56,461 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 23.01 02:57:55" (1/3) ... [2018-01-23 14:57:56,463 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3eb94120 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 23.01 02:57:56, skipping insertion in model container [2018-01-23 14:57:56,463 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.01 02:57:55" (2/3) ... [2018-01-23 14:57:56,463 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3eb94120 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 23.01 02:57:56, skipping insertion in model container [2018-01-23 14:57:56,463 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 23.01 02:57:56" (3/3) ... [2018-01-23 14:57:56,465 INFO L105 eAbstractionObserver]: Analyzing ICFG sll-sorted_true-unreach-call_true-valid-memsafety.i [2018-01-23 14:57:56,471 INFO L130 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-01-23 14:57:56,478 INFO L142 ceAbstractionStarter]: Appying trace abstraction to program that has 3 error locations. [2018-01-23 14:57:56,518 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-23 14:57:56,519 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-23 14:57:56,519 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-23 14:57:56,519 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-23 14:57:56,519 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-23 14:57:56,519 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-23 14:57:56,519 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-23 14:57:56,519 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == ULTIMATE.initErr0EnsuresViolation======== [2018-01-23 14:57:56,520 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-23 14:57:56,538 INFO L276 IsEmpty]: Start isEmpty. Operand 109 states. [2018-01-23 14:57:56,544 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 4 [2018-01-23 14:57:56,544 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:57:56,545 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1] [2018-01-23 14:57:56,545 INFO L371 AbstractCegarLoop]: === Iteration 1 === [ULTIMATE.initErr0EnsuresViolation]=== [2018-01-23 14:57:56,549 INFO L82 PathProgramCache]: Analyzing trace with hash 330448, now seen corresponding path program 1 times [2018-01-23 14:57:56,550 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:57:56,551 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:57:56,592 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:57:56,592 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:57:56,592 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:57:56,619 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2018-01-23 14:57:56,625 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2018-01-23 14:57:56,642 INFO L381 BasicCegarLoop]: Counterexample might be feasible [2018-01-23 14:57:56,649 WARN L343 cessorBacktranslator]: Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) [2018-01-23 14:57:56,657 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-23 14:57:56,657 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-23 14:57:56,657 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-23 14:57:56,658 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-23 14:57:56,658 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-23 14:57:56,658 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-23 14:57:56,658 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-23 14:57:56,658 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == ULTIMATE.startErr0EnsuresViolation======== [2018-01-23 14:57:56,658 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-23 14:57:56,662 INFO L276 IsEmpty]: Start isEmpty. Operand 109 states. [2018-01-23 14:57:56,666 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2018-01-23 14:57:56,666 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:57:56,666 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-23 14:57:56,667 INFO L371 AbstractCegarLoop]: === Iteration 1 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-23 14:57:56,667 INFO L82 PathProgramCache]: Analyzing trace with hash 439581356, now seen corresponding path program 1 times [2018-01-23 14:57:56,667 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:57:56,667 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:57:56,668 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:57:56,668 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:57:56,668 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:57:56,695 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:57:56,705 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:57:56,841 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-23 14:57:56,844 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-23 14:57:56,844 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-01-23 14:57:56,846 INFO L409 AbstractCegarLoop]: Interpolant automaton has 2 states [2018-01-23 14:57:56,860 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2018-01-23 14:57:56,861 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-01-23 14:57:56,863 INFO L87 Difference]: Start difference. First operand 109 states. Second operand 2 states. [2018-01-23 14:57:56,897 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:57:56,897 INFO L93 Difference]: Finished difference Result 194 states and 266 transitions. [2018-01-23 14:57:56,897 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2018-01-23 14:57:56,899 INFO L78 Accepts]: Start accepts. Automaton has 2 states. Word has length 32 [2018-01-23 14:57:56,899 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:57:56,911 INFO L225 Difference]: With dead ends: 194 [2018-01-23 14:57:56,911 INFO L226 Difference]: Without dead ends: 106 [2018-01-23 14:57:56,915 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-01-23 14:57:56,932 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 106 states. [2018-01-23 14:57:56,950 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 106 to 106. [2018-01-23 14:57:56,951 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 106 states. [2018-01-23 14:57:56,954 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 106 states to 106 states and 117 transitions. [2018-01-23 14:57:56,955 INFO L78 Accepts]: Start accepts. Automaton has 106 states and 117 transitions. Word has length 32 [2018-01-23 14:57:56,956 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:57:56,956 INFO L432 AbstractCegarLoop]: Abstraction has 106 states and 117 transitions. [2018-01-23 14:57:56,956 INFO L433 AbstractCegarLoop]: Interpolant automaton has 2 states. [2018-01-23 14:57:56,956 INFO L276 IsEmpty]: Start isEmpty. Operand 106 states and 117 transitions. [2018-01-23 14:57:56,958 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 50 [2018-01-23 14:57:56,958 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:57:56,958 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-23 14:57:56,958 INFO L371 AbstractCegarLoop]: === Iteration 2 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-23 14:57:56,958 INFO L82 PathProgramCache]: Analyzing trace with hash 1763191735, now seen corresponding path program 1 times [2018-01-23 14:57:56,958 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:57:56,958 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:57:56,959 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:57:56,959 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:57:56,959 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:57:56,980 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:57:56,981 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:57:57,038 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-23 14:57:57,038 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-23 14:57:57,038 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-01-23 14:57:57,040 INFO L409 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-01-23 14:57:57,040 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-01-23 14:57:57,040 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-23 14:57:57,041 INFO L87 Difference]: Start difference. First operand 106 states and 117 transitions. Second operand 3 states. [2018-01-23 14:57:57,089 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:57:57,089 INFO L93 Difference]: Finished difference Result 226 states and 253 transitions. [2018-01-23 14:57:57,089 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-01-23 14:57:57,089 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 49 [2018-01-23 14:57:57,090 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:57:57,093 INFO L225 Difference]: With dead ends: 226 [2018-01-23 14:57:57,093 INFO L226 Difference]: Without dead ends: 130 [2018-01-23 14:57:57,094 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-23 14:57:57,094 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 130 states. [2018-01-23 14:57:57,103 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 130 to 117. [2018-01-23 14:57:57,103 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 117 states. [2018-01-23 14:57:57,105 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 117 states to 117 states and 129 transitions. [2018-01-23 14:57:57,105 INFO L78 Accepts]: Start accepts. Automaton has 117 states and 129 transitions. Word has length 49 [2018-01-23 14:57:57,106 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:57:57,106 INFO L432 AbstractCegarLoop]: Abstraction has 117 states and 129 transitions. [2018-01-23 14:57:57,106 INFO L433 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-01-23 14:57:57,106 INFO L276 IsEmpty]: Start isEmpty. Operand 117 states and 129 transitions. [2018-01-23 14:57:57,108 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 62 [2018-01-23 14:57:57,108 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:57:57,108 INFO L322 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-23 14:57:57,108 INFO L371 AbstractCegarLoop]: === Iteration 3 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-23 14:57:57,109 INFO L82 PathProgramCache]: Analyzing trace with hash 651675214, now seen corresponding path program 1 times [2018-01-23 14:57:57,109 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:57:57,109 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:57:57,110 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:57:57,110 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:57:57,110 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:57:57,149 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:57:57,150 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:57:57,246 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-01-23 14:57:57,246 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-23 14:57:57,246 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-01-23 14:57:57,247 INFO L409 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-01-23 14:57:57,247 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-01-23 14:57:57,247 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-01-23 14:57:57,248 INFO L87 Difference]: Start difference. First operand 117 states and 129 transitions. Second operand 5 states. [2018-01-23 14:57:57,428 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:57:57,429 INFO L93 Difference]: Finished difference Result 208 states and 230 transitions. [2018-01-23 14:57:57,535 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-01-23 14:57:57,536 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 61 [2018-01-23 14:57:57,536 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:57:57,539 INFO L225 Difference]: With dead ends: 208 [2018-01-23 14:57:57,539 INFO L226 Difference]: Without dead ends: 197 [2018-01-23 14:57:57,539 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=25, Unknown=0, NotChecked=0, Total=42 [2018-01-23 14:57:57,540 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 197 states. [2018-01-23 14:57:57,551 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 197 to 127. [2018-01-23 14:57:57,552 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 127 states. [2018-01-23 14:57:57,554 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 127 states to 127 states and 141 transitions. [2018-01-23 14:57:57,554 INFO L78 Accepts]: Start accepts. Automaton has 127 states and 141 transitions. Word has length 61 [2018-01-23 14:57:57,554 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:57:57,554 INFO L432 AbstractCegarLoop]: Abstraction has 127 states and 141 transitions. [2018-01-23 14:57:57,554 INFO L433 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-01-23 14:57:57,555 INFO L276 IsEmpty]: Start isEmpty. Operand 127 states and 141 transitions. [2018-01-23 14:57:57,557 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 80 [2018-01-23 14:57:57,557 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:57:57,557 INFO L322 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-23 14:57:57,557 INFO L371 AbstractCegarLoop]: === Iteration 4 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-23 14:57:57,558 INFO L82 PathProgramCache]: Analyzing trace with hash -1008289951, now seen corresponding path program 1 times [2018-01-23 14:57:57,558 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:57:57,558 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:57:57,559 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:57:57,559 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:57:57,559 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:57:57,585 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:57:57,586 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:57:57,693 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2018-01-23 14:57:57,694 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-23 14:57:57,694 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2018-01-23 14:57:57,694 INFO L409 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-01-23 14:57:57,695 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-01-23 14:57:57,695 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2018-01-23 14:57:57,695 INFO L87 Difference]: Start difference. First operand 127 states and 141 transitions. Second operand 6 states. [2018-01-23 14:57:57,961 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:57:57,961 INFO L93 Difference]: Finished difference Result 243 states and 267 transitions. [2018-01-23 14:57:57,962 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-01-23 14:57:57,963 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 79 [2018-01-23 14:57:57,963 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:57:57,965 INFO L225 Difference]: With dead ends: 243 [2018-01-23 14:57:57,965 INFO L226 Difference]: Without dead ends: 197 [2018-01-23 14:57:57,967 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=34, Invalid=56, Unknown=0, NotChecked=0, Total=90 [2018-01-23 14:57:57,967 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 197 states. [2018-01-23 14:57:57,977 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 197 to 127. [2018-01-23 14:57:57,978 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 127 states. [2018-01-23 14:57:57,979 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 127 states to 127 states and 140 transitions. [2018-01-23 14:57:57,979 INFO L78 Accepts]: Start accepts. Automaton has 127 states and 140 transitions. Word has length 79 [2018-01-23 14:57:57,980 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:57:57,980 INFO L432 AbstractCegarLoop]: Abstraction has 127 states and 140 transitions. [2018-01-23 14:57:57,980 INFO L433 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-01-23 14:57:57,980 INFO L276 IsEmpty]: Start isEmpty. Operand 127 states and 140 transitions. [2018-01-23 14:57:57,982 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 82 [2018-01-23 14:57:57,982 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:57:57,982 INFO L322 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-23 14:57:57,983 INFO L371 AbstractCegarLoop]: === Iteration 5 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-23 14:57:57,983 INFO L82 PathProgramCache]: Analyzing trace with hash -159123330, now seen corresponding path program 1 times [2018-01-23 14:57:57,983 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:57:57,983 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:57:57,984 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:57:57,984 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:57:57,984 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:57:58,007 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:57:58,008 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:57:58,155 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2018-01-23 14:57:58,156 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-23 14:57:58,156 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2018-01-23 14:57:58,156 INFO L409 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-01-23 14:57:58,157 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-01-23 14:57:58,157 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2018-01-23 14:57:58,157 INFO L87 Difference]: Start difference. First operand 127 states and 140 transitions. Second operand 7 states. [2018-01-23 14:57:58,388 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:57:58,388 INFO L93 Difference]: Finished difference Result 222 states and 246 transitions. [2018-01-23 14:57:58,388 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-01-23 14:57:58,389 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 81 [2018-01-23 14:57:58,389 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:57:58,390 INFO L225 Difference]: With dead ends: 222 [2018-01-23 14:57:58,390 INFO L226 Difference]: Without dead ends: 148 [2018-01-23 14:57:58,391 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=34, Invalid=76, Unknown=0, NotChecked=0, Total=110 [2018-01-23 14:57:58,391 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 148 states. [2018-01-23 14:57:58,401 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 148 to 133. [2018-01-23 14:57:58,401 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 133 states. [2018-01-23 14:57:58,402 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 133 states to 133 states and 147 transitions. [2018-01-23 14:57:58,403 INFO L78 Accepts]: Start accepts. Automaton has 133 states and 147 transitions. Word has length 81 [2018-01-23 14:57:58,403 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:57:58,403 INFO L432 AbstractCegarLoop]: Abstraction has 133 states and 147 transitions. [2018-01-23 14:57:58,403 INFO L433 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-01-23 14:57:58,404 INFO L276 IsEmpty]: Start isEmpty. Operand 133 states and 147 transitions. [2018-01-23 14:57:58,405 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 82 [2018-01-23 14:57:58,405 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:57:58,405 INFO L322 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-23 14:57:58,406 INFO L371 AbstractCegarLoop]: === Iteration 6 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-23 14:57:58,406 INFO L82 PathProgramCache]: Analyzing trace with hash -1056516608, now seen corresponding path program 1 times [2018-01-23 14:57:58,406 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:57:58,406 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:57:58,407 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:57:58,407 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:57:58,407 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:57:58,430 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:57:58,431 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:57:58,659 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2018-01-23 14:57:58,659 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-23 14:57:58,659 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 2 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-23 14:57:58,667 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:57:58,713 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:57:58,721 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-23 14:57:58,785 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 8 [2018-01-23 14:57:58,790 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-01-23 14:57:58,790 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:57:58,792 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:57:58,798 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:57:58,798 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:16, output treesize:8 [2018-01-23 14:57:58,811 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 16 treesize of output 12 [2018-01-23 14:57:58,813 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 4 [2018-01-23 14:57:58,814 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:57:58,815 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:57:58,816 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:57:58,817 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:16, output treesize:4 [2018-01-23 14:57:58,860 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2018-01-23 14:57:58,890 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-23 14:57:58,891 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 9 [2018-01-23 14:57:58,891 INFO L409 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-01-23 14:57:58,891 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-01-23 14:57:58,892 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2018-01-23 14:57:58,892 INFO L87 Difference]: Start difference. First operand 133 states and 147 transitions. Second operand 9 states. [2018-01-23 14:57:59,209 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:57:59,210 INFO L93 Difference]: Finished difference Result 298 states and 324 transitions. [2018-01-23 14:57:59,210 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-01-23 14:57:59,210 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 81 [2018-01-23 14:57:59,210 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:57:59,212 INFO L225 Difference]: With dead ends: 298 [2018-01-23 14:57:59,212 INFO L226 Difference]: Without dead ends: 285 [2018-01-23 14:57:59,213 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 94 GetRequests, 76 SyntacticMatches, 6 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 26 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=51, Invalid=131, Unknown=0, NotChecked=0, Total=182 [2018-01-23 14:57:59,213 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 285 states. [2018-01-23 14:57:59,226 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 285 to 183. [2018-01-23 14:57:59,227 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 183 states. [2018-01-23 14:57:59,228 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 183 states to 183 states and 204 transitions. [2018-01-23 14:57:59,228 INFO L78 Accepts]: Start accepts. Automaton has 183 states and 204 transitions. Word has length 81 [2018-01-23 14:57:59,229 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:57:59,229 INFO L432 AbstractCegarLoop]: Abstraction has 183 states and 204 transitions. [2018-01-23 14:57:59,229 INFO L433 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-01-23 14:57:59,229 INFO L276 IsEmpty]: Start isEmpty. Operand 183 states and 204 transitions. [2018-01-23 14:57:59,230 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 84 [2018-01-23 14:57:59,230 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:57:59,230 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-23 14:57:59,230 INFO L371 AbstractCegarLoop]: === Iteration 7 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-23 14:57:59,231 INFO L82 PathProgramCache]: Analyzing trace with hash -2073781002, now seen corresponding path program 1 times [2018-01-23 14:57:59,231 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:57:59,231 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:57:59,232 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:57:59,232 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:57:59,232 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:57:59,253 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:57:59,254 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:57:59,485 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2018-01-23 14:57:59,485 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-23 14:57:59,485 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-23 14:57:59,491 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:57:59,532 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:57:59,538 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-23 14:57:59,570 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 8 [2018-01-23 14:57:59,572 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-01-23 14:57:59,573 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:57:59,577 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:57:59,584 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:57:59,585 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:16, output treesize:8 [2018-01-23 14:57:59,596 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 16 treesize of output 12 [2018-01-23 14:57:59,598 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 4 [2018-01-23 14:57:59,598 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:57:59,600 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:57:59,601 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:57:59,601 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:16, output treesize:4 [2018-01-23 14:57:59,617 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2018-01-23 14:57:59,637 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-23 14:57:59,637 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 9 [2018-01-23 14:57:59,638 INFO L409 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-01-23 14:57:59,638 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-01-23 14:57:59,638 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2018-01-23 14:57:59,638 INFO L87 Difference]: Start difference. First operand 183 states and 204 transitions. Second operand 9 states. [2018-01-23 14:58:00,028 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:58:00,028 INFO L93 Difference]: Finished difference Result 317 states and 345 transitions. [2018-01-23 14:58:00,028 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-01-23 14:58:00,028 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 83 [2018-01-23 14:58:00,029 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:58:00,031 INFO L225 Difference]: With dead ends: 317 [2018-01-23 14:58:00,031 INFO L226 Difference]: Without dead ends: 304 [2018-01-23 14:58:00,032 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 97 GetRequests, 78 SyntacticMatches, 7 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 28 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=51, Invalid=131, Unknown=0, NotChecked=0, Total=182 [2018-01-23 14:58:00,032 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 304 states. [2018-01-23 14:58:00,045 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 304 to 197. [2018-01-23 14:58:00,046 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 197 states. [2018-01-23 14:58:00,047 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 197 states to 197 states and 219 transitions. [2018-01-23 14:58:00,048 INFO L78 Accepts]: Start accepts. Automaton has 197 states and 219 transitions. Word has length 83 [2018-01-23 14:58:00,048 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:58:00,048 INFO L432 AbstractCegarLoop]: Abstraction has 197 states and 219 transitions. [2018-01-23 14:58:00,048 INFO L433 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-01-23 14:58:00,048 INFO L276 IsEmpty]: Start isEmpty. Operand 197 states and 219 transitions. [2018-01-23 14:58:00,050 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 93 [2018-01-23 14:58:00,050 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:58:00,050 INFO L322 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-23 14:58:00,050 INFO L371 AbstractCegarLoop]: === Iteration 8 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-23 14:58:00,051 INFO L82 PathProgramCache]: Analyzing trace with hash 781104601, now seen corresponding path program 1 times [2018-01-23 14:58:00,051 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:58:00,051 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:58:00,052 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:58:00,052 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:58:00,052 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:58:00,076 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:58:00,077 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:58:00,104 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 5 proven. 0 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2018-01-23 14:58:00,104 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-23 14:58:00,105 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-01-23 14:58:00,105 INFO L409 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-01-23 14:58:00,105 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-01-23 14:58:00,105 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-23 14:58:00,106 INFO L87 Difference]: Start difference. First operand 197 states and 219 transitions. Second operand 3 states. [2018-01-23 14:58:00,122 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:58:00,123 INFO L93 Difference]: Finished difference Result 291 states and 323 transitions. [2018-01-23 14:58:00,123 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-01-23 14:58:00,123 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 92 [2018-01-23 14:58:00,123 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:58:00,124 INFO L225 Difference]: With dead ends: 291 [2018-01-23 14:58:00,125 INFO L226 Difference]: Without dead ends: 197 [2018-01-23 14:58:00,125 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-23 14:58:00,126 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 197 states. [2018-01-23 14:58:00,142 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 197 to 197. [2018-01-23 14:58:00,143 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 197 states. [2018-01-23 14:58:00,144 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 197 states to 197 states and 217 transitions. [2018-01-23 14:58:00,144 INFO L78 Accepts]: Start accepts. Automaton has 197 states and 217 transitions. Word has length 92 [2018-01-23 14:58:00,145 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:58:00,145 INFO L432 AbstractCegarLoop]: Abstraction has 197 states and 217 transitions. [2018-01-23 14:58:00,146 INFO L433 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-01-23 14:58:00,147 INFO L276 IsEmpty]: Start isEmpty. Operand 197 states and 217 transitions. [2018-01-23 14:58:00,148 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 95 [2018-01-23 14:58:00,148 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:58:00,148 INFO L322 BasicCegarLoop]: trace histogram [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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-23 14:58:00,149 INFO L371 AbstractCegarLoop]: === Iteration 9 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-23 14:58:00,149 INFO L82 PathProgramCache]: Analyzing trace with hash 832080079, now seen corresponding path program 2 times [2018-01-23 14:58:00,149 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:58:00,149 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:58:00,151 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:58:00,151 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:58:00,151 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:58:00,176 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:58:00,180 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:58:00,356 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2018-01-23 14:58:00,356 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-23 14:58:00,356 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-23 14:58:00,364 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-01-23 14:58:00,391 INFO L201 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-23 14:58:00,452 INFO L214 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-23 14:58:00,455 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-23 14:58:00,459 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-23 14:58:00,574 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 8 [2018-01-23 14:58:00,577 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-01-23 14:58:00,577 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:00,579 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:00,585 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:00,585 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:19, output treesize:12 [2018-01-23 14:58:00,630 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 16 treesize of output 12 [2018-01-23 14:58:00,633 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 4 [2018-01-23 14:58:00,633 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:00,638 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:00,643 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:00,644 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:16, output treesize:4 [2018-01-23 14:58:00,703 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2018-01-23 14:58:00,736 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-23 14:58:00,736 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 11] total 16 [2018-01-23 14:58:00,737 INFO L409 AbstractCegarLoop]: Interpolant automaton has 16 states [2018-01-23 14:58:00,737 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2018-01-23 14:58:00,737 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=44, Invalid=196, Unknown=0, NotChecked=0, Total=240 [2018-01-23 14:58:00,737 INFO L87 Difference]: Start difference. First operand 197 states and 217 transitions. Second operand 16 states. [2018-01-23 14:58:01,152 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:58:01,152 INFO L93 Difference]: Finished difference Result 287 states and 311 transitions. [2018-01-23 14:58:01,152 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2018-01-23 14:58:01,152 INFO L78 Accepts]: Start accepts. Automaton has 16 states. Word has length 94 [2018-01-23 14:58:01,153 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:58:01,154 INFO L225 Difference]: With dead ends: 287 [2018-01-23 14:58:01,154 INFO L226 Difference]: Without dead ends: 282 [2018-01-23 14:58:01,155 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 117 GetRequests, 88 SyntacticMatches, 2 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 145 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=204, Invalid=608, Unknown=0, NotChecked=0, Total=812 [2018-01-23 14:58:01,155 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 282 states. [2018-01-23 14:58:01,167 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 282 to 238. [2018-01-23 14:58:01,167 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 238 states. [2018-01-23 14:58:01,169 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 238 states to 238 states and 262 transitions. [2018-01-23 14:58:01,169 INFO L78 Accepts]: Start accepts. Automaton has 238 states and 262 transitions. Word has length 94 [2018-01-23 14:58:01,169 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:58:01,169 INFO L432 AbstractCegarLoop]: Abstraction has 238 states and 262 transitions. [2018-01-23 14:58:01,169 INFO L433 AbstractCegarLoop]: Interpolant automaton has 16 states. [2018-01-23 14:58:01,169 INFO L276 IsEmpty]: Start isEmpty. Operand 238 states and 262 transitions. [2018-01-23 14:58:01,170 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 96 [2018-01-23 14:58:01,170 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:58:01,170 INFO L322 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-23 14:58:01,170 INFO L371 AbstractCegarLoop]: === Iteration 10 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-23 14:58:01,170 INFO L82 PathProgramCache]: Analyzing trace with hash -1265792568, now seen corresponding path program 1 times [2018-01-23 14:58:01,170 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:58:01,170 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:58:01,171 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:58:01,171 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-01-23 14:58:01,171 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:58:01,198 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:58:01,199 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:58:02,310 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-01-23 14:58:02,310 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-23 14:58:02,310 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-23 14:58:02,317 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:58:02,360 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:58:02,366 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-23 14:58:02,859 WARN L1029 $PredicateComparison]: unable to prove that (exists ((v_prenex_2 Int) (v_prenex_1 Int) (main_~head~5.base Int)) (let ((.cse0 (store |c_old(#valid)| main_~head~5.base 1))) (let ((.cse1 (store .cse0 v_prenex_2 1))) (and (= 0 (select .cse0 v_prenex_2)) (= |c_#valid| (store (store .cse1 v_prenex_1 1) main_~head~5.base 0)) (not (= 0 main_~head~5.base)) (= 0 (select .cse1 v_prenex_1)) (= 0 (select |c_old(#valid)| main_~head~5.base)))))) is different from true [2018-01-23 14:58:02,913 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 7 trivial. 2 not checked. [2018-01-23 14:58:02,934 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-23 14:58:02,934 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 9] total 26 [2018-01-23 14:58:02,935 INFO L409 AbstractCegarLoop]: Interpolant automaton has 26 states [2018-01-23 14:58:02,935 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2018-01-23 14:58:02,935 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=104, Invalid=498, Unknown=2, NotChecked=46, Total=650 [2018-01-23 14:58:02,935 INFO L87 Difference]: Start difference. First operand 238 states and 262 transitions. Second operand 26 states. [2018-01-23 14:58:04,341 WARN L146 SmtUtils]: Spent 157ms on a formula simplification. DAG size of input: 74 DAG size of output 72 [2018-01-23 14:58:04,561 WARN L146 SmtUtils]: Spent 131ms on a formula simplification. DAG size of input: 64 DAG size of output 64 [2018-01-23 14:58:04,721 WARN L146 SmtUtils]: Spent 126ms on a formula simplification. DAG size of input: 63 DAG size of output 61 [2018-01-23 14:58:06,211 WARN L146 SmtUtils]: Spent 158ms on a formula simplification. DAG size of input: 79 DAG size of output 72 [2018-01-23 14:58:08,217 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:58:08,217 INFO L93 Difference]: Finished difference Result 1159 states and 1275 transitions. [2018-01-23 14:58:08,249 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 40 states. [2018-01-23 14:58:08,249 INFO L78 Accepts]: Start accepts. Automaton has 26 states. Word has length 95 [2018-01-23 14:58:08,250 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:58:08,254 INFO L225 Difference]: With dead ends: 1159 [2018-01-23 14:58:08,255 INFO L226 Difference]: Without dead ends: 1152 [2018-01-23 14:58:08,256 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 151 GetRequests, 94 SyntacticMatches, 2 SemanticMatches, 55 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 716 ImplicationChecksByTransitivity, 4.2s TimeCoverageRelationStatistics Valid=541, Invalid=2519, Unknown=24, NotChecked=108, Total=3192 [2018-01-23 14:58:08,257 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1152 states. [2018-01-23 14:58:08,288 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1152 to 397. [2018-01-23 14:58:08,288 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 397 states. [2018-01-23 14:58:08,289 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 397 states to 397 states and 447 transitions. [2018-01-23 14:58:08,289 INFO L78 Accepts]: Start accepts. Automaton has 397 states and 447 transitions. Word has length 95 [2018-01-23 14:58:08,290 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:58:08,290 INFO L432 AbstractCegarLoop]: Abstraction has 397 states and 447 transitions. [2018-01-23 14:58:08,290 INFO L433 AbstractCegarLoop]: Interpolant automaton has 26 states. [2018-01-23 14:58:08,290 INFO L276 IsEmpty]: Start isEmpty. Operand 397 states and 447 transitions. [2018-01-23 14:58:08,291 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 100 [2018-01-23 14:58:08,291 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:58:08,291 INFO L322 BasicCegarLoop]: trace histogram [3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-23 14:58:08,291 INFO L371 AbstractCegarLoop]: === Iteration 11 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-23 14:58:08,291 INFO L82 PathProgramCache]: Analyzing trace with hash -390068147, now seen corresponding path program 3 times [2018-01-23 14:58:08,291 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:58:08,291 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:58:08,292 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:58:08,292 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:58:08,292 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:58:08,306 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:58:08,307 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:58:08,797 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2018-01-23 14:58:08,798 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-23 14:58:08,798 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-23 14:58:08,806 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-01-23 14:58:08,825 INFO L254 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued a check-sat command [2018-01-23 14:58:08,876 INFO L254 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued a check-sat command [2018-01-23 14:58:08,878 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-23 14:58:08,883 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-23 14:58:08,887 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-23 14:58:08,888 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:08,912 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:08,912 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:10, output treesize:9 [2018-01-23 14:58:08,961 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:08,964 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:08,965 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 4 [2018-01-23 14:58:08,965 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:08,974 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:08,974 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:24, output treesize:18 [2018-01-23 14:58:09,001 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 8 [2018-01-23 14:58:09,003 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-01-23 14:58:09,003 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:09,006 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:09,015 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:09,015 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:29, output treesize:26 [2018-01-23 14:58:09,138 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:09,146 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 35 treesize of output 36 [2018-01-23 14:58:09,153 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-01-23 14:58:09,154 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:09,185 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:09,223 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:09,224 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:38, output treesize:30 [2018-01-23 14:58:09,309 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 2 new quantified variables, introduced 0 case distinctions, treesize of input 59 treesize of output 49 [2018-01-23 14:58:09,315 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:09,319 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 30 treesize of output 18 [2018-01-23 14:58:09,319 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:09,336 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:09,372 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-23 14:58:09,372 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:62, output treesize:31 [2018-01-23 14:58:09,426 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 35 treesize of output 23 [2018-01-23 14:58:09,428 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 9 [2018-01-23 14:58:09,428 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:09,432 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 1 [2018-01-23 14:58:09,432 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:09,434 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:09,436 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:09,436 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 2 variables, input treesize:35, output treesize:9 [2018-01-23 14:58:09,473 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2018-01-23 14:58:09,494 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-23 14:58:09,495 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 25 [2018-01-23 14:58:09,495 INFO L409 AbstractCegarLoop]: Interpolant automaton has 25 states [2018-01-23 14:58:09,495 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2018-01-23 14:58:09,495 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=74, Invalid=526, Unknown=0, NotChecked=0, Total=600 [2018-01-23 14:58:09,496 INFO L87 Difference]: Start difference. First operand 397 states and 447 transitions. Second operand 25 states. [2018-01-23 14:58:10,696 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:58:10,696 INFO L93 Difference]: Finished difference Result 790 states and 878 transitions. [2018-01-23 14:58:10,696 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2018-01-23 14:58:10,696 INFO L78 Accepts]: Start accepts. Automaton has 25 states. Word has length 99 [2018-01-23 14:58:10,696 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:58:10,699 INFO L225 Difference]: With dead ends: 790 [2018-01-23 14:58:10,699 INFO L226 Difference]: Without dead ends: 686 [2018-01-23 14:58:10,700 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 136 GetRequests, 90 SyntacticMatches, 2 SemanticMatches, 44 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 444 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=397, Invalid=1673, Unknown=0, NotChecked=0, Total=2070 [2018-01-23 14:58:10,701 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 686 states. [2018-01-23 14:58:10,747 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 686 to 406. [2018-01-23 14:58:10,748 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 406 states. [2018-01-23 14:58:10,749 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 406 states to 406 states and 456 transitions. [2018-01-23 14:58:10,749 INFO L78 Accepts]: Start accepts. Automaton has 406 states and 456 transitions. Word has length 99 [2018-01-23 14:58:10,750 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:58:10,750 INFO L432 AbstractCegarLoop]: Abstraction has 406 states and 456 transitions. [2018-01-23 14:58:10,750 INFO L433 AbstractCegarLoop]: Interpolant automaton has 25 states. [2018-01-23 14:58:10,750 INFO L276 IsEmpty]: Start isEmpty. Operand 406 states and 456 transitions. [2018-01-23 14:58:10,751 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 101 [2018-01-23 14:58:10,751 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:58:10,752 INFO L322 BasicCegarLoop]: trace histogram [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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-23 14:58:10,752 INFO L371 AbstractCegarLoop]: === Iteration 12 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-23 14:58:10,752 INFO L82 PathProgramCache]: Analyzing trace with hash -1613645068, now seen corresponding path program 2 times [2018-01-23 14:58:10,752 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:58:10,752 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:58:10,753 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:58:10,753 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-01-23 14:58:10,753 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:58:10,769 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:58:10,770 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:58:10,906 INFO L134 CoverageAnalysis]: Checked inductivity of 19 backedges. 4 proven. 7 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2018-01-23 14:58:10,906 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-23 14:58:10,906 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-23 14:58:10,913 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-01-23 14:58:10,936 INFO L201 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-23 14:58:10,987 INFO L214 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-23 14:58:10,991 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-23 14:58:10,997 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-23 14:58:11,124 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2018-01-23 14:58:11,128 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 3 [2018-01-23 14:58:11,128 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:11,131 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:11,132 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:11,133 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:15, output treesize:3 [2018-01-23 14:58:11,147 INFO L134 CoverageAnalysis]: Checked inductivity of 19 backedges. 4 proven. 7 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2018-01-23 14:58:11,179 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-23 14:58:11,179 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 12] total 17 [2018-01-23 14:58:11,179 INFO L409 AbstractCegarLoop]: Interpolant automaton has 17 states [2018-01-23 14:58:11,179 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2018-01-23 14:58:11,180 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=40, Invalid=232, Unknown=0, NotChecked=0, Total=272 [2018-01-23 14:58:11,180 INFO L87 Difference]: Start difference. First operand 406 states and 456 transitions. Second operand 17 states. [2018-01-23 14:58:11,757 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:58:11,757 INFO L93 Difference]: Finished difference Result 542 states and 596 transitions. [2018-01-23 14:58:11,757 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2018-01-23 14:58:11,758 INFO L78 Accepts]: Start accepts. Automaton has 17 states. Word has length 100 [2018-01-23 14:58:11,758 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:58:11,759 INFO L225 Difference]: With dead ends: 542 [2018-01-23 14:58:11,760 INFO L226 Difference]: Without dead ends: 521 [2018-01-23 14:58:11,760 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 126 GetRequests, 98 SyntacticMatches, 0 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 126 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=150, Invalid=720, Unknown=0, NotChecked=0, Total=870 [2018-01-23 14:58:11,761 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 521 states. [2018-01-23 14:58:11,807 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 521 to 430. [2018-01-23 14:58:11,807 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 430 states. [2018-01-23 14:58:11,809 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 430 states to 430 states and 482 transitions. [2018-01-23 14:58:11,809 INFO L78 Accepts]: Start accepts. Automaton has 430 states and 482 transitions. Word has length 100 [2018-01-23 14:58:11,810 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:58:11,810 INFO L432 AbstractCegarLoop]: Abstraction has 430 states and 482 transitions. [2018-01-23 14:58:11,810 INFO L433 AbstractCegarLoop]: Interpolant automaton has 17 states. [2018-01-23 14:58:11,810 INFO L276 IsEmpty]: Start isEmpty. Operand 430 states and 482 transitions. [2018-01-23 14:58:11,811 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 103 [2018-01-23 14:58:11,812 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:58:11,812 INFO L322 BasicCegarLoop]: trace histogram [3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-23 14:58:11,812 INFO L371 AbstractCegarLoop]: === Iteration 13 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-23 14:58:11,812 INFO L82 PathProgramCache]: Analyzing trace with hash 1975736536, now seen corresponding path program 1 times [2018-01-23 14:58:11,812 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:58:11,813 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:58:11,813 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:58:11,813 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-01-23 14:58:11,814 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:58:11,833 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:58:11,835 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:58:12,514 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 4 proven. 8 refuted. 0 times theorem prover too weak. 17 trivial. 0 not checked. [2018-01-23 14:58:12,515 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-23 14:58:12,515 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-23 14:58:12,521 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:58:12,548 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:58:12,552 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-23 14:58:12,723 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 57 treesize of output 69 [2018-01-23 14:58:12,728 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 58 treesize of output 42 [2018-01-23 14:58:12,728 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:12,770 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 1 new quantified variables, introduced 2 case distinctions, treesize of input 55 treesize of output 50 [2018-01-23 14:58:12,771 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 2 xjuncts. [2018-01-23 14:58:12,800 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-23 14:58:12,838 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 57 treesize of output 54 [2018-01-23 14:58:12,840 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 1 [2018-01-23 14:58:12,840 INFO L267 ElimStorePlain]: Start of recursive call 6: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:12,847 INFO L267 ElimStorePlain]: Start of recursive call 5: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:12,878 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 38 treesize of output 35 [2018-01-23 14:58:12,880 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 16 treesize of output 1 [2018-01-23 14:58:12,880 INFO L267 ElimStorePlain]: Start of recursive call 8: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:12,884 INFO L267 ElimStorePlain]: Start of recursive call 7: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:12,887 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 38 treesize of output 35 [2018-01-23 14:58:12,889 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 16 treesize of output 1 [2018-01-23 14:58:12,889 INFO L267 ElimStorePlain]: Start of recursive call 10: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:12,894 INFO L267 ElimStorePlain]: Start of recursive call 9: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:12,933 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 38 treesize of output 50 [2018-01-23 14:58:12,937 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 39 treesize of output 23 [2018-01-23 14:58:12,937 INFO L267 ElimStorePlain]: Start of recursive call 12: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:12,967 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 1 new quantified variables, introduced 2 case distinctions, treesize of input 36 treesize of output 31 [2018-01-23 14:58:12,968 INFO L267 ElimStorePlain]: Start of recursive call 13: End of recursive call: and 2 xjuncts. [2018-01-23 14:58:12,984 INFO L267 ElimStorePlain]: Start of recursive call 11: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-23 14:58:13,003 INFO L267 ElimStorePlain]: Start of recursive call 1: 4 dim-2 vars, End of recursive call: and 3 xjuncts. [2018-01-23 14:58:13,003 INFO L202 ElimStorePlain]: Needed 13 recursive calls to eliminate 4 variables, input treesize:115, output treesize:58 [2018-01-23 14:58:13,079 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 41 treesize of output 38 [2018-01-23 14:58:13,081 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-01-23 14:58:13,081 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:13,090 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:13,200 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 37 treesize of output 49 [2018-01-23 14:58:13,205 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 38 treesize of output 37 [2018-01-23 14:58:13,205 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:13,236 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 1 new quantified variables, introduced 2 case distinctions, treesize of input 35 treesize of output 43 [2018-01-23 14:58:13,237 INFO L267 ElimStorePlain]: Start of recursive call 6: End of recursive call: and 2 xjuncts. [2018-01-23 14:58:13,288 INFO L267 ElimStorePlain]: Start of recursive call 4: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-23 14:58:13,355 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 40 treesize of output 37 [2018-01-23 14:58:13,357 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 9 [2018-01-23 14:58:13,357 INFO L267 ElimStorePlain]: Start of recursive call 8: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:13,364 INFO L267 ElimStorePlain]: Start of recursive call 7: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:13,426 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 41 treesize of output 53 [2018-01-23 14:58:13,429 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 42 treesize of output 41 [2018-01-23 14:58:13,430 INFO L267 ElimStorePlain]: Start of recursive call 10: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:13,460 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 1 new quantified variables, introduced 2 case distinctions, treesize of input 39 treesize of output 47 [2018-01-23 14:58:13,461 INFO L267 ElimStorePlain]: Start of recursive call 11: End of recursive call: and 2 xjuncts. [2018-01-23 14:58:13,481 INFO L267 ElimStorePlain]: Start of recursive call 9: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-23 14:58:13,535 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 34 [2018-01-23 14:58:13,537 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-01-23 14:58:13,537 INFO L267 ElimStorePlain]: Start of recursive call 13: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:13,543 INFO L267 ElimStorePlain]: Start of recursive call 12: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:13,546 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 35 treesize of output 32 [2018-01-23 14:58:13,547 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-01-23 14:58:13,548 INFO L267 ElimStorePlain]: Start of recursive call 15: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:13,555 INFO L267 ElimStorePlain]: Start of recursive call 14: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:13,602 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 36 treesize of output 33 [2018-01-23 14:58:13,603 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 9 [2018-01-23 14:58:13,604 INFO L267 ElimStorePlain]: Start of recursive call 17: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:13,610 INFO L267 ElimStorePlain]: Start of recursive call 16: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:13,651 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 6 dim-2 vars, End of recursive call: 2 dim-0 vars, and 4 xjuncts. [2018-01-23 14:58:13,652 INFO L202 ElimStorePlain]: Needed 17 recursive calls to eliminate 8 variables, input treesize:123, output treesize:127 [2018-01-23 14:58:13,744 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 42 treesize of output 38 [2018-01-23 14:58:13,747 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 3 [2018-01-23 14:58:13,747 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:13,756 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:13,804 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 47 treesize of output 51 [2018-01-23 14:58:13,812 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 43 treesize of output 41 [2018-01-23 14:58:13,812 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 2 xjuncts. [2018-01-23 14:58:13,844 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 43 treesize of output 38 [2018-01-23 14:58:13,845 INFO L267 ElimStorePlain]: Start of recursive call 6: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:13,873 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 38 treesize of output 33 [2018-01-23 14:58:13,874 INFO L267 ElimStorePlain]: Start of recursive call 7: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:13,888 INFO L267 ElimStorePlain]: Start of recursive call 4: 3 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:13,920 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 47 treesize of output 49 [2018-01-23 14:58:13,923 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 41 treesize of output 33 [2018-01-23 14:58:13,924 INFO L267 ElimStorePlain]: Start of recursive call 9: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:13,947 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 45 treesize of output 38 [2018-01-23 14:58:13,948 INFO L267 ElimStorePlain]: Start of recursive call 10: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:13,970 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 38 treesize of output 33 [2018-01-23 14:58:13,970 INFO L267 ElimStorePlain]: Start of recursive call 11: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:13,990 INFO L267 ElimStorePlain]: Start of recursive call 8: 3 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-23 14:58:14,024 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 3 dim-2 vars, End of recursive call: 3 dim-0 vars, and 4 xjuncts. [2018-01-23 14:58:14,024 INFO L202 ElimStorePlain]: Needed 11 recursive calls to eliminate 5 variables, input treesize:137, output treesize:131 [2018-01-23 14:58:14,146 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:14,146 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 19 treesize of output 20 [2018-01-23 14:58:14,148 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 20 treesize of output 12 [2018-01-23 14:58:14,149 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:14,151 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:14,154 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:14,154 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:23, output treesize:12 [2018-01-23 14:58:14,250 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2018-01-23 14:58:14,255 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 1 case distinctions, treesize of input 11 treesize of output 8 [2018-01-23 14:58:14,256 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-23 14:58:14,258 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-23 14:58:14,263 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 2 xjuncts. [2018-01-23 14:58:14,263 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:19, output treesize:18 [2018-01-23 14:58:14,321 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-23 14:58:14,322 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:14,324 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:14,324 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:11, output treesize:10 [2018-01-23 14:58:14,424 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 4 proven. 5 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2018-01-23 14:58:14,446 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-23 14:58:14,446 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [24, 19] total 41 [2018-01-23 14:58:14,446 INFO L409 AbstractCegarLoop]: Interpolant automaton has 41 states [2018-01-23 14:58:14,446 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 41 interpolants. [2018-01-23 14:58:14,447 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=139, Invalid=1501, Unknown=0, NotChecked=0, Total=1640 [2018-01-23 14:58:14,447 INFO L87 Difference]: Start difference. First operand 430 states and 482 transitions. Second operand 41 states. [2018-01-23 14:58:16,171 WARN L146 SmtUtils]: Spent 119ms on a formula simplification. DAG size of input: 108 DAG size of output 59 [2018-01-23 14:58:17,093 WARN L146 SmtUtils]: Spent 138ms on a formula simplification. DAG size of input: 92 DAG size of output 78 [2018-01-23 14:58:17,778 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:58:17,779 INFO L93 Difference]: Finished difference Result 801 states and 891 transitions. [2018-01-23 14:58:17,779 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 44 states. [2018-01-23 14:58:17,779 INFO L78 Accepts]: Start accepts. Automaton has 41 states. Word has length 102 [2018-01-23 14:58:17,779 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:58:17,781 INFO L225 Difference]: With dead ends: 801 [2018-01-23 14:58:17,782 INFO L226 Difference]: Without dead ends: 704 [2018-01-23 14:58:17,784 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 168 GetRequests, 86 SyntacticMatches, 2 SemanticMatches, 80 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1510 ImplicationChecksByTransitivity, 3.4s TimeCoverageRelationStatistics Valid=951, Invalid=5691, Unknown=0, NotChecked=0, Total=6642 [2018-01-23 14:58:17,784 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 704 states. [2018-01-23 14:58:17,837 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 704 to 437. [2018-01-23 14:58:17,838 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 437 states. [2018-01-23 14:58:17,839 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 437 states to 437 states and 489 transitions. [2018-01-23 14:58:17,839 INFO L78 Accepts]: Start accepts. Automaton has 437 states and 489 transitions. Word has length 102 [2018-01-23 14:58:17,839 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:58:17,839 INFO L432 AbstractCegarLoop]: Abstraction has 437 states and 489 transitions. [2018-01-23 14:58:17,840 INFO L433 AbstractCegarLoop]: Interpolant automaton has 41 states. [2018-01-23 14:58:17,840 INFO L276 IsEmpty]: Start isEmpty. Operand 437 states and 489 transitions. [2018-01-23 14:58:17,841 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 103 [2018-01-23 14:58:17,841 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:58:17,842 INFO L322 BasicCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-23 14:58:17,842 INFO L371 AbstractCegarLoop]: === Iteration 14 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-23 14:58:17,842 INFO L82 PathProgramCache]: Analyzing trace with hash -1661833282, now seen corresponding path program 1 times [2018-01-23 14:58:17,842 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:58:17,842 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:58:17,843 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:58:17,843 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:58:17,843 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:58:17,858 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:58:17,859 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:58:18,015 INFO L134 CoverageAnalysis]: Checked inductivity of 21 backedges. 4 proven. 9 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2018-01-23 14:58:18,016 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-23 14:58:18,016 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-23 14:58:18,022 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:58:18,055 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:58:18,060 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-23 14:58:18,193 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2018-01-23 14:58:18,198 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 1 case distinctions, treesize of input 11 treesize of output 8 [2018-01-23 14:58:18,199 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-23 14:58:18,201 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-23 14:58:18,206 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 2 xjuncts. [2018-01-23 14:58:18,206 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:15, output treesize:8 [2018-01-23 14:58:18,264 INFO L134 CoverageAnalysis]: Checked inductivity of 21 backedges. 6 proven. 7 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2018-01-23 14:58:18,299 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-23 14:58:18,299 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 14] total 21 [2018-01-23 14:58:18,300 INFO L409 AbstractCegarLoop]: Interpolant automaton has 21 states [2018-01-23 14:58:18,300 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2018-01-23 14:58:18,300 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=46, Invalid=374, Unknown=0, NotChecked=0, Total=420 [2018-01-23 14:58:18,300 INFO L87 Difference]: Start difference. First operand 437 states and 489 transitions. Second operand 21 states. [2018-01-23 14:58:18,891 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:58:18,891 INFO L93 Difference]: Finished difference Result 580 states and 639 transitions. [2018-01-23 14:58:18,892 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2018-01-23 14:58:18,892 INFO L78 Accepts]: Start accepts. Automaton has 21 states. Word has length 102 [2018-01-23 14:58:18,892 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:58:18,893 INFO L225 Difference]: With dead ends: 580 [2018-01-23 14:58:18,894 INFO L226 Difference]: Without dead ends: 559 [2018-01-23 14:58:18,894 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 131 GetRequests, 98 SyntacticMatches, 0 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 129 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=182, Invalid=1008, Unknown=0, NotChecked=0, Total=1190 [2018-01-23 14:58:18,895 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 559 states. [2018-01-23 14:58:18,948 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 559 to 430. [2018-01-23 14:58:18,949 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 430 states. [2018-01-23 14:58:18,951 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 430 states to 430 states and 482 transitions. [2018-01-23 14:58:18,951 INFO L78 Accepts]: Start accepts. Automaton has 430 states and 482 transitions. Word has length 102 [2018-01-23 14:58:18,951 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:58:18,952 INFO L432 AbstractCegarLoop]: Abstraction has 430 states and 482 transitions. [2018-01-23 14:58:18,952 INFO L433 AbstractCegarLoop]: Interpolant automaton has 21 states. [2018-01-23 14:58:18,952 INFO L276 IsEmpty]: Start isEmpty. Operand 430 states and 482 transitions. [2018-01-23 14:58:18,954 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 106 [2018-01-23 14:58:18,954 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:58:18,954 INFO L322 BasicCegarLoop]: trace histogram [3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-23 14:58:18,954 INFO L371 AbstractCegarLoop]: === Iteration 15 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-23 14:58:18,954 INFO L82 PathProgramCache]: Analyzing trace with hash -471619372, now seen corresponding path program 1 times [2018-01-23 14:58:18,954 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:58:18,955 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:58:18,955 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:58:18,955 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:58:18,956 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:58:18,972 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:58:18,973 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:58:19,817 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 0 proven. 24 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2018-01-23 14:58:19,817 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-23 14:58:19,817 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-23 14:58:19,822 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:58:19,849 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:58:19,852 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-23 14:58:20,025 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 52 treesize of output 64 [2018-01-23 14:58:20,028 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 53 treesize of output 52 [2018-01-23 14:58:20,028 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:20,069 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:20,106 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 48 treesize of output 58 [2018-01-23 14:58:20,109 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 49 treesize of output 48 [2018-01-23 14:58:20,110 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:20,161 INFO L267 ElimStorePlain]: Start of recursive call 4: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:20,198 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 52 treesize of output 64 [2018-01-23 14:58:20,201 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 53 treesize of output 52 [2018-01-23 14:58:20,201 INFO L267 ElimStorePlain]: Start of recursive call 7: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:20,244 INFO L267 ElimStorePlain]: Start of recursive call 6: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:20,278 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 48 treesize of output 58 [2018-01-23 14:58:20,281 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 1 new quantified variables, introduced 0 case distinctions, treesize of input 44 treesize of output 46 [2018-01-23 14:58:20,282 INFO L267 ElimStorePlain]: Start of recursive call 9: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:20,311 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 45 treesize of output 44 [2018-01-23 14:58:20,312 INFO L267 ElimStorePlain]: Start of recursive call 10: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:20,326 INFO L267 ElimStorePlain]: Start of recursive call 8: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:20,347 INFO L267 ElimStorePlain]: Start of recursive call 1: 4 dim-2 vars, End of recursive call: and 2 xjuncts. [2018-01-23 14:58:20,347 INFO L202 ElimStorePlain]: Needed 10 recursive calls to eliminate 4 variables, input treesize:105, output treesize:89 [2018-01-23 14:58:20,410 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 3 case distinctions, treesize of input 60 treesize of output 70 [2018-01-23 14:58:20,414 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 59 treesize of output 49 [2018-01-23 14:58:20,415 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:20,457 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 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 2 case distinctions, treesize of input 53 treesize of output 59 [2018-01-23 14:58:20,458 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 2 xjuncts. [2018-01-23 14:58:20,476 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:20,517 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 3 case distinctions, treesize of input 60 treesize of output 68 [2018-01-23 14:58:20,521 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 57 treesize of output 49 [2018-01-23 14:58:20,522 INFO L267 ElimStorePlain]: Start of recursive call 6: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:20,566 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 54 treesize of output 58 [2018-01-23 14:58:20,567 INFO L267 ElimStorePlain]: Start of recursive call 7: End of recursive call: and 2 xjuncts. [2018-01-23 14:58:20,586 INFO L267 ElimStorePlain]: Start of recursive call 5: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:20,618 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 3 case distinctions, treesize of input 45 treesize of output 65 [2018-01-23 14:58:20,622 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 50 treesize of output 42 [2018-01-23 14:58:20,622 INFO L267 ElimStorePlain]: Start of recursive call 9: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:20,659 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 43 treesize of output 47 [2018-01-23 14:58:20,659 INFO L267 ElimStorePlain]: Start of recursive call 10: End of recursive call: and 2 xjuncts. [2018-01-23 14:58:20,680 INFO L267 ElimStorePlain]: Start of recursive call 8: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-23 14:58:20,716 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 3 case distinctions, treesize of input 45 treesize of output 67 [2018-01-23 14:58:20,720 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 52 treesize of output 38 [2018-01-23 14:58:20,720 INFO L267 ElimStorePlain]: Start of recursive call 12: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:20,756 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 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 2 case distinctions, treesize of input 38 treesize of output 44 [2018-01-23 14:58:20,756 INFO L267 ElimStorePlain]: Start of recursive call 13: End of recursive call: and 2 xjuncts. [2018-01-23 14:58:20,770 INFO L267 ElimStorePlain]: Start of recursive call 11: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:20,791 INFO L267 ElimStorePlain]: Start of recursive call 1: 4 dim-0 vars, 4 dim-2 vars, End of recursive call: and 3 xjuncts. [2018-01-23 14:58:20,791 INFO L202 ElimStorePlain]: Needed 13 recursive calls to eliminate 8 variables, input treesize:121, output treesize:71 [2018-01-23 14:58:20,954 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 51 treesize of output 51 [2018-01-23 14:58:20,960 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 2 new quantified variables, introduced 1 case distinctions, treesize of input 39 treesize of output 39 [2018-01-23 14:58:20,960 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-23 14:58:20,977 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 47 treesize of output 40 [2018-01-23 14:58:20,977 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:20,992 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 1 new quantified variables, introduced 0 case distinctions, treesize of input 40 treesize of output 36 [2018-01-23 14:58:20,993 INFO L267 ElimStorePlain]: Start of recursive call 5: 1 dim-0 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-23 14:58:21,006 INFO L267 ElimStorePlain]: Start of recursive call 2: 3 dim-1 vars, End of recursive call: 2 dim-0 vars, and 3 xjuncts. [2018-01-23 14:58:21,030 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 51 treesize of output 45 [2018-01-23 14:58:21,032 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 41 treesize of output 30 [2018-01-23 14:58:21,032 INFO L267 ElimStorePlain]: Start of recursive call 7: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:21,043 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 30 treesize of output 28 [2018-01-23 14:58:21,043 INFO L267 ElimStorePlain]: Start of recursive call 8: 1 dim-0 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-23 14:58:21,054 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:21,056 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 27 [2018-01-23 14:58:21,056 INFO L267 ElimStorePlain]: Start of recursive call 9: 1 dim-0 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-23 14:58:21,066 INFO L267 ElimStorePlain]: Start of recursive call 6: 3 dim-1 vars, End of recursive call: 2 dim-0 vars, and 2 xjuncts. [2018-01-23 14:58:21,091 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-2 vars, End of recursive call: 4 dim-0 vars, and 5 xjuncts. [2018-01-23 14:58:21,092 INFO L202 ElimStorePlain]: Needed 9 recursive calls to eliminate 2 variables, input treesize:103, output treesize:149 [2018-01-23 14:58:21,298 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 0 proven. 17 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2018-01-23 14:58:21,319 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-23 14:58:21,319 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [24, 15] total 37 [2018-01-23 14:58:21,319 INFO L409 AbstractCegarLoop]: Interpolant automaton has 37 states [2018-01-23 14:58:21,319 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 37 interpolants. [2018-01-23 14:58:21,320 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=143, Invalid=1189, Unknown=0, NotChecked=0, Total=1332 [2018-01-23 14:58:21,320 INFO L87 Difference]: Start difference. First operand 430 states and 482 transitions. Second operand 37 states. [2018-01-23 14:58:22,418 WARN L146 SmtUtils]: Spent 105ms on a formula simplification. DAG size of input: 98 DAG size of output 66 [2018-01-23 14:58:22,743 WARN L146 SmtUtils]: Spent 110ms on a formula simplification. DAG size of input: 101 DAG size of output 69 [2018-01-23 14:58:22,988 WARN L146 SmtUtils]: Spent 138ms on a formula simplification. DAG size of input: 130 DAG size of output 76 [2018-01-23 14:58:23,581 WARN L146 SmtUtils]: Spent 102ms on a formula simplification. DAG size of input: 114 DAG size of output 88 [2018-01-23 14:58:25,084 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:58:25,084 INFO L93 Difference]: Finished difference Result 1057 states and 1173 transitions. [2018-01-23 14:58:25,084 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 44 states. [2018-01-23 14:58:25,084 INFO L78 Accepts]: Start accepts. Automaton has 37 states. Word has length 105 [2018-01-23 14:58:25,085 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:58:25,086 INFO L225 Difference]: With dead ends: 1057 [2018-01-23 14:58:25,086 INFO L226 Difference]: Without dead ends: 669 [2018-01-23 14:58:25,087 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 170 GetRequests, 94 SyntacticMatches, 0 SemanticMatches, 76 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1450 ImplicationChecksByTransitivity, 3.8s TimeCoverageRelationStatistics Valid=969, Invalid=5037, Unknown=0, NotChecked=0, Total=6006 [2018-01-23 14:58:25,088 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 669 states. [2018-01-23 14:58:25,141 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 669 to 534. [2018-01-23 14:58:25,141 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 534 states. [2018-01-23 14:58:25,143 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 534 states to 534 states and 589 transitions. [2018-01-23 14:58:25,143 INFO L78 Accepts]: Start accepts. Automaton has 534 states and 589 transitions. Word has length 105 [2018-01-23 14:58:25,143 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:58:25,143 INFO L432 AbstractCegarLoop]: Abstraction has 534 states and 589 transitions. [2018-01-23 14:58:25,143 INFO L433 AbstractCegarLoop]: Interpolant automaton has 37 states. [2018-01-23 14:58:25,143 INFO L276 IsEmpty]: Start isEmpty. Operand 534 states and 589 transitions. [2018-01-23 14:58:25,144 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 112 [2018-01-23 14:58:25,144 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:58:25,144 INFO L322 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 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-23 14:58:25,144 INFO L371 AbstractCegarLoop]: === Iteration 16 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-23 14:58:25,144 INFO L82 PathProgramCache]: Analyzing trace with hash 531869476, now seen corresponding path program 4 times [2018-01-23 14:58:25,144 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:58:25,144 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:58:25,145 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:58:25,145 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:58:25,145 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:58:25,165 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:58:25,166 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:58:25,935 INFO L134 CoverageAnalysis]: Checked inductivity of 44 backedges. 4 proven. 23 refuted. 0 times theorem prover too weak. 17 trivial. 0 not checked. [2018-01-23 14:58:25,935 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-23 14:58:25,935 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-23 14:58:25,941 INFO L101 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-01-23 14:58:25,974 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-23 14:58:25,977 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-23 14:58:25,980 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-23 14:58:25,980 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:25,981 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:25,981 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:6, output treesize:5 [2018-01-23 14:58:26,030 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:26,030 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:26,031 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-23 14:58:26,031 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:26,038 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:26,038 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:27, output treesize:25 [2018-01-23 14:58:26,063 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 8 [2018-01-23 14:58:26,064 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-01-23 14:58:26,064 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:26,065 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:26,073 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:26,073 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:36, output treesize:37 [2018-01-23 14:58:26,157 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:26,159 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 44 treesize of output 45 [2018-01-23 14:58:26,161 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-01-23 14:58:26,161 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:26,167 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:26,173 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:26,173 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:49, output treesize:41 [2018-01-23 14:58:26,276 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 51 treesize of output 50 [2018-01-23 14:58:26,278 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:26,279 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 14 [2018-01-23 14:58:26,280 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:26,286 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:26,293 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:26,293 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:60, output treesize:41 [2018-01-23 14:58:26,296 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:26,297 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:26,298 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:26,298 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 20 treesize of output 21 [2018-01-23 14:58:26,299 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:26,306 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:26,307 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:46, output treesize:39 [2018-01-23 14:58:26,347 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 42 treesize of output 41 [2018-01-23 14:58:26,350 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 14 treesize of output 7 [2018-01-23 14:58:26,350 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:26,356 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:26,362 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:26,362 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:50, output treesize:40 [2018-01-23 14:58:26,472 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:26,472 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:26,478 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 4 disjoint index pairs (out of 3 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 67 treesize of output 71 [2018-01-23 14:58:26,480 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-01-23 14:58:26,480 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:26,489 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:26,497 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-23 14:58:26,497 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:67, output treesize:55 [2018-01-23 14:58:26,551 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 3 new quantified variables, introduced 0 case distinctions, treesize of input 103 treesize of output 76 [2018-01-23 14:58:26,555 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:26,556 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 38 treesize of output 22 [2018-01-23 14:58:26,556 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:26,562 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:26,568 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: 2 dim-0 vars, and 1 xjuncts. [2018-01-23 14:58:26,568 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:103, output treesize:60 [2018-01-23 14:58:26,656 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 4 new quantified variables, introduced 0 case distinctions, treesize of input 67 treesize of output 42 [2018-01-23 14:58:26,658 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 15 treesize of output 11 [2018-01-23 14:58:26,659 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:26,663 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 9 [2018-01-23 14:58:26,664 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:26,667 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 1 [2018-01-23 14:58:26,668 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:26,669 INFO L267 ElimStorePlain]: Start of recursive call 2: 3 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:26,672 INFO L267 ElimStorePlain]: Start of recursive call 1: 4 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:26,672 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 5 variables, input treesize:67, output treesize:4 [2018-01-23 14:58:26,739 INFO L134 CoverageAnalysis]: Checked inductivity of 44 backedges. 0 proven. 18 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2018-01-23 14:58:26,760 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-23 14:58:26,760 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [30, 20] total 48 [2018-01-23 14:58:26,760 INFO L409 AbstractCegarLoop]: Interpolant automaton has 48 states [2018-01-23 14:58:26,761 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 48 interpolants. [2018-01-23 14:58:26,761 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=163, Invalid=2093, Unknown=0, NotChecked=0, Total=2256 [2018-01-23 14:58:26,761 INFO L87 Difference]: Start difference. First operand 534 states and 589 transitions. Second operand 48 states. [2018-01-23 14:58:28,297 WARN L146 SmtUtils]: Spent 115ms on a formula simplification. DAG size of input: 62 DAG size of output 48 [2018-01-23 14:58:31,040 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:58:31,040 INFO L93 Difference]: Finished difference Result 952 states and 1044 transitions. [2018-01-23 14:58:31,041 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 56 states. [2018-01-23 14:58:31,041 INFO L78 Accepts]: Start accepts. Automaton has 48 states. Word has length 111 [2018-01-23 14:58:31,041 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:58:31,042 INFO L225 Difference]: With dead ends: 952 [2018-01-23 14:58:31,042 INFO L226 Difference]: Without dead ends: 760 [2018-01-23 14:58:31,045 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 195 GetRequests, 95 SyntacticMatches, 2 SemanticMatches, 98 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2636 ImplicationChecksByTransitivity, 3.8s TimeCoverageRelationStatistics Valid=1318, Invalid=8582, Unknown=0, NotChecked=0, Total=9900 [2018-01-23 14:58:31,045 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 760 states. [2018-01-23 14:58:31,085 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 760 to 513. [2018-01-23 14:58:31,085 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 513 states. [2018-01-23 14:58:31,087 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 513 states to 513 states and 564 transitions. [2018-01-23 14:58:31,087 INFO L78 Accepts]: Start accepts. Automaton has 513 states and 564 transitions. Word has length 111 [2018-01-23 14:58:31,087 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:58:31,087 INFO L432 AbstractCegarLoop]: Abstraction has 513 states and 564 transitions. [2018-01-23 14:58:31,087 INFO L433 AbstractCegarLoop]: Interpolant automaton has 48 states. [2018-01-23 14:58:31,087 INFO L276 IsEmpty]: Start isEmpty. Operand 513 states and 564 transitions. [2018-01-23 14:58:31,088 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 113 [2018-01-23 14:58:31,088 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:58:31,088 INFO L322 BasicCegarLoop]: trace histogram [4, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-23 14:58:31,088 INFO L371 AbstractCegarLoop]: === Iteration 17 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-23 14:58:31,088 INFO L82 PathProgramCache]: Analyzing trace with hash -1917037198, now seen corresponding path program 1 times [2018-01-23 14:58:31,089 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:58:31,089 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:58:31,089 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:58:31,089 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-01-23 14:58:31,089 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:58:31,099 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:58:31,100 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:58:31,170 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2018-01-23 14:58:31,170 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-23 14:58:31,170 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-01-23 14:58:31,171 INFO L409 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-01-23 14:58:31,171 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-01-23 14:58:31,171 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-01-23 14:58:31,171 INFO L87 Difference]: Start difference. First operand 513 states and 564 transitions. Second operand 4 states. [2018-01-23 14:58:31,254 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:58:31,254 INFO L93 Difference]: Finished difference Result 628 states and 692 transitions. [2018-01-23 14:58:31,255 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-01-23 14:58:31,255 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 112 [2018-01-23 14:58:31,255 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:58:31,256 INFO L225 Difference]: With dead ends: 628 [2018-01-23 14:58:31,256 INFO L226 Difference]: Without dead ends: 560 [2018-01-23 14:58:31,256 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-23 14:58:31,257 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 560 states. [2018-01-23 14:58:31,296 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 560 to 527. [2018-01-23 14:58:31,297 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 527 states. [2018-01-23 14:58:31,298 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 527 states to 527 states and 582 transitions. [2018-01-23 14:58:31,298 INFO L78 Accepts]: Start accepts. Automaton has 527 states and 582 transitions. Word has length 112 [2018-01-23 14:58:31,298 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:58:31,298 INFO L432 AbstractCegarLoop]: Abstraction has 527 states and 582 transitions. [2018-01-23 14:58:31,299 INFO L433 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-01-23 14:58:31,299 INFO L276 IsEmpty]: Start isEmpty. Operand 527 states and 582 transitions. [2018-01-23 14:58:31,299 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 114 [2018-01-23 14:58:31,299 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:58:31,300 INFO L322 BasicCegarLoop]: trace histogram [3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-23 14:58:31,300 INFO L371 AbstractCegarLoop]: === Iteration 18 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-23 14:58:31,300 INFO L82 PathProgramCache]: Analyzing trace with hash 373053973, now seen corresponding path program 3 times [2018-01-23 14:58:31,300 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:58:31,300 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:58:31,301 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:58:31,301 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:58:31,301 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:58:31,312 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:58:31,313 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:58:31,724 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 1 proven. 7 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2018-01-23 14:58:31,725 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-23 14:58:31,725 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-23 14:58:31,731 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-01-23 14:58:31,752 INFO L254 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued a check-sat command [2018-01-23 14:58:31,787 INFO L254 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued a check-sat command [2018-01-23 14:58:31,791 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-23 14:58:31,796 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-23 14:58:31,798 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-23 14:58:31,799 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:31,811 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:31,811 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:10, output treesize:9 [2018-01-23 14:58:31,885 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:31,885 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:31,886 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 21 [2018-01-23 14:58:31,886 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:31,895 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:31,895 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:29, output treesize:27 [2018-01-23 14:58:31,926 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 8 [2018-01-23 14:58:31,937 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-01-23 14:58:31,937 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:31,945 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:32,013 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 8 [2018-01-23 14:58:32,020 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-01-23 14:58:32,021 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:32,025 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:32,083 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 2 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:32,083 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 3 variables, input treesize:46, output treesize:39 [2018-01-23 14:58:32,383 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:32,387 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 36 treesize of output 37 [2018-01-23 14:58:32,389 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-01-23 14:58:32,389 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:32,396 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:32,410 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 19 treesize of output 24 [2018-01-23 14:58:32,413 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 11 [2018-01-23 14:58:32,413 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:32,418 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:32,427 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:32,428 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 2 variables, input treesize:62, output treesize:54 [2018-01-23 14:58:32,478 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 102 treesize of output 92 [2018-01-23 14:58:32,481 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:32,482 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 30 treesize of output 18 [2018-01-23 14:58:32,483 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:32,492 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:32,508 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 50 treesize of output 45 [2018-01-23 14:58:32,511 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:32,512 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 30 treesize of output 18 [2018-01-23 14:58:32,513 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:32,517 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:32,525 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 2 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-23 14:58:32,525 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 3 variables, input treesize:117, output treesize:55 [2018-01-23 14:58:32,983 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:32,984 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:32,985 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:32,986 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 82 treesize of output 75 [2018-01-23 14:58:32,987 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:33,026 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:33,027 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:33,028 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:33,028 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:33,029 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 74 treesize of output 75 [2018-01-23 14:58:33,029 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:33,061 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-23 14:58:33,061 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:157, output treesize:143 [2018-01-23 14:58:33,223 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:33,229 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 105 treesize of output 106 [2018-01-23 14:58:33,231 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 16 treesize of output 1 [2018-01-23 14:58:33,231 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:33,244 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:33,296 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 113 treesize of output 106 [2018-01-23 14:58:33,298 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 16 treesize of output 1 [2018-01-23 14:58:33,298 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:33,312 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:33,349 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:33,353 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:33,355 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 1 new quantified variables, introduced 0 case distinctions, treesize of input 82 treesize of output 103 [2018-01-23 14:58:33,357 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 16 treesize of output 1 [2018-01-23 14:58:33,357 INFO L267 ElimStorePlain]: Start of recursive call 7: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:33,369 INFO L267 ElimStorePlain]: Start of recursive call 6: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:33,405 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 90 treesize of output 87 [2018-01-23 14:58:33,406 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 16 treesize of output 1 [2018-01-23 14:58:33,406 INFO L267 ElimStorePlain]: Start of recursive call 9: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:33,417 INFO L267 ElimStorePlain]: Start of recursive call 8: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:33,445 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 4 dim-2 vars, End of recursive call: 2 dim-0 vars, and 2 xjuncts. [2018-01-23 14:58:33,446 INFO L202 ElimStorePlain]: Needed 9 recursive calls to eliminate 6 variables, input treesize:219, output treesize:139 [2018-01-23 14:58:33,522 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:33,525 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 4 disjoint index pairs (out of 6 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 94 treesize of output 96 [2018-01-23 14:58:33,552 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 16 [2018-01-23 14:58:33,552 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:33,567 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:33,607 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:33,611 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:33,612 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:33,613 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 1 new quantified variables, introduced 0 case distinctions, treesize of input 86 treesize of output 120 [2018-01-23 14:58:33,615 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 22 treesize of output 20 [2018-01-23 14:58:33,616 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:33,632 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:33,665 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:33,670 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 78 treesize of output 83 [2018-01-23 14:58:33,672 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-01-23 14:58:33,672 INFO L267 ElimStorePlain]: Start of recursive call 7: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:33,685 INFO L267 ElimStorePlain]: Start of recursive call 6: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:33,715 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:33,715 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:33,722 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 78 treesize of output 87 [2018-01-23 14:58:33,724 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-01-23 14:58:33,724 INFO L267 ElimStorePlain]: Start of recursive call 9: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:33,736 INFO L267 ElimStorePlain]: Start of recursive call 8: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:33,763 INFO L267 ElimStorePlain]: Start of recursive call 1: 4 dim-0 vars, 4 dim-2 vars, End of recursive call: 4 dim-0 vars, and 2 xjuncts. [2018-01-23 14:58:33,763 INFO L202 ElimStorePlain]: Needed 9 recursive calls to eliminate 8 variables, input treesize:181, output treesize:145 [2018-01-23 14:58:33,856 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:33,857 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:33,866 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 4 new quantified variables, introduced 0 case distinctions, treesize of input 102 treesize of output 91 [2018-01-23 14:58:33,873 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 35 treesize of output 27 [2018-01-23 14:58:33,874 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-23 14:58:33,913 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 25 treesize of output 20 [2018-01-23 14:58:33,914 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:33,932 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 1 [2018-01-23 14:58:33,933 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:33,945 INFO L267 ElimStorePlain]: Start of recursive call 2: 3 dim-1 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-23 14:58:33,970 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 3 new quantified variables, introduced 0 case distinctions, treesize of input 57 treesize of output 45 [2018-01-23 14:58:33,973 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 13 treesize of output 12 [2018-01-23 14:58:33,973 INFO L267 ElimStorePlain]: Start of recursive call 7: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:33,980 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 4 [2018-01-23 14:58:33,980 INFO L267 ElimStorePlain]: Start of recursive call 8: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:33,985 INFO L267 ElimStorePlain]: Start of recursive call 6: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:34,003 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:34,004 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:34,004 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:34,005 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:34,006 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 5 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 94 treesize of output 90 [2018-01-23 14:58:34,012 INFO L477 Elim1Store]: Elim1 applied some 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 2 new quantified variables, introduced 1 case distinctions, treesize of input 38 treesize of output 37 [2018-01-23 14:58:34,013 INFO L267 ElimStorePlain]: Start of recursive call 10: 1 dim-0 vars, End of recursive call: 1 dim-0 vars, and 2 xjuncts. [2018-01-23 14:58:34,031 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 28 treesize of output 20 [2018-01-23 14:58:34,031 INFO L267 ElimStorePlain]: Start of recursive call 11: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:34,042 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 1 [2018-01-23 14:58:34,042 INFO L267 ElimStorePlain]: Start of recursive call 12: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:34,050 INFO L267 ElimStorePlain]: Start of recursive call 9: 3 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:34,067 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 4 new quantified variables, introduced 0 case distinctions, treesize of input 58 treesize of output 45 [2018-01-23 14:58:34,069 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 13 treesize of output 9 [2018-01-23 14:58:34,069 INFO L267 ElimStorePlain]: Start of recursive call 14: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:34,076 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 4 [2018-01-23 14:58:34,076 INFO L267 ElimStorePlain]: Start of recursive call 15: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:34,079 INFO L267 ElimStorePlain]: Start of recursive call 13: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:34,088 INFO L267 ElimStorePlain]: Start of recursive call 1: 4 dim-0 vars, 4 dim-2 vars, End of recursive call: and 2 xjuncts. [2018-01-23 14:58:34,088 INFO L202 ElimStorePlain]: Needed 15 recursive calls to eliminate 8 variables, input treesize:197, output treesize:9 [2018-01-23 14:58:34,163 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 0 proven. 8 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2018-01-23 14:58:34,183 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-23 14:58:34,183 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 21] total 36 [2018-01-23 14:58:34,184 INFO L409 AbstractCegarLoop]: Interpolant automaton has 36 states [2018-01-23 14:58:34,184 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 36 interpolants. [2018-01-23 14:58:34,184 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=109, Invalid=1150, Unknown=1, NotChecked=0, Total=1260 [2018-01-23 14:58:34,184 INFO L87 Difference]: Start difference. First operand 527 states and 582 transitions. Second operand 36 states. [2018-01-23 14:58:36,416 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-23 14:58:36,416 INFO L93 Difference]: Finished difference Result 885 states and 975 transitions. [2018-01-23 14:58:36,417 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2018-01-23 14:58:36,417 INFO L78 Accepts]: Start accepts. Automaton has 36 states. Word has length 113 [2018-01-23 14:58:36,417 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-23 14:58:36,419 INFO L225 Difference]: With dead ends: 885 [2018-01-23 14:58:36,419 INFO L226 Difference]: Without dead ends: 771 [2018-01-23 14:58:36,420 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 156 GetRequests, 94 SyntacticMatches, 3 SemanticMatches, 59 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 713 ImplicationChecksByTransitivity, 2.6s TimeCoverageRelationStatistics Valid=498, Invalid=3161, Unknown=1, NotChecked=0, Total=3660 [2018-01-23 14:58:36,420 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 771 states. [2018-01-23 14:58:36,464 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 771 to 551. [2018-01-23 14:58:36,464 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 551 states. [2018-01-23 14:58:36,465 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 551 states to 551 states and 609 transitions. [2018-01-23 14:58:36,465 INFO L78 Accepts]: Start accepts. Automaton has 551 states and 609 transitions. Word has length 113 [2018-01-23 14:58:36,466 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-23 14:58:36,466 INFO L432 AbstractCegarLoop]: Abstraction has 551 states and 609 transitions. [2018-01-23 14:58:36,466 INFO L433 AbstractCegarLoop]: Interpolant automaton has 36 states. [2018-01-23 14:58:36,466 INFO L276 IsEmpty]: Start isEmpty. Operand 551 states and 609 transitions. [2018-01-23 14:58:36,467 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 114 [2018-01-23 14:58:36,467 INFO L314 BasicCegarLoop]: Found error trace [2018-01-23 14:58:36,467 INFO L322 BasicCegarLoop]: trace histogram [3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-23 14:58:36,467 INFO L371 AbstractCegarLoop]: === Iteration 19 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-23 14:58:36,467 INFO L82 PathProgramCache]: Analyzing trace with hash -1960338665, now seen corresponding path program 1 times [2018-01-23 14:58:36,467 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-23 14:58:36,467 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-23 14:58:36,468 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:58:36,468 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-01-23 14:58:36,468 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-23 14:58:36,478 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:58:36,479 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-23 14:58:38,588 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 0 proven. 17 refuted. 0 times theorem prover too weak. 17 trivial. 0 not checked. [2018-01-23 14:58:38,588 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-23 14:58:38,613 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-23 14:58:38,618 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-23 14:58:38,648 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-23 14:58:38,652 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-23 14:58:38,654 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-23 14:58:38,654 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:38,657 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:38,657 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:10, output treesize:9 [2018-01-23 14:58:38,817 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:38,817 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:38,818 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 4 [2018-01-23 14:58:38,818 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:38,823 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:38,824 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:23, output treesize:17 [2018-01-23 14:58:38,888 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 8 [2018-01-23 14:58:38,890 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-01-23 14:58:38,890 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:38,891 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:38,899 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 8 [2018-01-23 14:58:38,901 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-01-23 14:58:38,901 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:38,902 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:38,908 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 2 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:38,908 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 3 variables, input treesize:36, output treesize:25 [2018-01-23 14:58:39,120 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:39,124 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-23 14:58:39,126 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-01-23 14:58:39,126 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:39,130 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:39,141 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 19 treesize of output 24 [2018-01-23 14:58:39,144 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 11 [2018-01-23 14:58:39,145 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:39,149 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:39,155 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:39,155 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 2 variables, input treesize:48, output treesize:40 [2018-01-23 14:58:39,254 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 50 treesize of output 45 [2018-01-23 14:58:39,257 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:39,271 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 30 treesize of output 18 [2018-01-23 14:58:39,271 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:39,277 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:39,290 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 62 treesize of output 52 [2018-01-23 14:58:39,293 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:39,294 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 30 treesize of output 18 [2018-01-23 14:58:39,294 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:39,299 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:39,305 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 2 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-23 14:58:39,305 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 3 variables, input treesize:103, output treesize:41 [2018-01-23 14:58:39,511 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 26 treesize of output 24 [2018-01-23 14:58:39,513 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2018-01-23 14:58:39,513 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:39,518 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 1 [2018-01-23 14:58:39,518 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:39,519 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:39,524 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-23 14:58:39,524 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 2 variables, input treesize:55, output treesize:33 [2018-01-23 14:58:39,907 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 2 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 6 case distinctions, treesize of input 46 treesize of output 67 [2018-01-23 14:58:39,911 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 47 treesize of output 31 [2018-01-23 14:58:39,911 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:39,956 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 2 case distinctions, treesize of input 36 treesize of output 28 [2018-01-23 14:58:39,957 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 2 xjuncts. [2018-01-23 14:58:39,988 INFO L267 ElimStorePlain]: Start of recursive call 2: 4 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-23 14:58:40,002 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 2 xjuncts. [2018-01-23 14:58:40,002 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 2 variables, input treesize:59, output treesize:65 [2018-01-23 14:58:40,156 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:40,175 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 2 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 6 case distinctions, treesize of input 44 treesize of output 73 [2018-01-23 14:58:40,179 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 53 treesize of output 52 [2018-01-23 14:58:40,179 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:40,316 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 38 treesize of output 32 [2018-01-23 14:58:40,316 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:40,336 INFO L267 ElimStorePlain]: Start of recursive call 2: 4 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-23 14:58:40,367 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:40,368 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 36 treesize of output 42 [2018-01-23 14:58:40,369 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 16 [2018-01-23 14:58:40,369 INFO L267 ElimStorePlain]: Start of recursive call 6: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:40,377 INFO L267 ElimStorePlain]: Start of recursive call 5: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-23 14:58:40,402 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 2 dim-2 vars, End of recursive call: 2 dim-0 vars, and 3 xjuncts. [2018-01-23 14:58:40,403 INFO L202 ElimStorePlain]: Needed 6 recursive calls to eliminate 3 variables, input treesize:81, output treesize:97 [2018-01-23 14:58:40,517 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:40,518 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 37 treesize of output 41 [2018-01-23 14:58:40,525 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 2 case distinctions, treesize of input 23 treesize of output 30 [2018-01-23 14:58:40,526 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-23 14:58:40,543 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-23 14:58:40,577 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:40,587 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 3 new quantified variables, introduced 4 case distinctions, treesize of input 53 treesize of output 65 [2018-01-23 14:58:40,595 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 2 case distinctions, treesize of input 57 treesize of output 69 [2018-01-23 14:58:40,596 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 2 xjuncts. [2018-01-23 14:58:40,642 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 2 case distinctions, treesize of input 45 treesize of output 49 [2018-01-23 14:58:40,643 INFO L267 ElimStorePlain]: Start of recursive call 6: End of recursive call: and 2 xjuncts. [2018-01-23 14:58:40,673 INFO L267 ElimStorePlain]: Start of recursive call 4: 2 dim-1 vars, End of recursive call: and 4 xjuncts. [2018-01-23 14:58:40,718 INFO L267 ElimStorePlain]: Start of recursive call 1: 4 dim-0 vars, 2 dim-2 vars, End of recursive call: 5 dim-0 vars, and 6 xjuncts. [2018-01-23 14:58:40,718 INFO L202 ElimStorePlain]: Needed 6 recursive calls to eliminate 6 variables, input treesize:91, output treesize:206 [2018-01-23 14:58:41,556 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 43 treesize of output 30 [2018-01-23 14:58:41,560 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-23 14:58:41,561 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-23 14:58:41,566 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 9 [2018-01-23 14:58:41,566 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:41,567 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 13 [2018-01-23 14:58:41,567 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:41,570 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-23 14:58:41,582 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:41,582 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:41,583 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:41,584 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:41,584 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:41,585 INFO L700 Elim1Store]: detected not equals via solver [2018-01-23 14:58:41,585 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 8 disjoint index pairs (out of 3 index pairs), introduced 5 new quantified variables, introduced 0 case distinctions, treesize of input 47 treesize of output 65 [2018-01-23 14:58:41,608 INFO L477 Elim1Store]: Elim1 applied some preprocessing eliminated variable of array dimension 1, 0 stores, 4 select indices, 4 select index equivalence classes, 5 disjoint index pairs (out of 6 index pairs), introduced 5 new quantified variables, introduced 6 case distinctions, treesize of input 34 treesize of output 75 [2018-01-23 14:58:41,609 WARN L130 XnfTransformerHelper]: expecting exponential blowup for input size 6 [2018-01-23 14:58:41,630 INFO L267 ElimStorePlain]: Start of recursive call 7: 94 dim-0 vars, End of recursive call: 94 dim-0 vars, and 54 xjuncts. [2018-01-23 14:58:41,776 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 1 [2018-01-23 14:58:41,776 INFO L267 ElimStorePlain]: Start of recursive call 8: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:41,785 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 3 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 27 treesize of output 21 [2018-01-23 14:58:41,785 INFO L267 ElimStorePlain]: Start of recursive call 9: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:41,786 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 13 [2018-01-23 14:58:41,786 INFO L267 ElimStorePlain]: Start of recursive call 10: End of recursive call: and 1 xjuncts. [2018-01-23 14:58:41,790 INFO L267 ElimStorePlain]: Start of recursive call 6: 3 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-23 14:58:41,803 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 3 dim-2 vars, End of recursive call: and 2 xjuncts. [2018-01-23 14:58:41,803 INFO L202 ElimStorePlain]: Needed 10 recursive calls to eliminate 6 variables, input treesize:130, output treesize:9 [2018-01-23 14:58:42,105 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 0 proven. 17 refuted. 0 times theorem prover too weak. 17 trivial. 0 not checked. [2018-01-23 14:58:42,125 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-23 14:58:42,125 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [27, 29] total 54 [2018-01-23 14:58:42,125 INFO L409 AbstractCegarLoop]: Interpolant automaton has 54 states [2018-01-23 14:58:42,126 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 54 interpolants. [2018-01-23 14:58:42,126 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=211, Invalid=2651, Unknown=0, NotChecked=0, Total=2862 [2018-01-23 14:58:42,126 INFO L87 Difference]: Start difference. First operand 551 states and 609 transitions. Second operand 54 states. [2018-01-23 14:58:43,119 WARN L146 SmtUtils]: Spent 169ms on a formula simplification. DAG size of input: 127 DAG size of output 80 [2018-01-23 14:58:43,428 WARN L146 SmtUtils]: Spent 197ms on a formula simplification. DAG size of input: 140 DAG size of output 84 [2018-01-23 14:58:43,708 WARN L146 SmtUtils]: Spent 161ms on a formula simplification. DAG size of input: 98 DAG size of output 82 [2018-01-23 14:58:44,012 WARN L146 SmtUtils]: Spent 162ms on a formula simplification. DAG size of input: 97 DAG size of output 82 [2018-01-23 14:58:44,488 WARN L146 SmtUtils]: Spent 133ms on a formula simplification. DAG size of input: 102 DAG size of output 77 [2018-01-23 14:58:45,180 WARN L146 SmtUtils]: Spent 145ms on a formula simplification. DAG size of input: 117 DAG size of output 79 [2018-01-23 14:58:45,456 WARN L146 SmtUtils]: Spent 127ms on a formula simplification. DAG size of input: 76 DAG size of output 75 Received shutdown request... [2018-01-23 14:58:45,691 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2018-01-23 14:58:45,691 WARN L491 AbstractCegarLoop]: Verification canceled [2018-01-23 14:58:45,695 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-23 14:58:45,695 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-23 14:58:45,695 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-23 14:58:45,695 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-23 14:58:45,695 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-23 14:58:45,695 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-23 14:58:45,696 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-23 14:58:45,696 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == mainErr0EnsuresViolation======== [2018-01-23 14:58:45,696 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-23 14:58:45,697 INFO L276 IsEmpty]: Start isEmpty. Operand 109 states. [2018-01-23 14:58:45,698 WARN L491 AbstractCegarLoop]: Verification canceled [2018-01-23 14:58:45,699 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 23.01 02:58:45 BoogieIcfgContainer [2018-01-23 14:58:45,699 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-01-23 14:58:45,700 INFO L168 Benchmark]: Toolchain (without parser) took 49988.34 ms. Allocated memory was 306.2 MB in the beginning and 836.2 MB in the end (delta: 530.1 MB). Free memory was 264.5 MB in the beginning and 565.1 MB in the end (delta: -300.6 MB). Peak memory consumption was 229.4 MB. Max. memory is 5.3 GB. [2018-01-23 14:58:45,702 INFO L168 Benchmark]: CDTParser took 0.17 ms. Allocated memory is still 306.2 MB. Free memory is still 270.5 MB. There was no memory consumed. Max. memory is 5.3 GB. [2018-01-23 14:58:45,702 INFO L168 Benchmark]: CACSL2BoogieTranslator took 230.60 ms. Allocated memory is still 306.2 MB. Free memory was 263.5 MB in the beginning and 251.5 MB in the end (delta: 12.0 MB). Peak memory consumption was 12.0 MB. Max. memory is 5.3 GB. [2018-01-23 14:58:45,702 INFO L168 Benchmark]: Boogie Preprocessor took 42.74 ms. Allocated memory is still 306.2 MB. Free memory was 251.5 MB in the beginning and 249.5 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 5.3 GB. [2018-01-23 14:58:45,703 INFO L168 Benchmark]: RCFGBuilder took 467.59 ms. Allocated memory is still 306.2 MB. Free memory was 249.5 MB in the beginning and 218.6 MB in the end (delta: 30.9 MB). Peak memory consumption was 30.9 MB. Max. memory is 5.3 GB. [2018-01-23 14:58:45,703 INFO L168 Benchmark]: TraceAbstraction took 49239.86 ms. Allocated memory was 306.2 MB in the beginning and 836.2 MB in the end (delta: 530.1 MB). Free memory was 218.6 MB in the beginning and 565.1 MB in the end (delta: -346.5 MB). Peak memory consumption was 183.5 MB. Max. memory is 5.3 GB. [2018-01-23 14:58:45,705 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.17 ms. Allocated memory is still 306.2 MB. Free memory is still 270.5 MB. There was no memory consumed. Max. memory is 5.3 GB. * CACSL2BoogieTranslator took 230.60 ms. Allocated memory is still 306.2 MB. Free memory was 263.5 MB in the beginning and 251.5 MB in the end (delta: 12.0 MB). Peak memory consumption was 12.0 MB. Max. memory is 5.3 GB. * Boogie Preprocessor took 42.74 ms. Allocated memory is still 306.2 MB. Free memory was 251.5 MB in the beginning and 249.5 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 5.3 GB. * RCFGBuilder took 467.59 ms. Allocated memory is still 306.2 MB. Free memory was 249.5 MB in the beginning and 218.6 MB in the end (delta: 30.9 MB). Peak memory consumption was 30.9 MB. Max. memory is 5.3 GB. * TraceAbstraction took 49239.86 ms. Allocated memory was 306.2 MB in the beginning and 836.2 MB in the end (delta: 530.1 MB). Free memory was 218.6 MB in the beginning and 565.1 MB in the end (delta: -346.5 MB). Peak memory consumption was 183.5 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) * 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, 109 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=109occurred 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 - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that all allocated memory was freed (line 1). Cancelled while BasicCegarLoop was constructing difference of abstraction (551states) and interpolant automaton (currently 19 states, 54 states before enhancement), while ReachableStatesComputation was computing reachable states (80 states constructedinput type IntersectNwa). - StatisticsResult: Ultimate Automizer benchmark data for error location: ULTIMATE.startErr0EnsuresViolation CFG has 3 procedures, 109 locations, 3 error locations. TIMEOUT Result, 49.0s OverallTime, 19 OverallIterations, 4 TraceHistogramMax, 27.0s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 1838 SDtfs, 13997 SDslu, 16402 SDs, 0 SdLazy, 13041 SolverSat, 1658 SolverUnsat, 210 SolverUnknown, 0 SolverNotchecked, 8.7s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 1751 GetRequests, 1106 SyntacticMatches, 27 SemanticMatches, 618 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 8664 ImplicationChecksByTransitivity, 27.8s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=551occurred in iteration=18, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s AbstIntTime, 0 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, AutomataMinimizationStatistics: 0.5s AutomataMinimizationTime, 18 MinimizatonAttempts, 2578 StatesRemovedByMinimization, 16 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.1s SsaConstructionTime, 0.7s SatisfiabilityAnalysisTime, 19.5s InterpolantComputationTime, 2902 NumberOfCodeBlocks, 2861 NumberOfCodeBlocksAsserted, 35 NumberOfCheckSat, 2871 ConstructedInterpolants, 230 QuantifiedInterpolants, 6371062 SizeOfPredicates, 182 NumberOfNonLiveVariables, 3135 ConjunctsInSsa, 468 ConjunctsInUnsatCore, 31 InterpolantComputations, 7 PerfectInterpolantSequences, 426/637 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, REUSE_STATISTICS: No data available - TimeoutResultAtElement [Line: 982]: Timeout (TraceAbstraction) Unable to prove that all allocated memory was freed (line 982). Cancelled while IsEmpty was searching accepting run (input had 109 states). - StatisticsResult: Ultimate Automizer benchmark data for error location: mainErr0EnsuresViolation CFG has 3 procedures, 109 locations, 3 error locations. TIMEOUT Result, 0.0s OverallTime, 0 OverallIterations, 0 TraceHistogramMax, 0.0s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: No data available, PredicateUnifierStatistics: No data available, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=109occurred 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: 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/sll-sorted_true-unreach-call_true-valid-memsafety.i_mempurity-32bit-Automizer_Camel+AI_EQ.epf_AutomizerC.xml/Csv-Benchmark-0-2018-01-23_14-58-45-712.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/sll-sorted_true-unreach-call_true-valid-memsafety.i_mempurity-32bit-Automizer_Camel+AI_EQ.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-0-2018-01-23_14-58-45-712.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/sll-sorted_true-unreach-call_true-valid-memsafety.i_mempurity-32bit-Automizer_Camel+AI_EQ.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-1-2018-01-23_14-58-45-712.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/sll-sorted_true-unreach-call_true-valid-memsafety.i_mempurity-32bit-Automizer_Camel+AI_EQ.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-2-2018-01-23_14-58-45-712.csv Completed graceful shutdown