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/svcomp-DerefFreeMemtrack-32bit-Automizer_Taipan+AI_EQ_smtcomp.epf -i ../../../trunk/examples/svcomp/array-memsafety/cstrncat-alloca_true-valid-memsafety_true-termination.i -------------------------------------------------------------------------------- This is Ultimate 0.1.23-6b94a2f [2018-01-25 05:21:57,162 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-01-25 05:21:57,164 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-01-25 05:21:57,176 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-01-25 05:21:57,176 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-01-25 05:21:57,177 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-01-25 05:21:57,179 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-01-25 05:21:57,180 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-01-25 05:21:57,183 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-01-25 05:21:57,183 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-01-25 05:21:57,184 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-01-25 05:21:57,185 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-01-25 05:21:57,186 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-01-25 05:21:57,187 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-01-25 05:21:57,188 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-01-25 05:21:57,191 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-01-25 05:21:57,193 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-01-25 05:21:57,195 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-01-25 05:21:57,196 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-01-25 05:21:57,197 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-01-25 05:21:57,199 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-01-25 05:21:57,200 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-01-25 05:21:57,200 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-01-25 05:21:57,201 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-01-25 05:21:57,202 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-01-25 05:21:57,203 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-01-25 05:21:57,203 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-01-25 05:21:57,204 INFO L177 SettingsManager]: PEA to Boogie provides no preferences, ignoring... [2018-01-25 05:21:57,204 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-01-25 05:21:57,204 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-01-25 05:21:57,205 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-01-25 05:21:57,205 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/ai/eq-bench/svcomp-DerefFreeMemtrack-32bit-Automizer_Taipan+AI_EQ_smtcomp.epf [2018-01-25 05:21:57,215 INFO L110 SettingsManager]: Loading preferences was successful [2018-01-25 05:21:57,215 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-01-25 05:21:57,216 INFO L131 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2018-01-25 05:21:57,216 INFO L133 SettingsManager]: * to procedures, called more than once=true [2018-01-25 05:21:57,217 INFO L131 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2018-01-25 05:21:57,217 INFO L133 SettingsManager]: * Abstract domain for RCFG-of-the-future=VPDomain [2018-01-25 05:21:57,217 INFO L133 SettingsManager]: * Precise comparison operator=true [2018-01-25 05:21:57,217 INFO L133 SettingsManager]: * Use the RCFG-of-the-future interface=true [2018-01-25 05:21:57,218 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-01-25 05:21:57,218 INFO L133 SettingsManager]: * sizeof long=4 [2018-01-25 05:21:57,218 INFO L133 SettingsManager]: * Check unreachability of error function in SV-COMP mode=false [2018-01-25 05:21:57,218 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-01-25 05:21:57,219 INFO L133 SettingsManager]: * sizeof POINTER=4 [2018-01-25 05:21:57,219 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-01-25 05:21:57,219 INFO L133 SettingsManager]: * Check for the main procedure if all allocated memory was freed=true [2018-01-25 05:21:57,219 INFO L133 SettingsManager]: * Bitprecise bitfields=true [2018-01-25 05:21:57,219 INFO L133 SettingsManager]: * SV-COMP memtrack compatibility mode=true [2018-01-25 05:21:57,220 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-01-25 05:21:57,220 INFO L133 SettingsManager]: * sizeof long double=12 [2018-01-25 05:21:57,220 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-01-25 05:21:57,220 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-01-25 05:21:57,220 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-01-25 05:21:57,221 INFO L133 SettingsManager]: * Add additional assume for each assert=false [2018-01-25 05:21:57,221 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-01-25 05:21:57,221 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-01-25 05:21:57,221 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-01-25 05:21:57,221 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-01-25 05:21:57,222 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-01-25 05:21:57,222 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-01-25 05:21:57,222 INFO L133 SettingsManager]: * Trace refinement strategy=TAIPAN [2018-01-25 05:21:57,222 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-01-25 05:21:57,222 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-01-25 05:21:57,223 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-01-25 05:21:57,223 INFO L133 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES [2018-01-25 05:21:57,224 INFO L131 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2018-01-25 05:21:57,224 INFO L133 SettingsManager]: * TransformationType=HEAP_SEPARATOR [2018-01-25 05:21:57,258 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-01-25 05:21:57,271 INFO L266 ainManager$Toolchain]: [Toolchain 1]: Parser(s) successfully initialized [2018-01-25 05:21:57,276 INFO L222 ainManager$Toolchain]: [Toolchain 1]: Toolchain data selected. [2018-01-25 05:21:57,277 INFO L271 PluginConnector]: Initializing CDTParser... [2018-01-25 05:21:57,278 INFO L276 PluginConnector]: CDTParser initialized [2018-01-25 05:21:57,278 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/array-memsafety/cstrncat-alloca_true-valid-memsafety_true-termination.i [2018-01-25 05:21:57,478 INFO L304 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-01-25 05:21:57,484 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2018-01-25 05:21:57,484 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2018-01-25 05:21:57,485 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2018-01-25 05:21:57,490 INFO L276 PluginConnector]: CACSL2BoogieTranslator initialized [2018-01-25 05:21:57,492 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 25.01 05:21:57" (1/1) ... [2018-01-25 05:21:57,496 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@f7faa1c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.01 05:21:57, skipping insertion in model container [2018-01-25 05:21:57,496 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 25.01 05:21:57" (1/1) ... [2018-01-25 05:21:57,511 INFO L153 Dispatcher]: Using SV-COMP mode [2018-01-25 05:21:57,550 INFO L153 Dispatcher]: Using SV-COMP mode [2018-01-25 05:21:57,665 INFO L450 PostProcessor]: Settings: Checked method=main [2018-01-25 05:21:57,682 INFO L450 PostProcessor]: Settings: Checked method=main [2018-01-25 05:21:57,688 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.01 05:21:57 WrapperNode [2018-01-25 05:21:57,689 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2018-01-25 05:21:57,689 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-01-25 05:21:57,689 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-01-25 05:21:57,689 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-01-25 05:21:57,703 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.01 05:21:57" (1/1) ... [2018-01-25 05:21:57,703 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.01 05:21:57" (1/1) ... [2018-01-25 05:21:57,714 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.01 05:21:57" (1/1) ... [2018-01-25 05:21:57,714 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.01 05:21:57" (1/1) ... [2018-01-25 05:21:57,718 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.01 05:21:57" (1/1) ... [2018-01-25 05:21:57,721 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.01 05:21:57" (1/1) ... [2018-01-25 05:21:57,722 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.01 05:21:57" (1/1) ... [2018-01-25 05:21:57,723 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-01-25 05:21:57,723 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-01-25 05:21:57,724 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-01-25 05:21:57,724 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-01-25 05:21:57,724 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.01 05:21:57" (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-25 05:21:57,768 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2018-01-25 05:21:57,768 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-01-25 05:21:57,769 INFO L136 BoogieDeclarations]: Found implementation of procedure cstrncat [2018-01-25 05:21:57,769 INFO L136 BoogieDeclarations]: Found implementation of procedure main [2018-01-25 05:21:57,769 INFO L128 BoogieDeclarations]: Found specification of procedure write~int [2018-01-25 05:21:57,769 INFO L128 BoogieDeclarations]: Found specification of procedure read~int [2018-01-25 05:21:57,769 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.free [2018-01-25 05:21:57,769 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2018-01-25 05:21:57,769 INFO L128 BoogieDeclarations]: Found specification of procedure #Ultimate.alloc [2018-01-25 05:21:57,769 INFO L128 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2018-01-25 05:21:57,769 INFO L128 BoogieDeclarations]: Found specification of procedure cstrncat [2018-01-25 05:21:57,769 INFO L128 BoogieDeclarations]: Found specification of procedure main [2018-01-25 05:21:57,770 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2018-01-25 05:21:57,770 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-01-25 05:21:58,036 INFO L257 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-01-25 05:21:58,037 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.01 05:21:58 BoogieIcfgContainer [2018-01-25 05:21:58,037 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-01-25 05:21:58,038 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-01-25 05:21:58,038 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-01-25 05:21:58,039 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-01-25 05:21:58,040 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 25.01 05:21:57" (1/3) ... [2018-01-25 05:21:58,040 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@588a999d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 25.01 05:21:58, skipping insertion in model container [2018-01-25 05:21:58,041 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.01 05:21:57" (2/3) ... [2018-01-25 05:21:58,041 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@588a999d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 25.01 05:21:58, skipping insertion in model container [2018-01-25 05:21:58,041 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.01 05:21:58" (3/3) ... [2018-01-25 05:21:58,043 INFO L105 eAbstractionObserver]: Analyzing ICFG cstrncat-alloca_true-valid-memsafety_true-termination.i [2018-01-25 05:21:58,049 INFO L130 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-01-25 05:21:58,055 INFO L142 ceAbstractionStarter]: Appying trace abstraction to program that has 15 error locations. [2018-01-25 05:21:58,100 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-25 05:21:58,101 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-25 05:21:58,101 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-25 05:21:58,101 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-25 05:21:58,101 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-25 05:21:58,101 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-25 05:21:58,101 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-25 05:21:58,101 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-01-25 05:21:58,102 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-25 05:21:58,120 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states. [2018-01-25 05:21:58,125 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2018-01-25 05:21:58,125 INFO L314 BasicCegarLoop]: Found error trace [2018-01-25 05:21:58,126 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-25 05:21:58,126 INFO L371 AbstractCegarLoop]: === Iteration 1 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-25 05:21:58,131 INFO L82 PathProgramCache]: Analyzing trace with hash 1927484354, now seen corresponding path program 1 times [2018-01-25 05:21:58,133 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-25 05:21:58,175 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-25 05:21:58,176 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-25 05:21:58,176 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-25 05:21:58,176 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-25 05:21:58,230 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-25 05:21:58,240 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-25 05:21:58,297 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-25 05:21:58,299 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-25 05:21:58,299 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-01-25 05:21:58,300 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-25 05:21:58,303 INFO L409 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-01-25 05:21:58,318 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-01-25 05:21:58,319 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-25 05:21:58,322 INFO L87 Difference]: Start difference. First operand 58 states. Second operand 3 states. [2018-01-25 05:21:58,547 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-25 05:21:58,548 INFO L93 Difference]: Finished difference Result 90 states and 103 transitions. [2018-01-25 05:21:58,548 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-01-25 05:21:58,549 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 11 [2018-01-25 05:21:58,550 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-25 05:21:58,559 INFO L225 Difference]: With dead ends: 90 [2018-01-25 05:21:58,559 INFO L226 Difference]: Without dead ends: 55 [2018-01-25 05:21:58,563 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-25 05:21:58,577 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2018-01-25 05:21:58,593 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 55. [2018-01-25 05:21:58,594 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 55 states. [2018-01-25 05:21:58,595 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 61 transitions. [2018-01-25 05:21:58,597 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 61 transitions. Word has length 11 [2018-01-25 05:21:58,597 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-25 05:21:58,597 INFO L432 AbstractCegarLoop]: Abstraction has 55 states and 61 transitions. [2018-01-25 05:21:58,597 INFO L433 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-01-25 05:21:58,598 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 61 transitions. [2018-01-25 05:21:58,598 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2018-01-25 05:21:58,598 INFO L314 BasicCegarLoop]: Found error trace [2018-01-25 05:21:58,598 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-25 05:21:58,599 INFO L371 AbstractCegarLoop]: === Iteration 2 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-25 05:21:58,599 INFO L82 PathProgramCache]: Analyzing trace with hash 1621249811, now seen corresponding path program 1 times [2018-01-25 05:21:58,599 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-25 05:21:58,600 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-25 05:21:58,600 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-25 05:21:58,600 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-25 05:21:58,601 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-25 05:21:58,614 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-25 05:21:58,616 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-25 05:21:58,685 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-25 05:21:58,685 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-25 05:21:58,686 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-01-25 05:21:58,686 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-25 05:21:58,687 INFO L409 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-01-25 05:21:58,688 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-01-25 05:21:58,688 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-01-25 05:21:58,688 INFO L87 Difference]: Start difference. First operand 55 states and 61 transitions. Second operand 5 states. [2018-01-25 05:21:58,780 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-25 05:21:58,780 INFO L93 Difference]: Finished difference Result 103 states and 114 transitions. [2018-01-25 05:21:58,781 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-01-25 05:21:58,781 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 15 [2018-01-25 05:21:58,781 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-25 05:21:58,783 INFO L225 Difference]: With dead ends: 103 [2018-01-25 05:21:58,783 INFO L226 Difference]: Without dead ends: 55 [2018-01-25 05:21:58,784 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-25 05:21:58,785 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2018-01-25 05:21:58,790 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 55. [2018-01-25 05:21:58,790 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 55 states. [2018-01-25 05:21:58,792 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 60 transitions. [2018-01-25 05:21:58,792 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 60 transitions. Word has length 15 [2018-01-25 05:21:58,793 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-25 05:21:58,793 INFO L432 AbstractCegarLoop]: Abstraction has 55 states and 60 transitions. [2018-01-25 05:21:58,793 INFO L433 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-01-25 05:21:58,793 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 60 transitions. [2018-01-25 05:21:58,794 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2018-01-25 05:21:58,794 INFO L314 BasicCegarLoop]: Found error trace [2018-01-25 05:21:58,794 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-25 05:21:58,794 INFO L371 AbstractCegarLoop]: === Iteration 3 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-25 05:21:58,795 INFO L82 PathProgramCache]: Analyzing trace with hash -1993659115, now seen corresponding path program 1 times [2018-01-25 05:21:58,795 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-25 05:21:58,796 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-25 05:21:58,796 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-25 05:21:58,796 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-25 05:21:58,796 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-25 05:21:58,819 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-25 05:21:58,820 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-25 05:21:58,900 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-25 05:21:58,901 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-25 05:21:58,901 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-01-25 05:21:58,901 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-25 05:21:58,901 INFO L409 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-01-25 05:21:58,902 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-01-25 05:21:58,902 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-01-25 05:21:58,902 INFO L87 Difference]: Start difference. First operand 55 states and 60 transitions. Second operand 4 states. [2018-01-25 05:21:59,050 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-25 05:21:59,050 INFO L93 Difference]: Finished difference Result 55 states and 60 transitions. [2018-01-25 05:21:59,050 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-01-25 05:21:59,050 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 15 [2018-01-25 05:21:59,051 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-25 05:21:59,052 INFO L225 Difference]: With dead ends: 55 [2018-01-25 05:21:59,052 INFO L226 Difference]: Without dead ends: 54 [2018-01-25 05:21:59,052 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-01-25 05:21:59,052 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2018-01-25 05:21:59,057 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 54. [2018-01-25 05:21:59,058 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 54 states. [2018-01-25 05:21:59,059 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 59 transitions. [2018-01-25 05:21:59,059 INFO L78 Accepts]: Start accepts. Automaton has 54 states and 59 transitions. Word has length 15 [2018-01-25 05:21:59,059 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-25 05:21:59,060 INFO L432 AbstractCegarLoop]: Abstraction has 54 states and 59 transitions. [2018-01-25 05:21:59,060 INFO L433 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-01-25 05:21:59,060 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states and 59 transitions. [2018-01-25 05:21:59,060 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2018-01-25 05:21:59,060 INFO L314 BasicCegarLoop]: Found error trace [2018-01-25 05:21:59,061 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-25 05:21:59,061 INFO L371 AbstractCegarLoop]: === Iteration 4 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-25 05:21:59,061 INFO L82 PathProgramCache]: Analyzing trace with hash -1993659114, now seen corresponding path program 1 times [2018-01-25 05:21:59,061 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-25 05:21:59,062 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-25 05:21:59,062 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-25 05:21:59,063 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-25 05:21:59,063 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-25 05:21:59,078 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-25 05:21:59,079 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-25 05:21:59,231 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-25 05:21:59,231 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-25 05:21:59,231 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2018-01-25 05:21:59,231 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-25 05:21:59,232 INFO L409 AbstractCegarLoop]: Interpolant automaton has 8 states [2018-01-25 05:21:59,232 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2018-01-25 05:21:59,232 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=38, Unknown=0, NotChecked=0, Total=56 [2018-01-25 05:21:59,233 INFO L87 Difference]: Start difference. First operand 54 states and 59 transitions. Second operand 8 states. [2018-01-25 05:21:59,365 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-25 05:21:59,365 INFO L93 Difference]: Finished difference Result 54 states and 59 transitions. [2018-01-25 05:21:59,366 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-01-25 05:21:59,366 INFO L78 Accepts]: Start accepts. Automaton has 8 states. Word has length 15 [2018-01-25 05:21:59,366 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-25 05:21:59,367 INFO L225 Difference]: With dead ends: 54 [2018-01-25 05:21:59,367 INFO L226 Difference]: Without dead ends: 53 [2018-01-25 05:21:59,368 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=48, Invalid=84, Unknown=0, NotChecked=0, Total=132 [2018-01-25 05:21:59,368 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 53 states. [2018-01-25 05:21:59,373 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 53 to 53. [2018-01-25 05:21:59,373 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 53 states. [2018-01-25 05:21:59,375 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 53 states to 53 states and 58 transitions. [2018-01-25 05:21:59,375 INFO L78 Accepts]: Start accepts. Automaton has 53 states and 58 transitions. Word has length 15 [2018-01-25 05:21:59,375 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-25 05:21:59,376 INFO L432 AbstractCegarLoop]: Abstraction has 53 states and 58 transitions. [2018-01-25 05:21:59,376 INFO L433 AbstractCegarLoop]: Interpolant automaton has 8 states. [2018-01-25 05:21:59,376 INFO L276 IsEmpty]: Start isEmpty. Operand 53 states and 58 transitions. [2018-01-25 05:21:59,376 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2018-01-25 05:21:59,377 INFO L314 BasicCegarLoop]: Found error trace [2018-01-25 05:21:59,377 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-25 05:21:59,377 INFO L371 AbstractCegarLoop]: === Iteration 5 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-25 05:21:59,377 INFO L82 PathProgramCache]: Analyzing trace with hash -1673890416, now seen corresponding path program 1 times [2018-01-25 05:21:59,378 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-25 05:21:59,379 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-25 05:21:59,379 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-25 05:21:59,379 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-25 05:21:59,379 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-25 05:21:59,393 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-25 05:21:59,394 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-25 05:21:59,428 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-25 05:21:59,429 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-25 05:21:59,429 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-01-25 05:21:59,429 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-25 05:21:59,429 INFO L409 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-01-25 05:21:59,430 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-01-25 05:21:59,430 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-01-25 05:21:59,430 INFO L87 Difference]: Start difference. First operand 53 states and 58 transitions. Second operand 4 states. [2018-01-25 05:21:59,480 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-25 05:21:59,481 INFO L93 Difference]: Finished difference Result 53 states and 58 transitions. [2018-01-25 05:21:59,481 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-01-25 05:21:59,481 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 16 [2018-01-25 05:21:59,481 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-25 05:21:59,482 INFO L225 Difference]: With dead ends: 53 [2018-01-25 05:21:59,482 INFO L226 Difference]: Without dead ends: 52 [2018-01-25 05:21:59,482 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-01-25 05:21:59,483 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 52 states. [2018-01-25 05:21:59,488 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 52 to 52. [2018-01-25 05:21:59,488 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 52 states. [2018-01-25 05:21:59,489 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 52 states to 52 states and 57 transitions. [2018-01-25 05:21:59,490 INFO L78 Accepts]: Start accepts. Automaton has 52 states and 57 transitions. Word has length 16 [2018-01-25 05:21:59,490 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-25 05:21:59,490 INFO L432 AbstractCegarLoop]: Abstraction has 52 states and 57 transitions. [2018-01-25 05:21:59,490 INFO L433 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-01-25 05:21:59,490 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 57 transitions. [2018-01-25 05:21:59,491 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2018-01-25 05:21:59,491 INFO L314 BasicCegarLoop]: Found error trace [2018-01-25 05:21:59,491 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-25 05:21:59,491 INFO L371 AbstractCegarLoop]: === Iteration 6 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-25 05:21:59,492 INFO L82 PathProgramCache]: Analyzing trace with hash -1673890415, now seen corresponding path program 1 times [2018-01-25 05:21:59,492 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-25 05:21:59,493 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-25 05:21:59,493 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-25 05:21:59,493 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-25 05:21:59,493 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-25 05:21:59,505 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-25 05:21:59,506 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-25 05:21:59,593 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-25 05:21:59,594 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-25 05:21:59,594 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-01-25 05:21:59,594 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-25 05:21:59,594 INFO L409 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-01-25 05:21:59,594 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-01-25 05:21:59,595 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-01-25 05:21:59,595 INFO L87 Difference]: Start difference. First operand 52 states and 57 transitions. Second operand 5 states. [2018-01-25 05:21:59,621 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-25 05:21:59,621 INFO L93 Difference]: Finished difference Result 52 states and 57 transitions. [2018-01-25 05:21:59,622 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-01-25 05:21:59,622 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 16 [2018-01-25 05:21:59,622 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-25 05:21:59,623 INFO L225 Difference]: With dead ends: 52 [2018-01-25 05:21:59,623 INFO L226 Difference]: Without dead ends: 51 [2018-01-25 05:21:59,623 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=14, Invalid=16, Unknown=0, NotChecked=0, Total=30 [2018-01-25 05:21:59,623 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2018-01-25 05:21:59,627 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 51. [2018-01-25 05:21:59,627 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 51 states. [2018-01-25 05:21:59,628 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 56 transitions. [2018-01-25 05:21:59,628 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 56 transitions. Word has length 16 [2018-01-25 05:21:59,628 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-25 05:21:59,629 INFO L432 AbstractCegarLoop]: Abstraction has 51 states and 56 transitions. [2018-01-25 05:21:59,629 INFO L433 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-01-25 05:21:59,629 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 56 transitions. [2018-01-25 05:21:59,629 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2018-01-25 05:21:59,630 INFO L314 BasicCegarLoop]: Found error trace [2018-01-25 05:21:59,630 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-25 05:21:59,630 INFO L371 AbstractCegarLoop]: === Iteration 7 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-25 05:21:59,630 INFO L82 PathProgramCache]: Analyzing trace with hash 1745382581, now seen corresponding path program 1 times [2018-01-25 05:21:59,630 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-25 05:21:59,631 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-25 05:21:59,631 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-25 05:21:59,631 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-25 05:21:59,631 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-25 05:21:59,644 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-25 05:21:59,645 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-25 05:21:59,682 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-25 05:21:59,682 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-25 05:21:59,682 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-01-25 05:21:59,682 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-25 05:21:59,683 INFO L409 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-01-25 05:21:59,683 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-01-25 05:21:59,683 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-01-25 05:21:59,683 INFO L87 Difference]: Start difference. First operand 51 states and 56 transitions. Second operand 5 states. [2018-01-25 05:21:59,743 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-25 05:21:59,743 INFO L93 Difference]: Finished difference Result 51 states and 56 transitions. [2018-01-25 05:21:59,744 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-01-25 05:21:59,744 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 20 [2018-01-25 05:21:59,744 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-25 05:21:59,745 INFO L225 Difference]: With dead ends: 51 [2018-01-25 05:21:59,745 INFO L226 Difference]: Without dead ends: 47 [2018-01-25 05:21:59,746 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2018-01-25 05:21:59,746 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2018-01-25 05:21:59,750 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 47. [2018-01-25 05:21:59,751 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 47 states. [2018-01-25 05:21:59,752 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 47 states to 47 states and 52 transitions. [2018-01-25 05:21:59,752 INFO L78 Accepts]: Start accepts. Automaton has 47 states and 52 transitions. Word has length 20 [2018-01-25 05:21:59,752 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-25 05:21:59,752 INFO L432 AbstractCegarLoop]: Abstraction has 47 states and 52 transitions. [2018-01-25 05:21:59,753 INFO L433 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-01-25 05:21:59,753 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 52 transitions. [2018-01-25 05:21:59,753 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2018-01-25 05:21:59,754 INFO L314 BasicCegarLoop]: Found error trace [2018-01-25 05:21:59,754 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] [2018-01-25 05:21:59,754 INFO L371 AbstractCegarLoop]: === Iteration 8 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-25 05:21:59,754 INFO L82 PathProgramCache]: Analyzing trace with hash 1745382582, now seen corresponding path program 1 times [2018-01-25 05:21:59,755 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-25 05:21:59,756 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-25 05:21:59,756 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-25 05:21:59,756 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-25 05:21:59,756 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-25 05:21:59,768 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-25 05:21:59,769 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-25 05:21:59,900 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-25 05:21:59,900 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-25 05:21:59,901 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2018-01-25 05:21:59,901 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-25 05:21:59,901 INFO L409 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-01-25 05:21:59,901 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-01-25 05:21:59,902 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2018-01-25 05:21:59,902 INFO L87 Difference]: Start difference. First operand 47 states and 52 transitions. Second operand 9 states. [2018-01-25 05:22:00,078 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-25 05:22:00,078 INFO L93 Difference]: Finished difference Result 69 states and 78 transitions. [2018-01-25 05:22:00,079 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-01-25 05:22:00,079 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 20 [2018-01-25 05:22:00,079 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-25 05:22:00,082 INFO L225 Difference]: With dead ends: 69 [2018-01-25 05:22:00,082 INFO L226 Difference]: Without dead ends: 65 [2018-01-25 05:22:00,083 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 14 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 16 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=57, Invalid=153, Unknown=0, NotChecked=0, Total=210 [2018-01-25 05:22:00,083 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 65 states. [2018-01-25 05:22:00,089 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 65 to 60. [2018-01-25 05:22:00,089 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 60 states. [2018-01-25 05:22:00,090 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 60 states to 60 states and 71 transitions. [2018-01-25 05:22:00,090 INFO L78 Accepts]: Start accepts. Automaton has 60 states and 71 transitions. Word has length 20 [2018-01-25 05:22:00,090 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-25 05:22:00,090 INFO L432 AbstractCegarLoop]: Abstraction has 60 states and 71 transitions. [2018-01-25 05:22:00,091 INFO L433 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-01-25 05:22:00,091 INFO L276 IsEmpty]: Start isEmpty. Operand 60 states and 71 transitions. [2018-01-25 05:22:00,091 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2018-01-25 05:22:00,091 INFO L314 BasicCegarLoop]: Found error trace [2018-01-25 05:22:00,091 INFO L322 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-25 05:22:00,091 INFO L371 AbstractCegarLoop]: === Iteration 9 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-25 05:22:00,092 INFO L82 PathProgramCache]: Analyzing trace with hash 1818413707, now seen corresponding path program 1 times [2018-01-25 05:22:00,092 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-25 05:22:00,092 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-25 05:22:00,092 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-25 05:22:00,093 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-25 05:22:00,093 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-25 05:22:00,104 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-25 05:22:00,105 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-25 05:22:00,282 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-25 05:22:00,283 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-25 05:22:00,283 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-01-25 05:22:00,284 INFO L199 CegarAbsIntRunner]: Running AI on error trace of length 24 with the following transitions: [2018-01-25 05:22:00,286 INFO L201 CegarAbsIntRunner]: [0], [1], [5], [10], [16], [20], [27], [28], [29], [30], [31], [32], [35], [46], [50], [52], [54], [59], [103], [104], [105], [107] [2018-01-25 05:22:00,335 INFO L147 AbstractInterpreter]: Using domain VPDomain [2018-01-25 05:22:00,335 INFO L101 FixpointEngine]: Starting fixpoint engine with domain VPDomain (maxUnwinding=3, maxParallelStates=2) [2018-01-25 05:22:01,354 INFO L259 AbstractInterpreter]: Some error location(s) were reachable [2018-01-25 05:22:01,355 INFO L268 AbstractInterpreter]: Visited 22 different actions 26 times. Merged at 4 different actions 4 times. Never widened. Found 1 fixpoints after 1 different actions. Largest state had 25 variables. [2018-01-25 05:22:01,369 INFO L434 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: Unknown [2018-01-25 05:22:01,369 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-25 05:22:01,369 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG 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-25 05:22:01,394 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-25 05:22:01,394 INFO L280 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-01-25 05:22:01,427 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-25 05:22:01,436 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-25 05:22:01,569 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-25 05:22:01,571 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:01,596 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-25 05:22:01,596 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:01,621 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:22:01,621 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:24, output treesize:19 [2018-01-25 05:22:01,691 INFO L700 Elim1Store]: detected not equals via solver [2018-01-25 05:22:01,700 INFO L700 Elim1Store]: detected not equals via solver [2018-01-25 05:22:01,701 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-25 05:22:01,701 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:01,714 INFO L700 Elim1Store]: detected not equals via solver [2018-01-25 05:22:01,715 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 23 [2018-01-25 05:22:01,716 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:01,727 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:22:01,727 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:30, output treesize:18 [2018-01-25 05:22:01,916 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-25 05:22:01,916 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-01-25 05:22:02,184 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 3 [2018-01-25 05:22:02,184 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:02,187 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 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 15 [2018-01-25 05:22:02,197 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 3 [2018-01-25 05:22:02,197 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:02,198 WARN L307 Elim1Store]: Array PQE input equivalent to true [2018-01-25 05:22:02,198 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:02,200 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:22:02,202 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:22:02,202 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 4 variables, input treesize:21, output treesize:3 [2018-01-25 05:22:02,214 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-25 05:22:02,234 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-25 05:22:02,235 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode CVC4_IG No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 Starting monitored process 3 with cvc4 --tear-down-incremental --print-success --lang smt --rewrite-divk --tlimit-per=12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with cvc4 --tear-down-incremental --print-success --lang smt --rewrite-divk --tlimit-per=12000 [2018-01-25 05:22:02,238 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-25 05:22:02,238 INFO L280 anRefinementStrategy]: Using traceCheck mode CVC4_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-01-25 05:22:02,267 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-25 05:22:02,271 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-25 05:22:02,277 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-25 05:22:02,277 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:02,291 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-25 05:22:02,292 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:02,308 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:22:02,309 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:24, output treesize:19 [2018-01-25 05:22:02,374 INFO L700 Elim1Store]: detected not equals via solver [2018-01-25 05:22:02,375 INFO L700 Elim1Store]: detected not equals via solver [2018-01-25 05:22:02,376 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 23 [2018-01-25 05:22:02,377 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:02,387 INFO L700 Elim1Store]: detected not equals via solver [2018-01-25 05:22:02,387 INFO L700 Elim1Store]: detected not equals via solver [2018-01-25 05:22:02,388 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-25 05:22:02,388 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:02,394 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 2 dim-1 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-25 05:22:02,394 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:30, output treesize:18 [2018-01-25 05:22:02,470 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-25 05:22:02,471 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-01-25 05:22:02,527 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 10 treesize of output 3 [2018-01-25 05:22:02,528 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:02,531 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 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 15 [2018-01-25 05:22:02,539 WARN L307 Elim1Store]: Array PQE input equivalent to true [2018-01-25 05:22:02,539 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:02,541 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 3 [2018-01-25 05:22:02,541 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:02,543 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:22:02,546 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:22:02,546 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 4 variables, input treesize:21, output treesize:3 [2018-01-25 05:22:02,588 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-25 05:22:02,590 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 5 imperfect interpolant sequences. [2018-01-25 05:22:02,590 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 12, 11, 11, 11] total 34 [2018-01-25 05:22:02,590 INFO L247 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-01-25 05:22:02,591 INFO L409 AbstractCegarLoop]: Interpolant automaton has 22 states [2018-01-25 05:22:02,591 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2018-01-25 05:22:02,591 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=137, Invalid=1053, Unknown=0, NotChecked=0, Total=1190 [2018-01-25 05:22:02,591 INFO L87 Difference]: Start difference. First operand 60 states and 71 transitions. Second operand 22 states. [2018-01-25 05:22:03,181 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-25 05:22:03,181 INFO L93 Difference]: Finished difference Result 87 states and 100 transitions. [2018-01-25 05:22:03,181 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-01-25 05:22:03,181 INFO L78 Accepts]: Start accepts. Automaton has 22 states. Word has length 23 [2018-01-25 05:22:03,182 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-25 05:22:03,182 INFO L225 Difference]: With dead ends: 87 [2018-01-25 05:22:03,182 INFO L226 Difference]: Without dead ends: 83 [2018-01-25 05:22:03,183 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 111 GetRequests, 62 SyntacticMatches, 8 SemanticMatches, 41 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 501 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=263, Invalid=1543, Unknown=0, NotChecked=0, Total=1806 [2018-01-25 05:22:03,183 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 83 states. [2018-01-25 05:22:03,188 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 83 to 70. [2018-01-25 05:22:03,188 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 70 states. [2018-01-25 05:22:03,189 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 70 states to 70 states and 86 transitions. [2018-01-25 05:22:03,189 INFO L78 Accepts]: Start accepts. Automaton has 70 states and 86 transitions. Word has length 23 [2018-01-25 05:22:03,189 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-25 05:22:03,190 INFO L432 AbstractCegarLoop]: Abstraction has 70 states and 86 transitions. [2018-01-25 05:22:03,190 INFO L433 AbstractCegarLoop]: Interpolant automaton has 22 states. [2018-01-25 05:22:03,190 INFO L276 IsEmpty]: Start isEmpty. Operand 70 states and 86 transitions. [2018-01-25 05:22:03,190 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2018-01-25 05:22:03,191 INFO L314 BasicCegarLoop]: Found error trace [2018-01-25 05:22:03,191 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-25 05:22:03,191 INFO L371 AbstractCegarLoop]: === Iteration 10 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-25 05:22:03,191 INFO L82 PathProgramCache]: Analyzing trace with hash -557502487, now seen corresponding path program 1 times [2018-01-25 05:22:03,191 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-25 05:22:03,192 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-25 05:22:03,192 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-25 05:22:03,193 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-25 05:22:03,193 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-25 05:22:03,205 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-25 05:22:03,206 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-25 05:22:03,252 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-25 05:22:03,252 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-25 05:22:03,252 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-01-25 05:22:03,252 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-25 05:22:03,253 INFO L409 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-01-25 05:22:03,253 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-01-25 05:22:03,253 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2018-01-25 05:22:03,253 INFO L87 Difference]: Start difference. First operand 70 states and 86 transitions. Second operand 6 states. [2018-01-25 05:22:03,297 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-25 05:22:03,297 INFO L93 Difference]: Finished difference Result 73 states and 92 transitions. [2018-01-25 05:22:03,297 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-01-25 05:22:03,297 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 25 [2018-01-25 05:22:03,297 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-25 05:22:03,299 INFO L225 Difference]: With dead ends: 73 [2018-01-25 05:22:03,299 INFO L226 Difference]: Without dead ends: 72 [2018-01-25 05:22:03,299 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=19, Invalid=37, Unknown=0, NotChecked=0, Total=56 [2018-01-25 05:22:03,299 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 72 states. [2018-01-25 05:22:03,305 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 72 to 69. [2018-01-25 05:22:03,306 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 69 states. [2018-01-25 05:22:03,306 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 69 states to 69 states and 83 transitions. [2018-01-25 05:22:03,307 INFO L78 Accepts]: Start accepts. Automaton has 69 states and 83 transitions. Word has length 25 [2018-01-25 05:22:03,307 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-25 05:22:03,307 INFO L432 AbstractCegarLoop]: Abstraction has 69 states and 83 transitions. [2018-01-25 05:22:03,307 INFO L433 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-01-25 05:22:03,307 INFO L276 IsEmpty]: Start isEmpty. Operand 69 states and 83 transitions. [2018-01-25 05:22:03,308 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2018-01-25 05:22:03,308 INFO L314 BasicCegarLoop]: Found error trace [2018-01-25 05:22:03,308 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-25 05:22:03,308 INFO L371 AbstractCegarLoop]: === Iteration 11 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-25 05:22:03,308 INFO L82 PathProgramCache]: Analyzing trace with hash -557502486, now seen corresponding path program 1 times [2018-01-25 05:22:03,309 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-25 05:22:03,309 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-25 05:22:03,310 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-25 05:22:03,310 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-25 05:22:03,310 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-25 05:22:03,321 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-25 05:22:03,322 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-25 05:22:03,433 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-25 05:22:03,434 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-25 05:22:03,434 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2018-01-25 05:22:03,434 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-25 05:22:03,434 INFO L409 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-01-25 05:22:03,434 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-01-25 05:22:03,434 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=54, Unknown=0, NotChecked=0, Total=72 [2018-01-25 05:22:03,435 INFO L87 Difference]: Start difference. First operand 69 states and 83 transitions. Second operand 9 states. [2018-01-25 05:22:03,536 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-25 05:22:03,536 INFO L93 Difference]: Finished difference Result 99 states and 123 transitions. [2018-01-25 05:22:03,537 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-01-25 05:22:03,537 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 25 [2018-01-25 05:22:03,537 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-25 05:22:03,537 INFO L225 Difference]: With dead ends: 99 [2018-01-25 05:22:03,538 INFO L226 Difference]: Without dead ends: 98 [2018-01-25 05:22:03,538 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 18 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=32, Invalid=100, Unknown=0, NotChecked=0, Total=132 [2018-01-25 05:22:03,538 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 98 states. [2018-01-25 05:22:03,545 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 98 to 80. [2018-01-25 05:22:03,545 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 80 states. [2018-01-25 05:22:03,546 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 80 states to 80 states and 98 transitions. [2018-01-25 05:22:03,546 INFO L78 Accepts]: Start accepts. Automaton has 80 states and 98 transitions. Word has length 25 [2018-01-25 05:22:03,546 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-25 05:22:03,546 INFO L432 AbstractCegarLoop]: Abstraction has 80 states and 98 transitions. [2018-01-25 05:22:03,546 INFO L433 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-01-25 05:22:03,547 INFO L276 IsEmpty]: Start isEmpty. Operand 80 states and 98 transitions. [2018-01-25 05:22:03,547 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2018-01-25 05:22:03,547 INFO L314 BasicCegarLoop]: Found error trace [2018-01-25 05:22:03,548 INFO L322 BasicCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-25 05:22:03,548 INFO L371 AbstractCegarLoop]: === Iteration 12 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-25 05:22:03,548 INFO L82 PathProgramCache]: Analyzing trace with hash -59760490, now seen corresponding path program 2 times [2018-01-25 05:22:03,548 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-25 05:22:03,549 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-25 05:22:03,549 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-25 05:22:03,549 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-25 05:22:03,549 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-25 05:22:03,563 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-25 05:22:03,564 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-25 05:22:03,911 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-25 05:22:03,911 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-25 05:22:03,911 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-01-25 05:22:03,911 INFO L183 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-01-25 05:22:03,912 INFO L434 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-01-25 05:22:03,912 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-25 05:22:03,912 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG 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-25 05:22:03,919 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-01-25 05:22:03,919 INFO L280 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST1 (IT: FPandBP) [2018-01-25 05:22:03,934 INFO L201 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-25 05:22:03,939 INFO L214 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-25 05:22:03,940 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-25 05:22:03,943 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-25 05:22:04,009 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-25 05:22:04,009 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:04,035 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-25 05:22:04,035 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:04,042 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:22:04,043 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:27, output treesize:25 [2018-01-25 05:22:04,115 INFO L700 Elim1Store]: detected not equals via solver [2018-01-25 05:22:04,116 INFO L700 Elim1Store]: detected not equals via solver [2018-01-25 05:22:04,116 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 12 treesize of output 21 [2018-01-25 05:22:04,117 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:04,133 INFO L700 Elim1Store]: detected not equals via solver [2018-01-25 05:22:04,134 INFO L700 Elim1Store]: detected not equals via solver [2018-01-25 05:22:04,135 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-25 05:22:04,136 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:04,151 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:22:04,152 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:36, output treesize:25 [2018-01-25 05:22:04,216 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 16 [2018-01-25 05:22:04,218 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 15 [2018-01-25 05:22:04,219 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:04,221 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:22:04,229 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-25 05:22:04,229 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:41, output treesize:37 [2018-01-25 05:22:04,261 INFO L700 Elim1Store]: detected not equals via solver [2018-01-25 05:22:04,264 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 32 treesize of output 33 [2018-01-25 05:22:04,275 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 13 treesize of output 12 [2018-01-25 05:22:04,275 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:04,287 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:22:04,302 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-2 vars, End of recursive call: 3 dim-0 vars, and 1 xjuncts. [2018-01-25 05:22:04,303 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:52, output treesize:48 [2018-01-25 05:22:04,408 INFO L700 Elim1Store]: detected not equals via solver [2018-01-25 05:22:04,412 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 34 treesize of output 32 [2018-01-25 05:22:04,422 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 18 treesize of output 19 [2018-01-25 05:22:04,423 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-25 05:22:04,442 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 10 treesize of output 1 [2018-01-25 05:22:04,442 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:04,446 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-25 05:22:04,456 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-2 vars, End of recursive call: 3 dim-0 vars, and 2 xjuncts. [2018-01-25 05:22:04,457 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 4 variables, input treesize:54, output treesize:69 [2018-01-25 05:22:04,582 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-25 05:22:04,582 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-01-25 05:22:04,806 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 24 treesize of output 22 [2018-01-25 05:22:04,819 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2018-01-25 05:22:04,819 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:04,822 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:22:04,824 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 20 [2018-01-25 05:22:04,845 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2018-01-25 05:22:04,845 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:04,848 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:22:04,855 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 2 xjuncts. [2018-01-25 05:22:04,856 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 1 variables, input treesize:47, output treesize:25 [2018-01-25 05:22:05,020 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 10 treesize of output 3 [2018-01-25 05:22:05,021 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:05,029 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 15 [2018-01-25 05:22:05,037 WARN L307 Elim1Store]: Array PQE input equivalent to true [2018-01-25 05:22:05,037 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:05,038 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 3 [2018-01-25 05:22:05,039 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:05,042 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:22:05,046 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:22:05,046 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 4 variables, input treesize:26, output treesize:9 [2018-01-25 05:22:05,122 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-25 05:22:05,142 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-25 05:22:05,142 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode CVC4_IG No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 Starting monitored process 5 with cvc4 --tear-down-incremental --print-success --lang smt --rewrite-divk --tlimit-per=12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with cvc4 --tear-down-incremental --print-success --lang smt --rewrite-divk --tlimit-per=12000 [2018-01-25 05:22:05,145 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-01-25 05:22:05,145 INFO L280 anRefinementStrategy]: Using traceCheck mode CVC4_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST1 (IT: FPandBP) [2018-01-25 05:22:05,162 INFO L201 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-25 05:22:05,191 INFO L214 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-25 05:22:05,224 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-25 05:22:05,229 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-25 05:22:05,292 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-25 05:22:05,292 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:05,300 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-25 05:22:05,301 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:05,306 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:22:05,306 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:19, output treesize:17 [2018-01-25 05:22:05,371 INFO L700 Elim1Store]: detected not equals via solver [2018-01-25 05:22:05,372 INFO L700 Elim1Store]: detected not equals via solver [2018-01-25 05:22:05,373 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-25 05:22:05,373 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:05,380 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 12 treesize of output 15 [2018-01-25 05:22:05,380 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:05,385 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:22:05,386 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:28, output treesize:21 [2018-01-25 05:22:05,454 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 13 [2018-01-25 05:22:05,455 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 13 treesize of output 12 [2018-01-25 05:22:05,455 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:05,457 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:22:05,461 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:22:05,462 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:29, output treesize:25 [2018-01-25 05:22:05,506 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 30 [2018-01-25 05:22:05,508 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 13 treesize of output 12 [2018-01-25 05:22:05,508 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:05,513 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:22:05,521 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-25 05:22:05,521 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:36, output treesize:32 [2018-01-25 05:22:05,689 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 31 treesize of output 29 [2018-01-25 05:22:05,695 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 1 case distinctions, treesize of input 15 treesize of output 16 [2018-01-25 05:22:05,695 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-25 05:22:05,704 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 10 treesize of output 1 [2018-01-25 05:22:05,704 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:05,707 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-25 05:22:05,712 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: and 2 xjuncts. [2018-01-25 05:22:05,712 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 3 variables, input treesize:38, output treesize:20 [2018-01-25 05:22:05,865 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-25 05:22:05,865 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-01-25 05:22:06,132 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 14 [2018-01-25 05:22:06,140 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2018-01-25 05:22:06,140 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:06,141 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:22:06,145 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:22:06,145 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:36, output treesize:25 [2018-01-25 05:22:07,072 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 10 treesize of output 3 [2018-01-25 05:22:07,072 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:07,077 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 1 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 23 [2018-01-25 05:22:07,090 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 7 [2018-01-25 05:22:07,090 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:07,090 WARN L307 Elim1Store]: Array PQE input equivalent to true [2018-01-25 05:22:07,090 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:07,094 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:22:07,099 INFO L267 ElimStorePlain]: Start of recursive call 1: 4 dim-0 vars, 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-25 05:22:07,099 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 6 variables, input treesize:37, output treesize:7 [2018-01-25 05:22:07,125 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-25 05:22:07,126 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 5 imperfect interpolant sequences. [2018-01-25 05:22:07,126 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 15, 13, 14, 12] total 58 [2018-01-25 05:22:07,126 INFO L247 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-01-25 05:22:07,127 INFO L409 AbstractCegarLoop]: Interpolant automaton has 27 states [2018-01-25 05:22:07,127 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2018-01-25 05:22:07,128 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=245, Invalid=3176, Unknown=1, NotChecked=0, Total=3422 [2018-01-25 05:22:07,128 INFO L87 Difference]: Start difference. First operand 80 states and 98 transitions. Second operand 27 states. [2018-01-25 05:22:11,862 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-25 05:22:11,862 INFO L93 Difference]: Finished difference Result 183 states and 220 transitions. [2018-01-25 05:22:11,862 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2018-01-25 05:22:11,862 INFO L78 Accepts]: Start accepts. Automaton has 27 states. Word has length 26 [2018-01-25 05:22:11,863 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-25 05:22:11,863 INFO L225 Difference]: With dead ends: 183 [2018-01-25 05:22:11,863 INFO L226 Difference]: Without dead ends: 179 [2018-01-25 05:22:11,865 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 134 GetRequests, 53 SyntacticMatches, 6 SemanticMatches, 75 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1505 ImplicationChecksByTransitivity, 3.7s TimeCoverageRelationStatistics Valid=611, Invalid=5240, Unknown=1, NotChecked=0, Total=5852 [2018-01-25 05:22:11,865 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 179 states. [2018-01-25 05:22:11,870 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 179 to 83. [2018-01-25 05:22:11,871 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 83 states. [2018-01-25 05:22:11,871 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 83 states to 83 states and 102 transitions. [2018-01-25 05:22:11,872 INFO L78 Accepts]: Start accepts. Automaton has 83 states and 102 transitions. Word has length 26 [2018-01-25 05:22:11,872 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-25 05:22:11,872 INFO L432 AbstractCegarLoop]: Abstraction has 83 states and 102 transitions. [2018-01-25 05:22:11,872 INFO L433 AbstractCegarLoop]: Interpolant automaton has 27 states. [2018-01-25 05:22:11,872 INFO L276 IsEmpty]: Start isEmpty. Operand 83 states and 102 transitions. [2018-01-25 05:22:11,873 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2018-01-25 05:22:11,873 INFO L314 BasicCegarLoop]: Found error trace [2018-01-25 05:22:11,873 INFO L322 BasicCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-25 05:22:11,873 INFO L371 AbstractCegarLoop]: === Iteration 13 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-25 05:22:11,873 INFO L82 PathProgramCache]: Analyzing trace with hash 2086668971, now seen corresponding path program 3 times [2018-01-25 05:22:11,874 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-25 05:22:11,874 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-25 05:22:11,874 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-01-25 05:22:11,874 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-25 05:22:11,874 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-25 05:22:11,888 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-25 05:22:11,889 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-25 05:22:12,352 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-25 05:22:12,352 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-25 05:22:12,352 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-01-25 05:22:12,353 INFO L183 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-01-25 05:22:12,353 INFO L434 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-01-25 05:22:12,353 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-25 05:22:12,353 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG 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-25 05:22:12,359 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-01-25 05:22:12,359 INFO L280 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST2 (IT: FPandBP) [2018-01-25 05:22:12,369 INFO L254 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued a check-sat command [2018-01-25 05:22:12,372 INFO L254 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued a check-sat command [2018-01-25 05:22:12,375 INFO L254 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued a check-sat command [2018-01-25 05:22:12,377 INFO L254 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued a check-sat command [2018-01-25 05:22:12,379 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-25 05:22:12,382 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-25 05:22:12,393 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-25 05:22:12,394 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:12,401 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-25 05:22:12,401 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:12,407 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:22:12,407 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:22, output treesize:20 [2018-01-25 05:22:12,430 INFO L700 Elim1Store]: detected not equals via solver [2018-01-25 05:22:12,431 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 12 treesize of output 15 [2018-01-25 05:22:12,431 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:12,440 INFO L700 Elim1Store]: detected not equals via solver [2018-01-25 05:22:12,440 INFO L700 Elim1Store]: detected not equals via solver [2018-01-25 05:22:12,441 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-25 05:22:12,441 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:12,447 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:22:12,447 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:31, output treesize:24 [2018-01-25 05:22:12,489 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 15 [2018-01-25 05:22:12,491 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 15 treesize of output 14 [2018-01-25 05:22:12,524 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:12,525 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:22:12,531 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-25 05:22:12,531 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:34, output treesize:30 [2018-01-25 05:22:12,559 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 31 treesize of output 32 [2018-01-25 05:22:12,562 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 12 [2018-01-25 05:22:12,562 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:12,566 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:22:12,571 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-2 vars, End of recursive call: 3 dim-0 vars, and 1 xjuncts. [2018-01-25 05:22:12,572 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:41, output treesize:37 [2018-01-25 05:22:12,694 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 34 treesize of output 32 [2018-01-25 05:22:12,701 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 18 treesize of output 15 [2018-01-25 05:22:12,701 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-25 05:22:12,709 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 10 treesize of output 1 [2018-01-25 05:22:12,709 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:12,712 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-25 05:22:12,719 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-2 vars, End of recursive call: and 3 xjuncts. [2018-01-25 05:22:12,719 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 4 variables, input treesize:44, output treesize:18 [2018-01-25 05:22:12,763 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 0 proven. 13 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-01-25 05:22:12,764 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-01-25 05:22:13,036 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 14 [2018-01-25 05:22:13,044 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 5 treesize of output 3 [2018-01-25 05:22:13,045 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:13,046 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:22:13,051 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-25 05:22:13,051 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:36, output treesize:39 [2018-01-25 05:22:13,434 WARN L143 SmtUtils]: Spent 302ms on a formula simplification that was a NOOP. DAG size: 36 [2018-01-25 05:22:13,786 WARN L143 SmtUtils]: Spent 303ms on a formula simplification that was a NOOP. DAG size: 36 [2018-01-25 05:22:13,802 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 36 treesize of output 30 [2018-01-25 05:22:13,803 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:13,813 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 1 new quantified variables, introduced 0 case distinctions, treesize of input 34 treesize of output 34 [2018-01-25 05:22:13,830 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 19 treesize of output 7 [2018-01-25 05:22:13,830 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:13,835 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:22:13,846 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 1 new quantified variables, introduced 0 case distinctions, treesize of input 30 treesize of output 30 [2018-01-25 05:22:13,859 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 21 treesize of output 7 [2018-01-25 05:22:13,860 INFO L267 ElimStorePlain]: Start of recursive call 6: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:13,863 INFO L267 ElimStorePlain]: Start of recursive call 5: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:22:13,872 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 10 [2018-01-25 05:22:13,872 INFO L267 ElimStorePlain]: Start of recursive call 7: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:13,880 INFO L267 ElimStorePlain]: Start of recursive call 1: 8 dim-0 vars, 4 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-25 05:22:13,881 INFO L202 ElimStorePlain]: Needed 7 recursive calls to eliminate 12 variables, input treesize:71, output treesize:7 [2018-01-25 05:22:13,886 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 0 proven. 13 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-01-25 05:22:13,915 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-25 05:22:13,915 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode CVC4_IG No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 Starting monitored process 7 with cvc4 --tear-down-incremental --print-success --lang smt --rewrite-divk --tlimit-per=12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with cvc4 --tear-down-incremental --print-success --lang smt --rewrite-divk --tlimit-per=12000 [2018-01-25 05:22:13,918 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-01-25 05:22:13,918 INFO L280 anRefinementStrategy]: Using traceCheck mode CVC4_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST2 (IT: FPandBP) [2018-01-25 05:22:13,933 INFO L254 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued a check-sat command [2018-01-25 05:22:13,960 INFO L254 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued a check-sat command [2018-01-25 05:22:13,992 INFO L254 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued a check-sat command [2018-01-25 05:22:14,026 INFO L254 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued a check-sat command [2018-01-25 05:22:14,059 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-25 05:22:14,064 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-25 05:22:14,072 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-25 05:22:14,072 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:14,078 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-25 05:22:14,079 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:14,083 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:22:14,083 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:22, output treesize:20 [2018-01-25 05:22:14,088 INFO L700 Elim1Store]: detected not equals via solver [2018-01-25 05:22:14,089 INFO L700 Elim1Store]: detected not equals via solver [2018-01-25 05:22:14,089 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-25 05:22:14,089 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:14,097 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 12 treesize of output 15 [2018-01-25 05:22:14,098 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:14,103 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:22:14,103 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:31, output treesize:24 [2018-01-25 05:22:14,108 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 16 [2018-01-25 05:22:14,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, 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 15 [2018-01-25 05:22:14,110 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:14,111 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:22:14,117 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-25 05:22:14,117 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:38, output treesize:34 [2018-01-25 05:22:14,158 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 32 treesize of output 33 [2018-01-25 05:22:14,160 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 13 treesize of output 12 [2018-01-25 05:22:14,160 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:14,164 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:22:14,171 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-2 vars, End of recursive call: 3 dim-0 vars, and 1 xjuncts. [2018-01-25 05:22:14,171 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:45, output treesize:41 [2018-01-25 05:22:14,348 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 34 treesize of output 32 [2018-01-25 05:22:14,353 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 18 treesize of output 15 [2018-01-25 05:22:14,354 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-25 05:22:14,360 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 10 treesize of output 1 [2018-01-25 05:22:14,360 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:14,363 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-25 05:22:14,371 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-2 vars, End of recursive call: and 2 xjuncts. [2018-01-25 05:22:14,371 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 4 variables, input treesize:50, output treesize:27 [2018-01-25 05:22:14,516 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-25 05:22:14,517 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-01-25 05:22:14,883 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 14 [2018-01-25 05:22:14,891 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 5 treesize of output 3 [2018-01-25 05:22:14,892 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:14,893 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:22:14,900 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-25 05:22:14,900 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:39, output treesize:58 [2018-01-25 05:22:16,539 WARN L143 SmtUtils]: Spent 424ms on a formula simplification that was a NOOP. DAG size: 39 [2018-01-25 05:22:18,486 WARN L143 SmtUtils]: Spent 1103ms on a formula simplification that was a NOOP. DAG size: 39 [2018-01-25 05:22:18,520 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 36 treesize of output 30 [2018-01-25 05:22:18,521 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:18,532 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 1 new quantified variables, introduced 0 case distinctions, treesize of input 30 treesize of output 30 [2018-01-25 05:22:18,545 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 21 treesize of output 7 [2018-01-25 05:22:18,546 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:18,548 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:22:18,558 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 34 treesize of output 28 [2018-01-25 05:22:18,559 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:18,569 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 1 new quantified variables, introduced 0 case distinctions, treesize of input 28 treesize of output 28 [2018-01-25 05:22:18,586 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 19 treesize of output 7 [2018-01-25 05:22:18,587 INFO L267 ElimStorePlain]: Start of recursive call 7: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:18,590 INFO L267 ElimStorePlain]: Start of recursive call 6: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:22:18,598 INFO L267 ElimStorePlain]: Start of recursive call 1: 8 dim-0 vars, 4 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-25 05:22:18,598 INFO L202 ElimStorePlain]: Needed 7 recursive calls to eliminate 12 variables, input treesize:93, output treesize:7 [2018-01-25 05:22:18,605 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-25 05:22:18,606 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 5 imperfect interpolant sequences. [2018-01-25 05:22:18,606 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14, 12, 15, 13] total 50 [2018-01-25 05:22:18,606 INFO L247 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-01-25 05:22:18,607 INFO L409 AbstractCegarLoop]: Interpolant automaton has 23 states [2018-01-25 05:22:18,607 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2018-01-25 05:22:18,607 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=187, Invalid=2361, Unknown=2, NotChecked=0, Total=2550 [2018-01-25 05:22:18,608 INFO L87 Difference]: Start difference. First operand 83 states and 102 transitions. Second operand 23 states. [2018-01-25 05:22:20,238 WARN L146 SmtUtils]: Spent 1193ms on a formula simplification. DAG size of input: 65 DAG size of output 49 [2018-01-25 05:22:23,575 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-25 05:22:23,575 INFO L93 Difference]: Finished difference Result 304 states and 378 transitions. [2018-01-25 05:22:23,576 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2018-01-25 05:22:23,576 INFO L78 Accepts]: Start accepts. Automaton has 23 states. Word has length 29 [2018-01-25 05:22:23,576 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-25 05:22:23,578 INFO L225 Difference]: With dead ends: 304 [2018-01-25 05:22:23,579 INFO L226 Difference]: Without dead ends: 300 [2018-01-25 05:22:23,580 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 154 GetRequests, 70 SyntacticMatches, 11 SemanticMatches, 73 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1370 ImplicationChecksByTransitivity, 9.8s TimeCoverageRelationStatistics Valid=589, Invalid=4959, Unknown=2, NotChecked=0, Total=5550 [2018-01-25 05:22:23,581 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 300 states. [2018-01-25 05:22:23,594 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 300 to 150. [2018-01-25 05:22:23,594 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 150 states. [2018-01-25 05:22:23,596 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 150 states to 150 states and 194 transitions. [2018-01-25 05:22:23,596 INFO L78 Accepts]: Start accepts. Automaton has 150 states and 194 transitions. Word has length 29 [2018-01-25 05:22:23,596 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-25 05:22:23,597 INFO L432 AbstractCegarLoop]: Abstraction has 150 states and 194 transitions. [2018-01-25 05:22:23,597 INFO L433 AbstractCegarLoop]: Interpolant automaton has 23 states. [2018-01-25 05:22:23,597 INFO L276 IsEmpty]: Start isEmpty. Operand 150 states and 194 transitions. [2018-01-25 05:22:23,599 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2018-01-25 05:22:23,599 INFO L314 BasicCegarLoop]: Found error trace [2018-01-25 05:22:23,600 INFO L322 BasicCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-25 05:22:23,600 INFO L371 AbstractCegarLoop]: === Iteration 14 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-25 05:22:23,600 INFO L82 PathProgramCache]: Analyzing trace with hash -1785596499, now seen corresponding path program 1 times [2018-01-25 05:22:23,600 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-25 05:22:23,601 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-25 05:22:23,601 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-01-25 05:22:23,601 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-25 05:22:23,601 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-25 05:22:23,617 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-25 05:22:23,618 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-25 05:22:24,139 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-25 05:22:24,139 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-25 05:22:24,139 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-01-25 05:22:24,139 INFO L199 CegarAbsIntRunner]: Running AI on error trace of length 30 with the following transitions: [2018-01-25 05:22:24,140 INFO L201 CegarAbsIntRunner]: [0], [1], [5], [10], [16], [22], [27], [28], [29], [30], [31], [32], [35], [46], [50], [52], [54], [59], [103], [104], [105], [107] [2018-01-25 05:22:24,141 INFO L147 AbstractInterpreter]: Using domain VPDomain [2018-01-25 05:22:24,141 INFO L101 FixpointEngine]: Starting fixpoint engine with domain VPDomain (maxUnwinding=3, maxParallelStates=2) [2018-01-25 05:22:25,162 INFO L259 AbstractInterpreter]: Some error location(s) were reachable [2018-01-25 05:22:25,162 INFO L268 AbstractInterpreter]: Visited 22 different actions 26 times. Merged at 4 different actions 4 times. Never widened. Found 1 fixpoints after 1 different actions. Largest state had 25 variables. [2018-01-25 05:22:25,184 INFO L434 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: Unknown [2018-01-25 05:22:25,184 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-25 05:22:25,184 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG 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-25 05:22:25,198 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-25 05:22:25,198 INFO L280 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-01-25 05:22:25,220 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-25 05:22:25,224 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-25 05:22:25,254 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-25 05:22:25,255 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:25,267 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-25 05:22:25,267 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:25,277 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:22:25,277 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:27, output treesize:25 [2018-01-25 05:22:25,397 INFO L700 Elim1Store]: detected not equals via solver [2018-01-25 05:22:25,398 INFO L700 Elim1Store]: detected not equals via solver [2018-01-25 05:22:25,398 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-25 05:22:25,399 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:25,416 INFO L700 Elim1Store]: detected not equals via solver [2018-01-25 05:22:25,417 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 12 treesize of output 21 [2018-01-25 05:22:25,417 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:25,430 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:22:25,430 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:36, output treesize:25 [2018-01-25 05:22:25,531 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 16 [2018-01-25 05:22:25,532 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 15 [2018-01-25 05:22:25,533 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:25,534 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:22:25,542 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-25 05:22:25,543 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:41, output treesize:37 [2018-01-25 05:22:25,583 INFO L700 Elim1Store]: detected not equals via solver [2018-01-25 05:22:25,586 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 32 treesize of output 33 [2018-01-25 05:22:25,588 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 13 treesize of output 12 [2018-01-25 05:22:25,589 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:25,593 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:22:25,601 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-2 vars, End of recursive call: 3 dim-0 vars, and 1 xjuncts. [2018-01-25 05:22:25,601 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:52, output treesize:48 [2018-01-25 05:22:25,871 INFO L700 Elim1Store]: detected not equals via solver [2018-01-25 05:22:25,872 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 45 treesize of output 41 [2018-01-25 05:22:25,876 INFO L700 Elim1Store]: detected not equals via solver [2018-01-25 05:22:25,881 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 3 disjoint index pairs (out of 3 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 27 treesize of output 41 [2018-01-25 05:22:25,882 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-25 05:22:25,896 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 1 [2018-01-25 05:22:25,897 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:25,904 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-25 05:22:25,919 INFO L267 ElimStorePlain]: Start of recursive call 1: 4 dim-0 vars, 1 dim-2 vars, End of recursive call: 4 dim-0 vars, and 2 xjuncts. [2018-01-25 05:22:25,919 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 5 variables, input treesize:73, output treesize:122 [2018-01-25 05:22:26,077 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-25 05:22:26,077 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-01-25 05:22:26,441 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 35 treesize of output 31 [2018-01-25 05:22:26,458 INFO L682 Elim1Store]: detected equality via solver [2018-01-25 05:22:26,459 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 5 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 12 [2018-01-25 05:22:26,459 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:26,463 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:22:26,471 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-25 05:22:26,471 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:48, output treesize:64 [2018-01-25 05:22:26,688 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 1 new quantified variables, introduced 0 case distinctions, treesize of input 24 treesize of output 27 [2018-01-25 05:22:26,703 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 3 [2018-01-25 05:22:26,703 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:26,708 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:22:26,719 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 10 [2018-01-25 05:22:26,719 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:26,732 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 26 treesize of output 20 [2018-01-25 05:22:26,732 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:26,742 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 1 new quantified variables, introduced 0 case distinctions, treesize of input 20 treesize of output 23 [2018-01-25 05:22:26,754 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 3 [2018-01-25 05:22:26,754 INFO L267 ElimStorePlain]: Start of recursive call 7: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:26,757 INFO L267 ElimStorePlain]: Start of recursive call 6: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:22:26,765 INFO L267 ElimStorePlain]: Start of recursive call 1: 4 dim-0 vars, 4 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-25 05:22:26,765 INFO L202 ElimStorePlain]: Needed 7 recursive calls to eliminate 8 variables, input treesize:64, output treesize:17 [2018-01-25 05:22:26,839 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-25 05:22:26,859 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-25 05:22:26,859 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode CVC4_IG No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 Starting monitored process 9 with cvc4 --tear-down-incremental --print-success --lang smt --rewrite-divk --tlimit-per=12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with cvc4 --tear-down-incremental --print-success --lang smt --rewrite-divk --tlimit-per=12000 [2018-01-25 05:22:26,861 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-25 05:22:26,862 INFO L280 anRefinementStrategy]: Using traceCheck mode CVC4_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-01-25 05:22:26,928 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-25 05:22:26,933 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-25 05:22:26,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 6 treesize of output 5 [2018-01-25 05:22:26,937 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:26,954 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-25 05:22:26,954 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:26,960 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:22:26,961 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:27, output treesize:25 [2018-01-25 05:22:27,043 INFO L700 Elim1Store]: detected not equals via solver [2018-01-25 05:22:27,044 INFO L700 Elim1Store]: detected not equals via solver [2018-01-25 05:22:27,044 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 21 [2018-01-25 05:22:27,044 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:27,056 INFO L700 Elim1Store]: detected not equals via solver [2018-01-25 05:22:27,057 INFO L700 Elim1Store]: detected not equals via solver [2018-01-25 05:22:27,057 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-25 05:22:27,057 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:27,064 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:22:27,064 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:36, output treesize:25 [2018-01-25 05:22:27,172 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 16 [2018-01-25 05:22:27,174 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 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 15 [2018-01-25 05:22:27,174 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:27,176 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:22:27,184 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-25 05:22:27,184 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:41, output treesize:37 [2018-01-25 05:22:27,248 INFO L700 Elim1Store]: detected not equals via solver [2018-01-25 05:22:27,251 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 32 treesize of output 33 [2018-01-25 05:22:27,253 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 12 [2018-01-25 05:22:27,253 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:27,258 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:22:27,266 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-2 vars, End of recursive call: 3 dim-0 vars, and 1 xjuncts. [2018-01-25 05:22:27,267 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:52, output treesize:48 [2018-01-25 05:22:27,545 INFO L700 Elim1Store]: detected not equals via solver [2018-01-25 05:22:27,546 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 45 treesize of output 41 [2018-01-25 05:22:27,550 INFO L700 Elim1Store]: detected not equals via solver [2018-01-25 05:22:27,556 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 3 disjoint index pairs (out of 3 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 27 treesize of output 41 [2018-01-25 05:22:27,556 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-25 05:22:27,573 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 10 treesize of output 1 [2018-01-25 05:22:27,573 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:27,580 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-25 05:22:27,596 INFO L267 ElimStorePlain]: Start of recursive call 1: 4 dim-0 vars, 1 dim-2 vars, End of recursive call: 4 dim-0 vars, and 2 xjuncts. [2018-01-25 05:22:27,596 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 5 variables, input treesize:76, output treesize:122 [2018-01-25 05:22:27,649 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-25 05:22:27,650 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-01-25 05:22:27,938 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 35 treesize of output 31 [2018-01-25 05:22:27,954 INFO L682 Elim1Store]: detected equality via solver [2018-01-25 05:22:27,955 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 2 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 12 [2018-01-25 05:22:27,956 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:27,959 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:22:27,969 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:22:27,969 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:47, output treesize:23 [2018-01-25 05:22:28,159 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 10 treesize of output 3 [2018-01-25 05:22:28,159 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:28,164 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 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 11 treesize of output 15 [2018-01-25 05:22:28,171 WARN L307 Elim1Store]: Array PQE input equivalent to true [2018-01-25 05:22:28,172 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:28,173 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 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 3 [2018-01-25 05:22:28,173 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-25 05:22:28,175 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:22:28,179 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-25 05:22:28,179 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 4 variables, input treesize:31, output treesize:14 [2018-01-25 05:22:28,297 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-25 05:22:28,299 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 5 imperfect interpolant sequences. [2018-01-25 05:22:28,299 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 17, 15, 17, 15] total 62 [2018-01-25 05:22:28,299 INFO L247 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-01-25 05:22:28,299 INFO L409 AbstractCegarLoop]: Interpolant automaton has 32 states [2018-01-25 05:22:28,299 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2018-01-25 05:22:28,300 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=345, Invalid=3561, Unknown=0, NotChecked=0, Total=3906 [2018-01-25 05:22:28,300 INFO L87 Difference]: Start difference. First operand 150 states and 194 transitions. Second operand 32 states. [2018-01-25 05:22:29,034 WARN L146 SmtUtils]: Spent 387ms on a formula simplification. DAG size of input: 81 DAG size of output 52 [2018-01-25 05:22:31,392 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-25 05:22:31,393 INFO L93 Difference]: Finished difference Result 427 states and 537 transitions. [2018-01-25 05:22:31,393 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2018-01-25 05:22:31,393 INFO L78 Accepts]: Start accepts. Automaton has 32 states. Word has length 29 [2018-01-25 05:22:31,393 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-25 05:22:31,395 INFO L225 Difference]: With dead ends: 427 [2018-01-25 05:22:31,395 INFO L226 Difference]: Without dead ends: 423 [2018-01-25 05:22:31,397 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 157 GetRequests, 64 SyntacticMatches, 10 SemanticMatches, 83 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2120 ImplicationChecksByTransitivity, 4.6s TimeCoverageRelationStatistics Valid=849, Invalid=6291, Unknown=0, NotChecked=0, Total=7140 [2018-01-25 05:22:31,397 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 423 states. [2018-01-25 05:22:31,412 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 423 to 181. [2018-01-25 05:22:31,412 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 181 states. [2018-01-25 05:22:31,414 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 181 states to 181 states and 237 transitions. [2018-01-25 05:22:31,414 INFO L78 Accepts]: Start accepts. Automaton has 181 states and 237 transitions. Word has length 29 [2018-01-25 05:22:31,414 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-25 05:22:31,414 INFO L432 AbstractCegarLoop]: Abstraction has 181 states and 237 transitions. [2018-01-25 05:22:31,414 INFO L433 AbstractCegarLoop]: Interpolant automaton has 32 states. [2018-01-25 05:22:31,415 INFO L276 IsEmpty]: Start isEmpty. Operand 181 states and 237 transitions. [2018-01-25 05:22:31,416 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2018-01-25 05:22:31,416 INFO L314 BasicCegarLoop]: Found error trace [2018-01-25 05:22:31,416 INFO L322 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-25 05:22:31,416 INFO L371 AbstractCegarLoop]: === Iteration 15 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-25 05:22:31,416 INFO L82 PathProgramCache]: Analyzing trace with hash 933708271, now seen corresponding path program 1 times [2018-01-25 05:22:31,417 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-25 05:22:31,417 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-25 05:22:31,417 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-25 05:22:31,418 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-25 05:22:31,418 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-25 05:22:31,428 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-25 05:22:31,429 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-25 05:22:31,502 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 1 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-25 05:22:31,502 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-25 05:22:31,502 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-01-25 05:22:31,503 INFO L199 CegarAbsIntRunner]: Running AI on error trace of length 33 with the following transitions: [2018-01-25 05:22:31,503 INFO L201 CegarAbsIntRunner]: [0], [1], [5], [10], [16], [20], [27], [28], [29], [30], [31], [32], [35], [46], [50], [52], [57], [65], [67], [70], [71], [73], [74], [77], [85], [103], [104], [105], [107] [2018-01-25 05:22:31,504 INFO L147 AbstractInterpreter]: Using domain VPDomain [2018-01-25 05:22:31,504 INFO L101 FixpointEngine]: Starting fixpoint engine with domain VPDomain (maxUnwinding=3, maxParallelStates=2) [2018-01-25 05:22:42,050 INFO L259 AbstractInterpreter]: Some error location(s) were reachable [2018-01-25 05:22:42,051 INFO L268 AbstractInterpreter]: Visited 29 different actions 51 times. Merged at 8 different actions 22 times. Never widened. Found 1 fixpoints after 1 different actions. Largest state had 30 variables. [2018-01-25 05:22:42,056 INFO L434 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: Unknown [2018-01-25 05:22:42,056 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-25 05:22:42,056 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG 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-25 05:22:42,067 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-25 05:22:42,067 INFO L280 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-01-25 05:22:42,081 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-25 05:22:42,082 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-25 05:22:42,092 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 1 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-25 05:22:42,092 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-01-25 05:22:42,106 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 1 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-25 05:22:42,125 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-25 05:22:42,125 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode CVC4_IG No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 Starting monitored process 11 with cvc4 --tear-down-incremental --print-success --lang smt --rewrite-divk --tlimit-per=12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 11 with cvc4 --tear-down-incremental --print-success --lang smt --rewrite-divk --tlimit-per=12000 [2018-01-25 05:22:42,128 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-25 05:22:42,128 INFO L280 anRefinementStrategy]: Using traceCheck mode CVC4_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-01-25 05:22:42,158 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-25 05:22:42,161 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-25 05:22:42,171 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 1 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-25 05:22:42,172 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-01-25 05:22:42,180 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 1 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-25 05:22:42,181 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 5 imperfect interpolant sequences. [2018-01-25 05:22:42,181 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7, 7, 7] total 7 [2018-01-25 05:22:42,181 INFO L247 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-01-25 05:22:42,181 INFO L409 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-01-25 05:22:42,182 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-01-25 05:22:42,182 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2018-01-25 05:22:42,182 INFO L87 Difference]: Start difference. First operand 181 states and 237 transitions. Second operand 7 states. [2018-01-25 05:22:42,244 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-25 05:22:42,244 INFO L93 Difference]: Finished difference Result 257 states and 332 transitions. [2018-01-25 05:22:42,245 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-01-25 05:22:42,245 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 32 [2018-01-25 05:22:42,245 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-25 05:22:42,246 INFO L225 Difference]: With dead ends: 257 [2018-01-25 05:22:42,246 INFO L226 Difference]: Without dead ends: 171 [2018-01-25 05:22:42,246 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 137 GetRequests, 124 SyntacticMatches, 4 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=31, Invalid=79, Unknown=0, NotChecked=0, Total=110 [2018-01-25 05:22:42,246 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 171 states. [2018-01-25 05:22:42,256 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 171 to 114. [2018-01-25 05:22:42,256 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 114 states. [2018-01-25 05:22:42,257 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 114 states to 114 states and 135 transitions. [2018-01-25 05:22:42,257 INFO L78 Accepts]: Start accepts. Automaton has 114 states and 135 transitions. Word has length 32 [2018-01-25 05:22:42,257 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-25 05:22:42,257 INFO L432 AbstractCegarLoop]: Abstraction has 114 states and 135 transitions. [2018-01-25 05:22:42,257 INFO L433 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-01-25 05:22:42,257 INFO L276 IsEmpty]: Start isEmpty. Operand 114 states and 135 transitions. [2018-01-25 05:22:42,258 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2018-01-25 05:22:42,258 INFO L314 BasicCegarLoop]: Found error trace [2018-01-25 05:22:42,258 INFO L322 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-25 05:22:42,258 INFO L371 AbstractCegarLoop]: === Iteration 16 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-25 05:22:42,258 INFO L82 PathProgramCache]: Analyzing trace with hash 799694765, now seen corresponding path program 1 times [2018-01-25 05:22:42,258 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-25 05:22:42,259 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-25 05:22:42,259 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-25 05:22:42,259 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-25 05:22:42,259 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-25 05:22:42,268 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-25 05:22:42,269 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-25 05:22:42,441 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-25 05:22:42,442 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-25 05:22:42,442 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-01-25 05:22:42,442 INFO L199 CegarAbsIntRunner]: Running AI on error trace of length 33 with the following transitions: [2018-01-25 05:22:42,442 INFO L201 CegarAbsIntRunner]: [0], [1], [5], [10], [16], [22], [27], [28], [29], [30], [31], [32], [35], [46], [50], [52], [57], [65], [67], [70], [71], [73], [74], [77], [85], [103], [104], [105], [107] [2018-01-25 05:22:42,443 INFO L147 AbstractInterpreter]: Using domain VPDomain [2018-01-25 05:22:42,443 INFO L101 FixpointEngine]: Starting fixpoint engine with domain VPDomain (maxUnwinding=3, maxParallelStates=2) Received shutdown request... [2018-01-25 05:22:48,771 WARN L571 FixpointEngine]: Received timeout, aborting fixpoint engine [2018-01-25 05:22:48,772 WARN L157 AbstractInterpreter]: Abstract interpretation run out of time [2018-01-25 05:22:48,772 INFO L434 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-01-25 05:22:48,772 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-25 05:22:48,772 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG 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-25 05:22:48,777 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-25 05:22:48,778 INFO L280 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-01-25 05:22:48,795 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-25 05:22:48,798 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-25 05:22:48,800 INFO L175 TraceCheckSpWp]: Timeout while computing interpolants [2018-01-25 05:22:48,800 WARN L491 AbstractCegarLoop]: Verification canceled [2018-01-25 05:22:48,805 WARN L187 ceAbstractionStarter]: Timeout [2018-01-25 05:22:48,805 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 25.01 05:22:48 BoogieIcfgContainer [2018-01-25 05:22:48,806 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-01-25 05:22:48,807 INFO L168 Benchmark]: Toolchain (without parser) took 51328.39 ms. Allocated memory was 303.0 MB in the beginning and 1.2 GB in the end (delta: 917.0 MB). Free memory was 263.1 MB in the beginning and 419.6 MB in the end (delta: -156.5 MB). Peak memory consumption was 760.5 MB. Max. memory is 5.3 GB. [2018-01-25 05:22:48,807 INFO L168 Benchmark]: CDTParser took 0.19 ms. Allocated memory is still 303.0 MB. Free memory is still 269.1 MB. There was no memory consumed. Max. memory is 5.3 GB. [2018-01-25 05:22:48,808 INFO L168 Benchmark]: CACSL2BoogieTranslator took 204.36 ms. Allocated memory is still 303.0 MB. Free memory was 262.1 MB in the beginning and 252.0 MB in the end (delta: 10.1 MB). Peak memory consumption was 10.1 MB. Max. memory is 5.3 GB. [2018-01-25 05:22:48,808 INFO L168 Benchmark]: Boogie Preprocessor took 34.07 ms. Allocated memory is still 303.0 MB. Free memory was 252.0 MB in the beginning and 249.9 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 5.3 GB. [2018-01-25 05:22:48,808 INFO L168 Benchmark]: RCFGBuilder took 313.55 ms. Allocated memory is still 303.0 MB. Free memory was 249.9 MB in the beginning and 230.3 MB in the end (delta: 19.6 MB). Peak memory consumption was 19.6 MB. Max. memory is 5.3 GB. [2018-01-25 05:22:48,809 INFO L168 Benchmark]: TraceAbstraction took 50768.11 ms. Allocated memory was 303.0 MB in the beginning and 1.2 GB in the end (delta: 917.0 MB). Free memory was 229.3 MB in the beginning and 419.6 MB in the end (delta: -190.3 MB). Peak memory consumption was 726.7 MB. Max. memory is 5.3 GB. [2018-01-25 05:22:48,810 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.19 ms. Allocated memory is still 303.0 MB. Free memory is still 269.1 MB. There was no memory consumed. Max. memory is 5.3 GB. * CACSL2BoogieTranslator took 204.36 ms. Allocated memory is still 303.0 MB. Free memory was 262.1 MB in the beginning and 252.0 MB in the end (delta: 10.1 MB). Peak memory consumption was 10.1 MB. Max. memory is 5.3 GB. * Boogie Preprocessor took 34.07 ms. Allocated memory is still 303.0 MB. Free memory was 252.0 MB in the beginning and 249.9 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 5.3 GB. * RCFGBuilder took 313.55 ms. Allocated memory is still 303.0 MB. Free memory was 249.9 MB in the beginning and 230.3 MB in the end (delta: 19.6 MB). Peak memory consumption was 19.6 MB. Max. memory is 5.3 GB. * TraceAbstraction took 50768.11 ms. Allocated memory was 303.0 MB in the beginning and 1.2 GB in the end (delta: 917.0 MB). Free memory was 229.3 MB in the beginning and 419.6 MB in the end (delta: -190.3 MB). Peak memory consumption was 726.7 MB. Max. memory is 5.3 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.analysis.abstractinterpretationv2: - StatisticsResult: ArrayEqualityDomainStatistics #Locations : 21 LocStat_MAX_WEQGRAPH_SIZE : 5 LocStat_MAX_SIZEOF_WEQEDGELABEL : 2 LocStat_NO_SUPPORTING_EQUALITIES : 271 LocStat_NO_SUPPORTING_DISEQUALITIES : 35 LocStat_NO_DISJUNCTIONS : -42 LocStat_MAX_NO_DISJUNCTIONS : -1 #Transitions : 28 TransStat_MAX_WEQGRAPH_SIZE : 2 TransStat_MAX_SIZEOF_WEQEDGELABEL : 1 TransStat_NO_SUPPORTING_EQUALITIES : 59 TransStat_NO_SUPPORTING_DISEQUALITIES : 5 TransStat_NO_DISJUNCTIONS : 29 TransStat_MAX_NO_DISJUNCTIONS : 2 - StatisticsResult: EqConstraintFactoryStatistics CONJOIN_DISJUNCTIVE(MILLISECONDS) : 1.900999 RENAME_VARIABLES(MILLISECONDS) : 0.475679 UNFREEZE(MILLISECONDS) : 0.000000 CONJOIN(MILLISECONDS) : 1.839681 PROJECTAWAY(MILLISECONDS) : 1.113324 ADD_WEAK_EQUALITY(MILLISECONDS) : 0.129029 DISJOIN(MILLISECONDS) : 0.260876 RENAME_VARIABLES_DISJUNCTIVE(MILLISECONDS) : 0.520643 ADD_EQUALITY(MILLISECONDS) : 0.024112 DISJOIN_DISJUNCTIVE(MILLISECONDS) : 0.000000 ADD_DISEQUALITY(MILLISECONDS) : 0.016718 #CONJOIN_DISJUNCTIVE : 48 #RENAME_VARIABLES : 72 #UNFREEZE : 0 #CONJOIN : 96 #PROJECTAWAY : 66 #ADD_WEAK_EQUALITY : 9 #DISJOIN : 6 #RENAME_VARIABLES_DISJUNCTIVE : 69 #ADD_EQUALITY : 61 #DISJOIN_DISJUNCTIVE : 0 #ADD_DISEQUALITY : 3 - StatisticsResult: ArrayEqualityDomainStatistics #Locations : 21 LocStat_MAX_WEQGRAPH_SIZE : 5 LocStat_MAX_SIZEOF_WEQEDGELABEL : 2 LocStat_NO_SUPPORTING_EQUALITIES : 266 LocStat_NO_SUPPORTING_DISEQUALITIES : 35 LocStat_NO_DISJUNCTIONS : -42 LocStat_MAX_NO_DISJUNCTIONS : -1 #Transitions : 28 TransStat_MAX_WEQGRAPH_SIZE : 2 TransStat_MAX_SIZEOF_WEQEDGELABEL : 1 TransStat_NO_SUPPORTING_EQUALITIES : 59 TransStat_NO_SUPPORTING_DISEQUALITIES : 5 TransStat_NO_DISJUNCTIONS : 29 TransStat_MAX_NO_DISJUNCTIONS : 2 - StatisticsResult: EqConstraintFactoryStatistics CONJOIN_DISJUNCTIVE(MILLISECONDS) : 1.729403 RENAME_VARIABLES(MILLISECONDS) : 0.346449 UNFREEZE(MILLISECONDS) : 0.000000 CONJOIN(MILLISECONDS) : 1.676885 PROJECTAWAY(MILLISECONDS) : 0.981313 ADD_WEAK_EQUALITY(MILLISECONDS) : 0.085303 DISJOIN(MILLISECONDS) : 0.403091 RENAME_VARIABLES_DISJUNCTIVE(MILLISECONDS) : 0.374669 ADD_EQUALITY(MILLISECONDS) : 0.018048 DISJOIN_DISJUNCTIVE(MILLISECONDS) : 0.000000 ADD_DISEQUALITY(MILLISECONDS) : 0.010340 #CONJOIN_DISJUNCTIVE : 47 #RENAME_VARIABLES : 72 #UNFREEZE : 0 #CONJOIN : 95 #PROJECTAWAY : 66 #ADD_WEAK_EQUALITY : 9 #DISJOIN : 6 #RENAME_VARIABLES_DISJUNCTIVE : 69 #ADD_EQUALITY : 61 #DISJOIN_DISJUNCTIVE : 0 #ADD_DISEQUALITY : 3 - StatisticsResult: ArrayEqualityDomainStatistics #Locations : 28 LocStat_MAX_WEQGRAPH_SIZE : 5 LocStat_MAX_SIZEOF_WEQEDGELABEL : 2 LocStat_NO_SUPPORTING_EQUALITIES : 422 LocStat_NO_SUPPORTING_DISEQUALITIES : 56 LocStat_NO_DISJUNCTIONS : -56 LocStat_MAX_NO_DISJUNCTIONS : -1 #Transitions : 35 TransStat_MAX_WEQGRAPH_SIZE : 2 TransStat_MAX_SIZEOF_WEQEDGELABEL : 1 TransStat_NO_SUPPORTING_EQUALITIES : 77 TransStat_NO_SUPPORTING_DISEQUALITIES : 6 TransStat_NO_DISJUNCTIONS : 38 TransStat_MAX_NO_DISJUNCTIONS : 2 - StatisticsResult: EqConstraintFactoryStatistics CONJOIN_DISJUNCTIVE(MILLISECONDS) : 14.939406 RENAME_VARIABLES(MILLISECONDS) : 1.763757 UNFREEZE(MILLISECONDS) : 0.000000 CONJOIN(MILLISECONDS) : 14.892674 PROJECTAWAY(MILLISECONDS) : 12.727179 ADD_WEAK_EQUALITY(MILLISECONDS) : 0.067794 DISJOIN(MILLISECONDS) : 1.837224 RENAME_VARIABLES_DISJUNCTIVE(MILLISECONDS) : 1.817950 ADD_EQUALITY(MILLISECONDS) : 0.018871 DISJOIN_DISJUNCTIVE(MILLISECONDS) : 0.000000 ADD_DISEQUALITY(MILLISECONDS) : 0.011305 #CONJOIN_DISJUNCTIVE : 99 #RENAME_VARIABLES : 176 #UNFREEZE : 0 #CONJOIN : 172 #PROJECTAWAY : 131 #ADD_WEAK_EQUALITY : 11 #DISJOIN : 34 #RENAME_VARIABLES_DISJUNCTIVE : 157 #ADD_EQUALITY : 80 #DISJOIN_DISJUNCTIVE : 0 #ADD_DISEQUALITY : 4 * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 570). Cancelled while BasicCegarLoop was analyzing trace of length 33 with TraceHistMax 2, while TraceCheckSpWp was constructing forward predicates, while XnfDer was eliminating 1 quantified variables from 1 xjuncts. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 569). Cancelled while BasicCegarLoop was analyzing trace of length 33 with TraceHistMax 2, while TraceCheckSpWp was constructing forward predicates, while XnfDer was eliminating 1 quantified variables from 1 xjuncts. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 570). Cancelled while BasicCegarLoop was analyzing trace of length 33 with TraceHistMax 2, while TraceCheckSpWp was constructing forward predicates, while XnfDer was eliminating 1 quantified variables from 1 xjuncts. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 569). Cancelled while BasicCegarLoop was analyzing trace of length 33 with TraceHistMax 2, while TraceCheckSpWp was constructing forward predicates, while XnfDer was eliminating 1 quantified variables from 1 xjuncts. - TimeoutResultAtElement [Line: 553]: Timeout (TraceAbstraction) Unable to prove that all allocated memory was freed (line 553). Cancelled while BasicCegarLoop was analyzing trace of length 33 with TraceHistMax 2, while TraceCheckSpWp was constructing forward predicates, while XnfDer was eliminating 1 quantified variables from 1 xjuncts. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 549). Cancelled while BasicCegarLoop was analyzing trace of length 33 with TraceHistMax 2, while TraceCheckSpWp was constructing forward predicates, while XnfDer was eliminating 1 quantified variables from 1 xjuncts. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 545). Cancelled while BasicCegarLoop was analyzing trace of length 33 with TraceHistMax 2, while TraceCheckSpWp was constructing forward predicates, while XnfDer was eliminating 1 quantified variables from 1 xjuncts. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 543). Cancelled while BasicCegarLoop was analyzing trace of length 33 with TraceHistMax 2, while TraceCheckSpWp was constructing forward predicates, while XnfDer was eliminating 1 quantified variables from 1 xjuncts. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 545). Cancelled while BasicCegarLoop was analyzing trace of length 33 with TraceHistMax 2, while TraceCheckSpWp was constructing forward predicates, while XnfDer was eliminating 1 quantified variables from 1 xjuncts. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 550). Cancelled while BasicCegarLoop was analyzing trace of length 33 with TraceHistMax 2, while TraceCheckSpWp was constructing forward predicates, while XnfDer was eliminating 1 quantified variables from 1 xjuncts. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 543). Cancelled while BasicCegarLoop was analyzing trace of length 33 with TraceHistMax 2, while TraceCheckSpWp was constructing forward predicates, while XnfDer was eliminating 1 quantified variables from 1 xjuncts. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 545). Cancelled while BasicCegarLoop was analyzing trace of length 33 with TraceHistMax 2, while TraceCheckSpWp was constructing forward predicates, while XnfDer was eliminating 1 quantified variables from 1 xjuncts. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 550). Cancelled while BasicCegarLoop was analyzing trace of length 33 with TraceHistMax 2, while TraceCheckSpWp was constructing forward predicates, while XnfDer was eliminating 1 quantified variables from 1 xjuncts. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 549). Cancelled while BasicCegarLoop was analyzing trace of length 33 with TraceHistMax 2, while TraceCheckSpWp was constructing forward predicates, while XnfDer was eliminating 1 quantified variables from 1 xjuncts. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 545). Cancelled while BasicCegarLoop was analyzing trace of length 33 with TraceHistMax 2, while TraceCheckSpWp was constructing forward predicates, while XnfDer was eliminating 1 quantified variables from 1 xjuncts. - StatisticsResult: Ultimate Automizer benchmark data CFG has 4 procedures, 58 locations, 15 error locations. TIMEOUT Result, 50.7s OverallTime, 16 OverallIterations, 4 TraceHistogramMax, 14.5s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 721 SDtfs, 2013 SDslu, 3826 SDs, 0 SdLazy, 3122 SolverSat, 581 SolverUnsat, 2 SolverUnknown, 0 SolverNotchecked, 6.5s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 764 GetRequests, 385 SyntacticMatches, 39 SemanticMatches, 340 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5540 ImplicationChecksByTransitivity, 20.2s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=181occurred in iteration=14, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 19.0s AbstIntTime, 4 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, AutomataMinimizationStatistics: 0.1s AutomataMinimizationTime, 15 MinimizatonAttempts, 584 StatesRemovedByMinimization, 8 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.6s SatisfiabilityAnalysisTime, 15.6s InterpolantComputationTime, 595 NumberOfCodeBlocks, 595 NumberOfCodeBlocksAsserted, 33 NumberOfCheckSat, 838 ConstructedInterpolants, 111 QuantifiedInterpolants, 268695 SizeOfPredicates, 153 NumberOfNonLiveVariables, 1370 ConjunctsInSsa, 361 ConjunctsInUnsatCore, 35 InterpolantComputations, 10 PerfectInterpolantSequences, 9/215 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, REUSE_STATISTICS: No data available RESULT: Ultimate could not prove your program: Timeout Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/cstrncat-alloca_true-valid-memsafety_true-termination.i_svcomp-DerefFreeMemtrack-32bit-Automizer_Taipan+AI_EQ_smtcomp.epf_AutomizerC.xml/Csv-Benchmark-0-2018-01-25_05-22-48-823.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/cstrncat-alloca_true-valid-memsafety_true-termination.i_svcomp-DerefFreeMemtrack-32bit-Automizer_Taipan+AI_EQ_smtcomp.epf_AutomizerC.xml/Csv-VPDomainBenchmark-0-2018-01-25_05-22-48-823.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/cstrncat-alloca_true-valid-memsafety_true-termination.i_svcomp-DerefFreeMemtrack-32bit-Automizer_Taipan+AI_EQ_smtcomp.epf_AutomizerC.xml/Csv-BenchmarkWithCounters-0-2018-01-25_05-22-48-823.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/cstrncat-alloca_true-valid-memsafety_true-termination.i_svcomp-DerefFreeMemtrack-32bit-Automizer_Taipan+AI_EQ_smtcomp.epf_AutomizerC.xml/Csv-VPDomainBenchmark-1-2018-01-25_05-22-48-823.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/cstrncat-alloca_true-valid-memsafety_true-termination.i_svcomp-DerefFreeMemtrack-32bit-Automizer_Taipan+AI_EQ_smtcomp.epf_AutomizerC.xml/Csv-BenchmarkWithCounters-1-2018-01-25_05-22-48-823.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/cstrncat-alloca_true-valid-memsafety_true-termination.i_svcomp-DerefFreeMemtrack-32bit-Automizer_Taipan+AI_EQ_smtcomp.epf_AutomizerC.xml/Csv-VPDomainBenchmark-2-2018-01-25_05-22-48-823.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/cstrncat-alloca_true-valid-memsafety_true-termination.i_svcomp-DerefFreeMemtrack-32bit-Automizer_Taipan+AI_EQ_smtcomp.epf_AutomizerC.xml/Csv-BenchmarkWithCounters-2-2018-01-25_05-22-48-823.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/cstrncat-alloca_true-valid-memsafety_true-termination.i_svcomp-DerefFreeMemtrack-32bit-Automizer_Taipan+AI_EQ_smtcomp.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-0-2018-01-25_05-22-48-823.csv Completed graceful shutdown