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_precise.epf -i ../../../trunk/examples/svcomp/array-memsafety/cstrncat-alloca_true-valid-memsafety_true-termination.i -------------------------------------------------------------------------------- This is Ultimate 0.1.23-6b94a2f [2018-01-24 23:10:24,856 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-01-24 23:10:24,858 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-01-24 23:10:24,873 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-01-24 23:10:24,874 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-01-24 23:10:24,875 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-01-24 23:10:24,876 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-01-24 23:10:24,877 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-01-24 23:10:24,879 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-01-24 23:10:24,880 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-01-24 23:10:24,881 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-01-24 23:10:24,882 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-01-24 23:10:24,882 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-01-24 23:10:24,884 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-01-24 23:10:24,885 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-01-24 23:10:24,887 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-01-24 23:10:24,889 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-01-24 23:10:24,891 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-01-24 23:10:24,893 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-01-24 23:10:24,894 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-01-24 23:10:24,896 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-01-24 23:10:24,897 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-01-24 23:10:24,897 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-01-24 23:10:24,898 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-01-24 23:10:24,899 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-01-24 23:10:24,900 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-01-24 23:10:24,900 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-01-24 23:10:24,901 INFO L177 SettingsManager]: PEA to Boogie provides no preferences, ignoring... [2018-01-24 23:10:24,901 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-01-24 23:10:24,902 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-01-24 23:10:24,902 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-01-24 23:10:24,902 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_precise.epf [2018-01-24 23:10:24,911 INFO L110 SettingsManager]: Loading preferences was successful [2018-01-24 23:10:24,911 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-01-24 23:10:24,912 INFO L131 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2018-01-24 23:10:24,912 INFO L133 SettingsManager]: * to procedures, called more than once=true [2018-01-24 23:10:24,912 INFO L131 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2018-01-24 23:10:24,912 INFO L133 SettingsManager]: * Weq Fattening=true [2018-01-24 23:10:24,912 INFO L133 SettingsManager]: * Abstract domain for RCFG-of-the-future=VPDomain [2018-01-24 23:10:24,912 INFO L133 SettingsManager]: * Use the RCFG-of-the-future interface=true [2018-01-24 23:10:24,913 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-01-24 23:10:24,913 INFO L133 SettingsManager]: * sizeof long=4 [2018-01-24 23:10:24,913 INFO L133 SettingsManager]: * Check unreachability of error function in SV-COMP mode=false [2018-01-24 23:10:24,913 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-01-24 23:10:24,913 INFO L133 SettingsManager]: * sizeof POINTER=4 [2018-01-24 23:10:24,914 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-01-24 23:10:24,914 INFO L133 SettingsManager]: * Check for the main procedure if all allocated memory was freed=true [2018-01-24 23:10:24,914 INFO L133 SettingsManager]: * Bitprecise bitfields=true [2018-01-24 23:10:24,914 INFO L133 SettingsManager]: * SV-COMP memtrack compatibility mode=true [2018-01-24 23:10:24,914 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-01-24 23:10:24,914 INFO L133 SettingsManager]: * sizeof long double=12 [2018-01-24 23:10:24,914 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-01-24 23:10:24,914 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-01-24 23:10:24,915 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-01-24 23:10:24,915 INFO L133 SettingsManager]: * Add additional assume for each assert=false [2018-01-24 23:10:24,915 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-01-24 23:10:24,915 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-01-24 23:10:24,915 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-01-24 23:10:24,916 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-01-24 23:10:24,916 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-01-24 23:10:24,916 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-01-24 23:10:24,916 INFO L133 SettingsManager]: * Trace refinement strategy=TAIPAN [2018-01-24 23:10:24,916 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-01-24 23:10:24,916 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-01-24 23:10:24,916 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-01-24 23:10:24,917 INFO L133 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES [2018-01-24 23:10:24,917 INFO L131 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2018-01-24 23:10:24,917 INFO L133 SettingsManager]: * TransformationType=HEAP_SEPARATOR [2018-01-24 23:10:24,967 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-01-24 23:10:24,986 INFO L266 ainManager$Toolchain]: [Toolchain 1]: Parser(s) successfully initialized [2018-01-24 23:10:24,991 INFO L222 ainManager$Toolchain]: [Toolchain 1]: Toolchain data selected. [2018-01-24 23:10:24,993 INFO L271 PluginConnector]: Initializing CDTParser... [2018-01-24 23:10:24,993 INFO L276 PluginConnector]: CDTParser initialized [2018-01-24 23:10:24,995 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-24 23:10:25,214 INFO L304 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-01-24 23:10:25,225 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2018-01-24 23:10:25,226 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2018-01-24 23:10:25,226 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2018-01-24 23:10:25,231 INFO L276 PluginConnector]: CACSL2BoogieTranslator initialized [2018-01-24 23:10:25,232 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 24.01 11:10:25" (1/1) ... [2018-01-24 23:10:25,235 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@29a59f06 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.01 11:10:25, skipping insertion in model container [2018-01-24 23:10:25,235 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 24.01 11:10:25" (1/1) ... [2018-01-24 23:10:25,254 INFO L153 Dispatcher]: Using SV-COMP mode [2018-01-24 23:10:25,332 INFO L153 Dispatcher]: Using SV-COMP mode [2018-01-24 23:10:25,477 INFO L450 PostProcessor]: Settings: Checked method=main [2018-01-24 23:10:25,499 INFO L450 PostProcessor]: Settings: Checked method=main [2018-01-24 23:10:25,507 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.01 11:10:25 WrapperNode [2018-01-24 23:10:25,507 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2018-01-24 23:10:25,508 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-01-24 23:10:25,508 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-01-24 23:10:25,508 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-01-24 23:10:25,525 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.01 11:10:25" (1/1) ... [2018-01-24 23:10:25,525 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.01 11:10:25" (1/1) ... [2018-01-24 23:10:25,537 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.01 11:10:25" (1/1) ... [2018-01-24 23:10:25,537 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.01 11:10:25" (1/1) ... [2018-01-24 23:10:25,541 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.01 11:10:25" (1/1) ... [2018-01-24 23:10:25,544 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.01 11:10:25" (1/1) ... [2018-01-24 23:10:25,545 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.01 11:10:25" (1/1) ... [2018-01-24 23:10:25,547 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-01-24 23:10:25,548 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-01-24 23:10:25,548 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-01-24 23:10:25,548 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-01-24 23:10:25,549 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.01 11:10:25" (1/1) ... No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-01-24 23:10:25,605 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2018-01-24 23:10:25,606 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-01-24 23:10:25,606 INFO L136 BoogieDeclarations]: Found implementation of procedure cstrncat [2018-01-24 23:10:25,606 INFO L136 BoogieDeclarations]: Found implementation of procedure main [2018-01-24 23:10:25,606 INFO L128 BoogieDeclarations]: Found specification of procedure write~int [2018-01-24 23:10:25,606 INFO L128 BoogieDeclarations]: Found specification of procedure read~int [2018-01-24 23:10:25,606 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.free [2018-01-24 23:10:25,606 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2018-01-24 23:10:25,606 INFO L128 BoogieDeclarations]: Found specification of procedure #Ultimate.alloc [2018-01-24 23:10:25,607 INFO L128 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2018-01-24 23:10:25,607 INFO L128 BoogieDeclarations]: Found specification of procedure cstrncat [2018-01-24 23:10:25,607 INFO L128 BoogieDeclarations]: Found specification of procedure main [2018-01-24 23:10:25,607 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2018-01-24 23:10:25,607 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-01-24 23:10:25,875 INFO L257 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-01-24 23:10:25,875 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 24.01 11:10:25 BoogieIcfgContainer [2018-01-24 23:10:25,876 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-01-24 23:10:25,877 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-01-24 23:10:25,877 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-01-24 23:10:25,879 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-01-24 23:10:25,879 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 24.01 11:10:25" (1/3) ... [2018-01-24 23:10:25,880 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@594ee5ab and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 24.01 11:10:25, skipping insertion in model container [2018-01-24 23:10:25,880 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.01 11:10:25" (2/3) ... [2018-01-24 23:10:25,880 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@594ee5ab and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 24.01 11:10:25, skipping insertion in model container [2018-01-24 23:10:25,880 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 24.01 11:10:25" (3/3) ... [2018-01-24 23:10:25,882 INFO L105 eAbstractionObserver]: Analyzing ICFG cstrncat-alloca_true-valid-memsafety_true-termination.i [2018-01-24 23:10:25,888 INFO L130 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-01-24 23:10:25,894 INFO L142 ceAbstractionStarter]: Appying trace abstraction to program that has 15 error locations. [2018-01-24 23:10:25,950 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-24 23:10:25,950 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-24 23:10:25,950 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-24 23:10:25,950 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-24 23:10:25,950 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-24 23:10:25,951 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-24 23:10:25,951 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-24 23:10:25,960 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-01-24 23:10:25,961 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-24 23:10:25,996 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states. [2018-01-24 23:10:26,004 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2018-01-24 23:10:26,004 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 23:10:26,005 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-24 23:10:26,005 INFO L371 AbstractCegarLoop]: === Iteration 1 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 23:10:26,011 INFO L82 PathProgramCache]: Analyzing trace with hash 1927484354, now seen corresponding path program 1 times [2018-01-24 23:10:26,014 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 23:10:26,073 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 23:10:26,073 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 23:10:26,074 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 23:10:26,074 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 23:10:26,139 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 23:10:26,146 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 23:10:26,207 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-24 23:10:26,209 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 23:10:26,209 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-01-24 23:10:26,209 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-24 23:10:26,211 INFO L409 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-01-24 23:10:26,222 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-01-24 23:10:26,223 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-24 23:10:26,225 INFO L87 Difference]: Start difference. First operand 58 states. Second operand 3 states. [2018-01-24 23:10:26,533 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 23:10:26,533 INFO L93 Difference]: Finished difference Result 90 states and 103 transitions. [2018-01-24 23:10:26,534 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-01-24 23:10:26,535 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 11 [2018-01-24 23:10:26,536 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 23:10:26,550 INFO L225 Difference]: With dead ends: 90 [2018-01-24 23:10:26,550 INFO L226 Difference]: Without dead ends: 55 [2018-01-24 23:10:26,554 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-24 23:10:26,577 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2018-01-24 23:10:26,595 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 55. [2018-01-24 23:10:26,597 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 55 states. [2018-01-24 23:10:26,600 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 61 transitions. [2018-01-24 23:10:26,602 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 61 transitions. Word has length 11 [2018-01-24 23:10:26,603 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 23:10:26,603 INFO L432 AbstractCegarLoop]: Abstraction has 55 states and 61 transitions. [2018-01-24 23:10:26,603 INFO L433 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-01-24 23:10:26,603 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 61 transitions. [2018-01-24 23:10:26,604 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2018-01-24 23:10:26,604 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 23:10:26,604 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-24 23:10:26,604 INFO L371 AbstractCegarLoop]: === Iteration 2 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 23:10:26,604 INFO L82 PathProgramCache]: Analyzing trace with hash 1621249811, now seen corresponding path program 1 times [2018-01-24 23:10:26,604 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 23:10:26,605 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 23:10:26,606 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 23:10:26,606 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 23:10:26,606 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 23:10:26,618 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 23:10:26,619 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 23:10:26,686 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-24 23:10:26,686 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 23:10:26,687 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-01-24 23:10:26,687 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-24 23:10:26,688 INFO L409 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-01-24 23:10:26,689 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-01-24 23:10:26,689 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-01-24 23:10:26,689 INFO L87 Difference]: Start difference. First operand 55 states and 61 transitions. Second operand 5 states. [2018-01-24 23:10:26,790 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 23:10:26,791 INFO L93 Difference]: Finished difference Result 103 states and 114 transitions. [2018-01-24 23:10:26,791 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-01-24 23:10:26,791 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 15 [2018-01-24 23:10:26,792 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 23:10:26,793 INFO L225 Difference]: With dead ends: 103 [2018-01-24 23:10:26,793 INFO L226 Difference]: Without dead ends: 55 [2018-01-24 23:10:26,795 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-24 23:10:26,795 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2018-01-24 23:10:26,800 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 55. [2018-01-24 23:10:26,801 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 55 states. [2018-01-24 23:10:26,802 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 60 transitions. [2018-01-24 23:10:26,803 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 60 transitions. Word has length 15 [2018-01-24 23:10:26,803 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 23:10:26,803 INFO L432 AbstractCegarLoop]: Abstraction has 55 states and 60 transitions. [2018-01-24 23:10:26,803 INFO L433 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-01-24 23:10:26,803 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 60 transitions. [2018-01-24 23:10:26,804 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2018-01-24 23:10:26,804 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 23:10:26,804 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-24 23:10:26,804 INFO L371 AbstractCegarLoop]: === Iteration 3 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 23:10:26,805 INFO L82 PathProgramCache]: Analyzing trace with hash -1993659115, now seen corresponding path program 1 times [2018-01-24 23:10:26,805 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 23:10:26,806 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 23:10:26,806 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 23:10:26,806 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 23:10:26,806 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 23:10:26,827 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 23:10:26,828 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 23:10:26,901 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-24 23:10:26,902 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 23:10:26,902 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-01-24 23:10:26,902 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-24 23:10:26,902 INFO L409 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-01-24 23:10:26,903 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-01-24 23:10:26,903 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-01-24 23:10:26,903 INFO L87 Difference]: Start difference. First operand 55 states and 60 transitions. Second operand 4 states. [2018-01-24 23:10:26,962 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 23:10:26,962 INFO L93 Difference]: Finished difference Result 55 states and 60 transitions. [2018-01-24 23:10:26,963 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-01-24 23:10:26,963 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 15 [2018-01-24 23:10:26,963 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 23:10:26,964 INFO L225 Difference]: With dead ends: 55 [2018-01-24 23:10:26,964 INFO L226 Difference]: Without dead ends: 54 [2018-01-24 23:10:26,965 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-24 23:10:26,965 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2018-01-24 23:10:26,970 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 54. [2018-01-24 23:10:26,970 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 54 states. [2018-01-24 23:10:26,972 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 59 transitions. [2018-01-24 23:10:26,972 INFO L78 Accepts]: Start accepts. Automaton has 54 states and 59 transitions. Word has length 15 [2018-01-24 23:10:26,972 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 23:10:26,972 INFO L432 AbstractCegarLoop]: Abstraction has 54 states and 59 transitions. [2018-01-24 23:10:26,972 INFO L433 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-01-24 23:10:26,972 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states and 59 transitions. [2018-01-24 23:10:26,973 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2018-01-24 23:10:26,973 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 23:10:26,973 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-24 23:10:26,973 INFO L371 AbstractCegarLoop]: === Iteration 4 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 23:10:26,973 INFO L82 PathProgramCache]: Analyzing trace with hash -1993659114, now seen corresponding path program 1 times [2018-01-24 23:10:26,973 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 23:10:26,974 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 23:10:26,974 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 23:10:26,974 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 23:10:26,974 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 23:10:26,987 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 23:10:26,987 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 23:10:27,163 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-24 23:10:27,164 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 23:10:27,206 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2018-01-24 23:10:27,206 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-24 23:10:27,206 INFO L409 AbstractCegarLoop]: Interpolant automaton has 8 states [2018-01-24 23:10:27,207 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2018-01-24 23:10:27,207 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=38, Unknown=0, NotChecked=0, Total=56 [2018-01-24 23:10:27,207 INFO L87 Difference]: Start difference. First operand 54 states and 59 transitions. Second operand 8 states. [2018-01-24 23:10:27,319 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 23:10:27,319 INFO L93 Difference]: Finished difference Result 54 states and 59 transitions. [2018-01-24 23:10:27,320 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-01-24 23:10:27,320 INFO L78 Accepts]: Start accepts. Automaton has 8 states. Word has length 15 [2018-01-24 23:10:27,320 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 23:10:27,321 INFO L225 Difference]: With dead ends: 54 [2018-01-24 23:10:27,321 INFO L226 Difference]: Without dead ends: 53 [2018-01-24 23:10:27,321 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-24 23:10:27,322 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 53 states. [2018-01-24 23:10:27,325 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 53 to 53. [2018-01-24 23:10:27,325 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 53 states. [2018-01-24 23:10:27,326 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 53 states to 53 states and 58 transitions. [2018-01-24 23:10:27,326 INFO L78 Accepts]: Start accepts. Automaton has 53 states and 58 transitions. Word has length 15 [2018-01-24 23:10:27,327 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 23:10:27,327 INFO L432 AbstractCegarLoop]: Abstraction has 53 states and 58 transitions. [2018-01-24 23:10:27,327 INFO L433 AbstractCegarLoop]: Interpolant automaton has 8 states. [2018-01-24 23:10:27,327 INFO L276 IsEmpty]: Start isEmpty. Operand 53 states and 58 transitions. [2018-01-24 23:10:27,327 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2018-01-24 23:10:27,327 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 23:10:27,328 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-24 23:10:27,329 INFO L371 AbstractCegarLoop]: === Iteration 5 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 23:10:27,329 INFO L82 PathProgramCache]: Analyzing trace with hash -1673890416, now seen corresponding path program 1 times [2018-01-24 23:10:27,330 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 23:10:27,330 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 23:10:27,331 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 23:10:27,331 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 23:10:27,331 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 23:10:27,345 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 23:10:27,347 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 23:10:27,381 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-24 23:10:27,381 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 23:10:27,382 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-01-24 23:10:27,382 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-24 23:10:27,382 INFO L409 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-01-24 23:10:27,382 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-01-24 23:10:27,382 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-01-24 23:10:27,383 INFO L87 Difference]: Start difference. First operand 53 states and 58 transitions. Second operand 4 states. [2018-01-24 23:10:27,435 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 23:10:27,435 INFO L93 Difference]: Finished difference Result 53 states and 58 transitions. [2018-01-24 23:10:27,436 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-01-24 23:10:27,436 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 16 [2018-01-24 23:10:27,436 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 23:10:27,437 INFO L225 Difference]: With dead ends: 53 [2018-01-24 23:10:27,437 INFO L226 Difference]: Without dead ends: 52 [2018-01-24 23:10:27,437 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-24 23:10:27,437 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 52 states. [2018-01-24 23:10:27,442 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 52 to 52. [2018-01-24 23:10:27,442 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 52 states. [2018-01-24 23:10:27,443 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 52 states to 52 states and 57 transitions. [2018-01-24 23:10:27,443 INFO L78 Accepts]: Start accepts. Automaton has 52 states and 57 transitions. Word has length 16 [2018-01-24 23:10:27,444 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 23:10:27,444 INFO L432 AbstractCegarLoop]: Abstraction has 52 states and 57 transitions. [2018-01-24 23:10:27,444 INFO L433 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-01-24 23:10:27,444 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 57 transitions. [2018-01-24 23:10:27,445 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2018-01-24 23:10:27,445 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 23:10:27,445 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-24 23:10:27,445 INFO L371 AbstractCegarLoop]: === Iteration 6 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 23:10:27,445 INFO L82 PathProgramCache]: Analyzing trace with hash -1673890415, now seen corresponding path program 1 times [2018-01-24 23:10:27,446 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 23:10:27,446 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 23:10:27,447 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 23:10:27,447 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 23:10:27,447 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 23:10:27,458 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 23:10:27,459 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 23:10:27,548 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-24 23:10:27,548 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 23:10:27,548 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-01-24 23:10:27,549 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-24 23:10:27,549 INFO L409 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-01-24 23:10:27,549 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-01-24 23:10:27,550 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-01-24 23:10:27,550 INFO L87 Difference]: Start difference. First operand 52 states and 57 transitions. Second operand 5 states. [2018-01-24 23:10:27,584 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 23:10:27,584 INFO L93 Difference]: Finished difference Result 52 states and 57 transitions. [2018-01-24 23:10:27,585 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-01-24 23:10:27,585 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 16 [2018-01-24 23:10:27,585 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 23:10:27,586 INFO L225 Difference]: With dead ends: 52 [2018-01-24 23:10:27,586 INFO L226 Difference]: Without dead ends: 51 [2018-01-24 23:10:27,586 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-24 23:10:27,586 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2018-01-24 23:10:27,590 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 51. [2018-01-24 23:10:27,590 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 51 states. [2018-01-24 23:10:27,591 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 56 transitions. [2018-01-24 23:10:27,591 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 56 transitions. Word has length 16 [2018-01-24 23:10:27,591 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 23:10:27,591 INFO L432 AbstractCegarLoop]: Abstraction has 51 states and 56 transitions. [2018-01-24 23:10:27,592 INFO L433 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-01-24 23:10:27,592 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 56 transitions. [2018-01-24 23:10:27,592 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2018-01-24 23:10:27,592 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 23:10:27,592 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-24 23:10:27,592 INFO L371 AbstractCegarLoop]: === Iteration 7 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 23:10:27,592 INFO L82 PathProgramCache]: Analyzing trace with hash 1745382581, now seen corresponding path program 1 times [2018-01-24 23:10:27,593 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 23:10:27,593 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 23:10:27,593 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 23:10:27,593 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 23:10:27,594 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 23:10:27,609 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 23:10:27,610 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 23:10:27,696 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-24 23:10:27,696 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 23:10:27,697 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-01-24 23:10:27,697 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-24 23:10:27,697 INFO L409 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-01-24 23:10:27,697 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-01-24 23:10:27,698 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-01-24 23:10:27,698 INFO L87 Difference]: Start difference. First operand 51 states and 56 transitions. Second operand 5 states. [2018-01-24 23:10:27,769 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 23:10:27,769 INFO L93 Difference]: Finished difference Result 51 states and 56 transitions. [2018-01-24 23:10:27,770 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-01-24 23:10:27,770 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 20 [2018-01-24 23:10:27,770 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 23:10:27,770 INFO L225 Difference]: With dead ends: 51 [2018-01-24 23:10:27,771 INFO L226 Difference]: Without dead ends: 47 [2018-01-24 23:10:27,771 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-24 23:10:27,771 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2018-01-24 23:10:27,774 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 47. [2018-01-24 23:10:27,774 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 47 states. [2018-01-24 23:10:27,775 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 47 states to 47 states and 52 transitions. [2018-01-24 23:10:27,775 INFO L78 Accepts]: Start accepts. Automaton has 47 states and 52 transitions. Word has length 20 [2018-01-24 23:10:27,775 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 23:10:27,775 INFO L432 AbstractCegarLoop]: Abstraction has 47 states and 52 transitions. [2018-01-24 23:10:27,775 INFO L433 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-01-24 23:10:27,775 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 52 transitions. [2018-01-24 23:10:27,776 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2018-01-24 23:10:27,776 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 23:10:27,776 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-24 23:10:27,776 INFO L371 AbstractCegarLoop]: === Iteration 8 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 23:10:27,776 INFO L82 PathProgramCache]: Analyzing trace with hash 1745382582, now seen corresponding path program 1 times [2018-01-24 23:10:27,777 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 23:10:27,777 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 23:10:27,777 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 23:10:27,777 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 23:10:27,778 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 23:10:27,790 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 23:10:27,791 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 23:10:27,897 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-24 23:10:27,897 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 23:10:27,897 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2018-01-24 23:10:27,898 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-24 23:10:27,898 INFO L409 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-01-24 23:10:27,898 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-01-24 23:10:27,898 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2018-01-24 23:10:27,899 INFO L87 Difference]: Start difference. First operand 47 states and 52 transitions. Second operand 9 states. [2018-01-24 23:10:28,105 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 23:10:28,105 INFO L93 Difference]: Finished difference Result 69 states and 78 transitions. [2018-01-24 23:10:28,105 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-01-24 23:10:28,106 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 20 [2018-01-24 23:10:28,106 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 23:10:28,109 INFO L225 Difference]: With dead ends: 69 [2018-01-24 23:10:28,109 INFO L226 Difference]: Without dead ends: 65 [2018-01-24 23:10:28,109 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-24 23:10:28,109 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 65 states. [2018-01-24 23:10:28,113 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 65 to 60. [2018-01-24 23:10:28,113 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 60 states. [2018-01-24 23:10:28,115 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 60 states to 60 states and 71 transitions. [2018-01-24 23:10:28,115 INFO L78 Accepts]: Start accepts. Automaton has 60 states and 71 transitions. Word has length 20 [2018-01-24 23:10:28,115 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 23:10:28,115 INFO L432 AbstractCegarLoop]: Abstraction has 60 states and 71 transitions. [2018-01-24 23:10:28,115 INFO L433 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-01-24 23:10:28,116 INFO L276 IsEmpty]: Start isEmpty. Operand 60 states and 71 transitions. [2018-01-24 23:10:28,116 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2018-01-24 23:10:28,116 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 23:10:28,117 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-24 23:10:28,117 INFO L371 AbstractCegarLoop]: === Iteration 9 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 23:10:28,117 INFO L82 PathProgramCache]: Analyzing trace with hash 1818413707, now seen corresponding path program 1 times [2018-01-24 23:10:28,117 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 23:10:28,118 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 23:10:28,118 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 23:10:28,118 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 23:10:28,118 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 23:10:28,130 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 23:10:28,131 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 23:10:28,408 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-24 23:10:28,408 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-24 23:10:28,408 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-01-24 23:10:28,409 INFO L199 CegarAbsIntRunner]: Running AI on error trace of length 24 with the following transitions: [2018-01-24 23:10:28,412 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-24 23:10:28,466 INFO L147 AbstractInterpreter]: Using domain VPDomain [2018-01-24 23:10:28,466 INFO L101 FixpointEngine]: Starting fixpoint engine with domain VPDomain (maxUnwinding=3, maxParallelStates=2) [2018-01-24 23:10:58,028 INFO L259 AbstractInterpreter]: Some error location(s) were reachable [2018-01-24 23:10:58,030 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-24 23:10:58,047 INFO L434 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: Unknown [2018-01-24 23:10:58,047 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-24 23:10:58,047 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-24 23:10:58,062 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 23:10:58,062 INFO L280 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-01-24 23:10:58,089 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 23:10:58,100 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-24 23:10:58,244 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-24 23:10:58,245 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 23:10:58,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-24 23:10:58,254 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 23:10:58,263 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-24 23:10:58,264 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:24, output treesize:19 [2018-01-24 23:10:58,365 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 23:10:58,366 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 23:10:58,366 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-24 23:10:58,366 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 23:10:58,380 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 23:10:58,381 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 23 [2018-01-24 23:10:58,382 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 23:10:58,395 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-24 23:10:58,395 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:30, output treesize:18 [2018-01-24 23:10:58,775 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-24 23:10:58,775 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-01-24 23:10:59,025 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-24 23:10:59,025 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 23:10:59,033 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-24 23:10:59,049 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-24 23:10:59,049 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-24 23:10:59,056 WARN L307 Elim1Store]: Array PQE input equivalent to true [2018-01-24 23:10:59,057 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-24 23:10:59,065 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 23:10:59,069 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-24 23:10:59,069 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 4 variables, input treesize:21, output treesize:3 [2018-01-24 23:10:59,104 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-24 23:10:59,133 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-24 23:10:59,133 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-24 23:10:59,137 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 23:10:59,137 INFO L280 anRefinementStrategy]: Using traceCheck mode CVC4_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-01-24 23:10:59,168 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 23:10:59,173 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-24 23:10:59,194 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-24 23:10:59,195 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 23:10:59,203 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-24 23:10:59,203 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 23:10:59,211 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-24 23:10:59,211 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:24, output treesize:19 [2018-01-24 23:10:59,271 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 23:10:59,272 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 23:10:59,272 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-24 23:10:59,273 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 23:10:59,285 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 23:10:59,286 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 23:10:59,286 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-24 23:10:59,286 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 23:10:59,309 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-24 23:10:59,310 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:30, output treesize:18 [2018-01-24 23:10:59,398 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-24 23:10:59,398 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-01-24 23:10:59,447 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-24 23:10:59,447 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 23:10:59,452 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-24 23:10:59,464 WARN L307 Elim1Store]: Array PQE input equivalent to true [2018-01-24 23:10:59,464 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-24 23:10:59,466 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-24 23:10:59,466 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-24 23:10:59,470 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 23:10:59,473 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-24 23:10:59,473 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 4 variables, input treesize:21, output treesize:3 [2018-01-24 23:10:59,538 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-24 23:10:59,540 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 5 imperfect interpolant sequences. [2018-01-24 23:10:59,540 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 12, 11, 11, 11] total 34 [2018-01-24 23:10:59,540 INFO L247 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-01-24 23:10:59,540 INFO L409 AbstractCegarLoop]: Interpolant automaton has 22 states [2018-01-24 23:10:59,540 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2018-01-24 23:10:59,541 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=137, Invalid=1053, Unknown=0, NotChecked=0, Total=1190 [2018-01-24 23:10:59,541 INFO L87 Difference]: Start difference. First operand 60 states and 71 transitions. Second operand 22 states. [2018-01-24 23:11:00,092 WARN L146 SmtUtils]: Spent 102ms on a formula simplification. DAG size of input: 26 DAG size of output 23 [2018-01-24 23:11:00,566 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 23:11:00,567 INFO L93 Difference]: Finished difference Result 87 states and 100 transitions. [2018-01-24 23:11:00,567 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-01-24 23:11:00,567 INFO L78 Accepts]: Start accepts. Automaton has 22 states. Word has length 23 [2018-01-24 23:11:00,567 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 23:11:00,568 INFO L225 Difference]: With dead ends: 87 [2018-01-24 23:11:00,569 INFO L226 Difference]: Without dead ends: 83 [2018-01-24 23:11:00,570 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 111 GetRequests, 62 SyntacticMatches, 8 SemanticMatches, 41 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 501 ImplicationChecksByTransitivity, 1.7s TimeCoverageRelationStatistics Valid=263, Invalid=1543, Unknown=0, NotChecked=0, Total=1806 [2018-01-24 23:11:00,570 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 83 states. [2018-01-24 23:11:00,577 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 83 to 70. [2018-01-24 23:11:00,577 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 70 states. [2018-01-24 23:11:00,578 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 70 states to 70 states and 86 transitions. [2018-01-24 23:11:00,579 INFO L78 Accepts]: Start accepts. Automaton has 70 states and 86 transitions. Word has length 23 [2018-01-24 23:11:00,579 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 23:11:00,579 INFO L432 AbstractCegarLoop]: Abstraction has 70 states and 86 transitions. [2018-01-24 23:11:00,579 INFO L433 AbstractCegarLoop]: Interpolant automaton has 22 states. [2018-01-24 23:11:00,579 INFO L276 IsEmpty]: Start isEmpty. Operand 70 states and 86 transitions. [2018-01-24 23:11:00,580 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2018-01-24 23:11:00,580 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 23:11:00,580 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-24 23:11:00,580 INFO L371 AbstractCegarLoop]: === Iteration 10 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 23:11:00,581 INFO L82 PathProgramCache]: Analyzing trace with hash -557502487, now seen corresponding path program 1 times [2018-01-24 23:11:00,581 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 23:11:00,582 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 23:11:00,582 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 23:11:00,582 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 23:11:00,582 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 23:11:00,596 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 23:11:00,596 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 23:11:00,734 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-24 23:11:00,734 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 23:11:00,734 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-01-24 23:11:00,734 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-24 23:11:00,734 INFO L409 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-01-24 23:11:00,735 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-01-24 23:11:00,735 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2018-01-24 23:11:00,735 INFO L87 Difference]: Start difference. First operand 70 states and 86 transitions. Second operand 6 states. [2018-01-24 23:11:00,797 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 23:11:00,797 INFO L93 Difference]: Finished difference Result 73 states and 92 transitions. [2018-01-24 23:11:00,797 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-01-24 23:11:00,797 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 25 [2018-01-24 23:11:00,798 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 23:11:00,799 INFO L225 Difference]: With dead ends: 73 [2018-01-24 23:11:00,799 INFO L226 Difference]: Without dead ends: 72 [2018-01-24 23:11:00,800 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-24 23:11:00,800 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 72 states. [2018-01-24 23:11:00,808 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 72 to 69. [2018-01-24 23:11:00,808 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 69 states. [2018-01-24 23:11:00,809 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 69 states to 69 states and 83 transitions. [2018-01-24 23:11:00,809 INFO L78 Accepts]: Start accepts. Automaton has 69 states and 83 transitions. Word has length 25 [2018-01-24 23:11:00,809 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 23:11:00,809 INFO L432 AbstractCegarLoop]: Abstraction has 69 states and 83 transitions. [2018-01-24 23:11:00,810 INFO L433 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-01-24 23:11:00,810 INFO L276 IsEmpty]: Start isEmpty. Operand 69 states and 83 transitions. [2018-01-24 23:11:00,810 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2018-01-24 23:11:00,811 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 23:11:00,811 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-24 23:11:00,811 INFO L371 AbstractCegarLoop]: === Iteration 11 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 23:11:00,811 INFO L82 PathProgramCache]: Analyzing trace with hash -557502486, now seen corresponding path program 1 times [2018-01-24 23:11:00,811 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 23:11:00,812 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 23:11:00,812 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 23:11:00,812 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 23:11:00,813 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 23:11:00,824 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 23:11:00,825 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 23:11:00,923 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-24 23:11:00,923 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 23:11:00,923 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2018-01-24 23:11:00,923 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-24 23:11:00,924 INFO L409 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-01-24 23:11:00,924 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-01-24 23:11:00,924 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=54, Unknown=0, NotChecked=0, Total=72 [2018-01-24 23:11:00,925 INFO L87 Difference]: Start difference. First operand 69 states and 83 transitions. Second operand 9 states. [2018-01-24 23:11:01,254 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 23:11:01,254 INFO L93 Difference]: Finished difference Result 99 states and 123 transitions. [2018-01-24 23:11:01,255 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-01-24 23:11:01,255 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 25 [2018-01-24 23:11:01,255 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 23:11:01,256 INFO L225 Difference]: With dead ends: 99 [2018-01-24 23:11:01,256 INFO L226 Difference]: Without dead ends: 98 [2018-01-24 23:11:01,256 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 18 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=32, Invalid=100, Unknown=0, NotChecked=0, Total=132 [2018-01-24 23:11:01,256 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 98 states. [2018-01-24 23:11:01,264 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 98 to 80. [2018-01-24 23:11:01,264 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 80 states. [2018-01-24 23:11:01,265 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 80 states to 80 states and 98 transitions. [2018-01-24 23:11:01,266 INFO L78 Accepts]: Start accepts. Automaton has 80 states and 98 transitions. Word has length 25 [2018-01-24 23:11:01,266 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 23:11:01,266 INFO L432 AbstractCegarLoop]: Abstraction has 80 states and 98 transitions. [2018-01-24 23:11:01,266 INFO L433 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-01-24 23:11:01,266 INFO L276 IsEmpty]: Start isEmpty. Operand 80 states and 98 transitions. [2018-01-24 23:11:01,267 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2018-01-24 23:11:01,267 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 23:11:01,267 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-24 23:11:01,267 INFO L371 AbstractCegarLoop]: === Iteration 12 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 23:11:01,268 INFO L82 PathProgramCache]: Analyzing trace with hash -59760490, now seen corresponding path program 2 times [2018-01-24 23:11:01,268 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 23:11:01,269 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 23:11:01,269 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 23:11:01,269 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 23:11:01,269 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 23:11:01,285 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 23:11:01,286 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 23:11:01,899 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-24 23:11:01,900 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-24 23:11:01,900 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-01-24 23:11:01,900 INFO L183 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-01-24 23:11:01,900 INFO L434 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-01-24 23:11:01,900 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-24 23:11:01,900 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-24 23:11:01,915 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-01-24 23:11:01,915 INFO L280 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST1 (IT: FPandBP) [2018-01-24 23:11:01,934 INFO L201 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-24 23:11:01,938 INFO L214 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-24 23:11:01,940 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-24 23:11:01,943 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-24 23:11:02,024 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-24 23:11:02,025 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 23:11:02,034 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-24 23:11:02,034 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 23:11:02,075 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 23:11:02,075 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:27, output treesize:25 [2018-01-24 23:11:02,188 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 23:11:02,210 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 23:11:02,211 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 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-24 23:11:02,212 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 23:11:02,400 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 23:11:02,425 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 23:11:02,426 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-24 23:11:02,426 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 23:11:02,510 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 23:11:02,511 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:36, output treesize:25 [2018-01-24 23:11:02,614 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-24 23:11:02,627 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-24 23:11:02,628 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 23:11:02,630 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 23:11:02,642 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-24 23:11:02,642 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:41, output treesize:37 [2018-01-24 23:11:02,706 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 23:11:02,710 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-24 23:11:02,727 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-24 23:11:02,728 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 23:11:02,779 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 23:11:02,789 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-24 23:11:02,789 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:52, output treesize:48 [2018-01-24 23:11:02,927 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 23:11:02,954 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 34 treesize of output 32 [2018-01-24 23:11:02,976 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-24 23:11:02,977 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-24 23:11:02,989 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-24 23:11:02,989 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-24 23:11:03,006 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-24 23:11:03,017 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-24 23:11:03,017 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 4 variables, input treesize:54, output treesize:69 [2018-01-24 23:11:03,232 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-24 23:11:03,232 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-01-24 23:11:03,586 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-24 23:11:03,597 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-24 23:11:03,597 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 23:11:03,601 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 23:11:03,603 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-24 23:11:03,619 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-24 23:11:03,619 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-24 23:11:03,622 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 23:11:03,631 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 2 xjuncts. [2018-01-24 23:11:03,631 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 1 variables, input treesize:47, output treesize:25 [2018-01-24 23:11:03,807 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-24 23:11:03,808 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 23:11:03,812 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-24 23:11:03,820 WARN L307 Elim1Store]: Array PQE input equivalent to true [2018-01-24 23:11:03,820 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-24 23:11:03,822 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-24 23:11:03,822 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-24 23:11:03,825 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 23:11:03,829 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-24 23:11:03,829 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 4 variables, input treesize:26, output treesize:9 [2018-01-24 23:11:03,906 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-24 23:11:03,927 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-24 23:11:03,928 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-24 23:11:03,931 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-01-24 23:11:03,931 INFO L280 anRefinementStrategy]: Using traceCheck mode CVC4_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST1 (IT: FPandBP) [2018-01-24 23:11:03,948 INFO L201 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-24 23:11:03,977 INFO L214 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-24 23:11:04,013 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-24 23:11:04,021 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-24 23:11:04,061 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-24 23:11:04,061 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 23:11:04,071 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-24 23:11:04,071 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 23:11:04,080 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 23:11:04,080 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:19, output treesize:17 [2018-01-24 23:11:04,174 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 23:11:04,174 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 23:11:04,175 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-24 23:11:04,175 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 23:11:04,189 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-24 23:11:04,190 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 23:11:04,198 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 23:11:04,198 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:28, output treesize:21 [2018-01-24 23:11:04,268 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-24 23:11:04,269 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-24 23:11:04,270 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 23:11:04,271 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 23:11:04,275 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-24 23:11:04,275 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:29, output treesize:25 [2018-01-24 23:11:04,317 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-24 23:11:04,319 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-24 23:11:04,319 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 23:11:04,324 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 23:11:04,330 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-24 23:11:04,330 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:36, output treesize:32 [2018-01-24 23:11:04,490 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-24 23:11:04,500 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-24 23:11:04,501 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-24 23:11:04,513 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 1 [2018-01-24 23:11:04,514 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-24 23:11:04,516 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-24 23:11:04,522 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-24 23:11:04,522 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 3 variables, input treesize:38, output treesize:20 [2018-01-24 23:11:04,682 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-24 23:11:04,682 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-01-24 23:11:04,965 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-24 23:11:04,975 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-24 23:11:04,976 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 23:11:04,978 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 23:11:04,983 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-24 23:11:04,983 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:36, output treesize:25 [2018-01-24 23:11:05,999 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-24 23:11:05,999 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 23:11:06,005 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-24 23:11:06,018 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 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-24 23:11:06,018 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-24 23:11:06,019 WARN L307 Elim1Store]: Array PQE input equivalent to true [2018-01-24 23:11:06,019 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-24 23:11:06,024 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 23:11:06,030 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-24 23:11:06,030 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 6 variables, input treesize:37, output treesize:7 [2018-01-24 23:11:06,057 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-24 23:11:06,058 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 5 imperfect interpolant sequences. [2018-01-24 23:11:06,058 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 15, 13, 14, 12] total 58 [2018-01-24 23:11:06,058 INFO L247 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-01-24 23:11:06,059 INFO L409 AbstractCegarLoop]: Interpolant automaton has 27 states [2018-01-24 23:11:06,059 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2018-01-24 23:11:06,060 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=245, Invalid=3176, Unknown=1, NotChecked=0, Total=3422 [2018-01-24 23:11:06,060 INFO L87 Difference]: Start difference. First operand 80 states and 98 transitions. Second operand 27 states. [2018-01-24 23:11:10,946 WARN L146 SmtUtils]: Spent 111ms on a formula simplification. DAG size of input: 50 DAG size of output 36 [2018-01-24 23:11:11,236 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 23:11:11,237 INFO L93 Difference]: Finished difference Result 183 states and 220 transitions. [2018-01-24 23:11:11,237 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2018-01-24 23:11:11,237 INFO L78 Accepts]: Start accepts. Automaton has 27 states. Word has length 26 [2018-01-24 23:11:11,237 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 23:11:11,239 INFO L225 Difference]: With dead ends: 183 [2018-01-24 23:11:11,239 INFO L226 Difference]: Without dead ends: 179 [2018-01-24 23:11:11,241 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 134 GetRequests, 53 SyntacticMatches, 6 SemanticMatches, 75 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1505 ImplicationChecksByTransitivity, 4.5s TimeCoverageRelationStatistics Valid=611, Invalid=5240, Unknown=1, NotChecked=0, Total=5852 [2018-01-24 23:11:11,241 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 179 states. [2018-01-24 23:11:11,248 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 179 to 83. [2018-01-24 23:11:11,248 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 83 states. [2018-01-24 23:11:11,249 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 83 states to 83 states and 102 transitions. [2018-01-24 23:11:11,249 INFO L78 Accepts]: Start accepts. Automaton has 83 states and 102 transitions. Word has length 26 [2018-01-24 23:11:11,249 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 23:11:11,249 INFO L432 AbstractCegarLoop]: Abstraction has 83 states and 102 transitions. [2018-01-24 23:11:11,249 INFO L433 AbstractCegarLoop]: Interpolant automaton has 27 states. [2018-01-24 23:11:11,249 INFO L276 IsEmpty]: Start isEmpty. Operand 83 states and 102 transitions. [2018-01-24 23:11:11,250 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2018-01-24 23:11:11,250 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 23:11:11,250 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-24 23:11:11,250 INFO L371 AbstractCegarLoop]: === Iteration 13 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 23:11:11,251 INFO L82 PathProgramCache]: Analyzing trace with hash 2086668971, now seen corresponding path program 3 times [2018-01-24 23:11:11,251 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 23:11:11,251 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 23:11:11,252 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-01-24 23:11:11,252 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 23:11:11,252 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 23:11:11,267 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 23:11:11,268 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 23:11:11,595 WARN L146 SmtUtils]: Spent 201ms on a formula simplification. DAG size of input: 33 DAG size of output 27 [2018-01-24 23:11:11,917 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-24 23:11:11,917 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-24 23:11:11,918 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-01-24 23:11:11,918 INFO L183 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-01-24 23:11:11,918 INFO L434 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-01-24 23:11:11,918 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-24 23:11:11,918 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-24 23:11:11,927 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-01-24 23:11:11,927 INFO L280 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST2 (IT: FPandBP) [2018-01-24 23:11:11,939 INFO L254 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued a check-sat command [2018-01-24 23:11:11,943 INFO L254 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued a check-sat command [2018-01-24 23:11:11,945 INFO L254 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued a check-sat command [2018-01-24 23:11:11,948 INFO L254 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued a check-sat command [2018-01-24 23:11:11,949 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-24 23:11:11,952 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-24 23:11:11,956 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-24 23:11:11,957 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 23:11:11,964 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-24 23:11:11,964 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 23:11:11,970 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 23:11:11,970 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:22, output treesize:20 [2018-01-24 23:11:11,997 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 23:11:11,998 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-24 23:11:11,998 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 23:11:12,008 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 23:11:12,009 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 23:11:12,009 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-24 23:11:12,009 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 23:11:12,015 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 23:11:12,016 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:31, output treesize:24 [2018-01-24 23:11:12,059 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-24 23:11:12,061 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-24 23:11:12,061 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 23:11:12,064 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 23:11:12,072 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-24 23:11:12,073 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:34, output treesize:30 [2018-01-24 23:11:12,103 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-24 23:11:12,104 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-24 23:11:12,105 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 23:11:12,109 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 23:11:12,118 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-24 23:11:12,118 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:41, output treesize:37 [2018-01-24 23:11:12,252 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-24 23:11:12,258 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-24 23:11:12,259 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-24 23:11:12,266 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-24 23:11:12,266 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-24 23:11:12,269 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-24 23:11:12,276 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-24 23:11:12,276 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 4 variables, input treesize:44, output treesize:18 [2018-01-24 23:11:12,341 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-24 23:11:12,341 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-01-24 23:11:12,628 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-24 23:11:12,637 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 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-24 23:11:12,637 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 23:11:12,639 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 23:11:12,644 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-24 23:11:12,644 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:36, output treesize:39 [2018-01-24 23:11:13,066 WARN L143 SmtUtils]: Spent 323ms on a formula simplification that was a NOOP. DAG size: 36 [2018-01-24 23:11:13,519 WARN L143 SmtUtils]: Spent 383ms on a formula simplification that was a NOOP. DAG size: 36 [2018-01-24 23:11:13,540 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 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-24 23:11:13,540 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 23:11:13,553 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-24 23:11:13,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, 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-24 23:11:13,574 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-24 23:11:13,579 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 23:11:13,592 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-24 23:11:13,623 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-24 23:11:13,623 INFO L267 ElimStorePlain]: Start of recursive call 6: End of recursive call: and 1 xjuncts. [2018-01-24 23:11:13,628 INFO L267 ElimStorePlain]: Start of recursive call 5: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 23:11:13,638 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-24 23:11:13,638 INFO L267 ElimStorePlain]: Start of recursive call 7: End of recursive call: and 1 xjuncts. [2018-01-24 23:11:13,646 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-24 23:11:13,647 INFO L202 ElimStorePlain]: Needed 7 recursive calls to eliminate 12 variables, input treesize:71, output treesize:7 [2018-01-24 23:11:13,653 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-24 23:11:13,674 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-24 23:11:13,675 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-24 23:11:13,678 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-01-24 23:11:13,678 INFO L280 anRefinementStrategy]: Using traceCheck mode CVC4_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST2 (IT: FPandBP) [2018-01-24 23:11:13,695 INFO L254 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued a check-sat command [2018-01-24 23:11:13,734 INFO L254 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued a check-sat command [2018-01-24 23:11:13,771 INFO L254 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued a check-sat command [2018-01-24 23:11:13,817 INFO L254 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued a check-sat command [2018-01-24 23:11:13,854 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-24 23:11:13,862 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-24 23:11:13,878 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-24 23:11:13,878 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 23:11:13,885 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-24 23:11:13,886 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 23:11:13,892 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 23:11:13,892 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:22, output treesize:20 [2018-01-24 23:11:13,898 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 23:11:13,898 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 23:11:13,899 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-24 23:11:13,899 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 23:11:13,908 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-24 23:11:13,909 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 23:11:13,915 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 23:11:13,916 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:31, output treesize:24 [2018-01-24 23:11:13,922 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-24 23:11:13,924 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-24 23:11:13,924 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 23:11:13,926 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 23:11:13,935 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-24 23:11:13,936 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:38, output treesize:34 [2018-01-24 23:11:13,986 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-24 23:11:13,988 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-24 23:11:13,988 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 23:11:13,992 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 23:11:14,001 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-24 23:11:14,001 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:45, output treesize:41 [2018-01-24 23:11:14,234 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-24 23:11:14,241 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-24 23:11:14,241 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-24 23:11:14,251 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-24 23:11:14,251 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-24 23:11:14,265 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-24 23:11:14,283 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-24 23:11:14,283 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 4 variables, input treesize:50, output treesize:27 [2018-01-24 23:11:14,491 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-24 23:11:14,492 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-01-24 23:11:15,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-24 23:11:15,141 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 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-24 23:11:15,141 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 23:11:15,142 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 23:11:15,149 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-24 23:11:15,149 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:39, output treesize:58 [2018-01-24 23:11:17,474 WARN L143 SmtUtils]: Spent 1671ms on a formula simplification that was a NOOP. DAG size: 39 [2018-01-24 23:11:18,399 WARN L143 SmtUtils]: Spent 325ms on a formula simplification that was a NOOP. DAG size: 39 [2018-01-24 23:11:18,446 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-24 23:11:18,447 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 23:11:18,462 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-24 23:11:18,480 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-24 23:11:18,481 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-24 23:11:18,484 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 23:11:18,498 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-24 23:11:18,498 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-24 23:11:18,543 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-24 23:11:18,562 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-24 23:11:18,562 INFO L267 ElimStorePlain]: Start of recursive call 7: End of recursive call: and 1 xjuncts. [2018-01-24 23:11:18,566 INFO L267 ElimStorePlain]: Start of recursive call 6: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 23:11:18,574 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-24 23:11:18,574 INFO L202 ElimStorePlain]: Needed 7 recursive calls to eliminate 12 variables, input treesize:93, output treesize:7 [2018-01-24 23:11:18,582 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-24 23:11:18,584 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 5 imperfect interpolant sequences. [2018-01-24 23:11:18,584 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14, 12, 15, 13] total 50 [2018-01-24 23:11:18,584 INFO L247 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-01-24 23:11:18,584 INFO L409 AbstractCegarLoop]: Interpolant automaton has 23 states [2018-01-24 23:11:18,585 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2018-01-24 23:11:18,585 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=188, Invalid=2360, Unknown=2, NotChecked=0, Total=2550 [2018-01-24 23:11:18,585 INFO L87 Difference]: Start difference. First operand 83 states and 102 transitions. Second operand 23 states. [2018-01-24 23:11:20,916 WARN L146 SmtUtils]: Spent 1840ms on a formula simplification. DAG size of input: 65 DAG size of output 49 [2018-01-24 23:11:22,542 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 23:11:22,542 INFO L93 Difference]: Finished difference Result 304 states and 378 transitions. [2018-01-24 23:11:22,542 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2018-01-24 23:11:22,543 INFO L78 Accepts]: Start accepts. Automaton has 23 states. Word has length 29 [2018-01-24 23:11:22,543 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 23:11:22,545 INFO L225 Difference]: With dead ends: 304 [2018-01-24 23:11:22,545 INFO L226 Difference]: Without dead ends: 300 [2018-01-24 23:11:22,546 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 154 GetRequests, 70 SyntacticMatches, 11 SemanticMatches, 73 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1370 ImplicationChecksByTransitivity, 9.4s TimeCoverageRelationStatistics Valid=590, Invalid=4958, Unknown=2, NotChecked=0, Total=5550 [2018-01-24 23:11:22,547 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 300 states. [2018-01-24 23:11:22,560 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 300 to 150. [2018-01-24 23:11:22,560 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 150 states. [2018-01-24 23:11:22,561 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 150 states to 150 states and 194 transitions. [2018-01-24 23:11:22,562 INFO L78 Accepts]: Start accepts. Automaton has 150 states and 194 transitions. Word has length 29 [2018-01-24 23:11:22,562 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 23:11:22,562 INFO L432 AbstractCegarLoop]: Abstraction has 150 states and 194 transitions. [2018-01-24 23:11:22,562 INFO L433 AbstractCegarLoop]: Interpolant automaton has 23 states. [2018-01-24 23:11:22,562 INFO L276 IsEmpty]: Start isEmpty. Operand 150 states and 194 transitions. [2018-01-24 23:11:22,564 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2018-01-24 23:11:22,564 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 23:11:22,565 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-24 23:11:22,565 INFO L371 AbstractCegarLoop]: === Iteration 14 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 23:11:22,565 INFO L82 PathProgramCache]: Analyzing trace with hash -1785596499, now seen corresponding path program 1 times [2018-01-24 23:11:22,565 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 23:11:22,566 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 23:11:22,566 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-01-24 23:11:22,566 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 23:11:22,566 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 23:11:22,580 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 23:11:22,581 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. Received shutdown request... [2018-01-24 23:11:22,956 WARN L491 AbstractCegarLoop]: Verification canceled [2018-01-24 23:11:22,960 WARN L187 ceAbstractionStarter]: Timeout [2018-01-24 23:11:22,961 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 24.01 11:11:22 BoogieIcfgContainer [2018-01-24 23:11:22,961 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-01-24 23:11:22,962 INFO L168 Benchmark]: Toolchain (without parser) took 57747.12 ms. Allocated memory was 304.6 MB in the beginning and 1.7 GB in the end (delta: 1.4 GB). Free memory was 264.7 MB in the beginning and 1.3 GB in the end (delta: -1.0 GB). Peak memory consumption was 405.9 MB. Max. memory is 5.3 GB. [2018-01-24 23:11:22,963 INFO L168 Benchmark]: CDTParser took 0.27 ms. Allocated memory is still 304.6 MB. Free memory is still 270.6 MB. There was no memory consumed. Max. memory is 5.3 GB. [2018-01-24 23:11:22,963 INFO L168 Benchmark]: CACSL2BoogieTranslator took 281.20 ms. Allocated memory is still 304.6 MB. Free memory was 263.7 MB in the beginning and 253.5 MB in the end (delta: 10.1 MB). Peak memory consumption was 10.1 MB. Max. memory is 5.3 GB. [2018-01-24 23:11:22,963 INFO L168 Benchmark]: Boogie Preprocessor took 39.76 ms. Allocated memory is still 304.6 MB. Free memory was 253.5 MB in the beginning and 251.5 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 5.3 GB. [2018-01-24 23:11:22,963 INFO L168 Benchmark]: RCFGBuilder took 328.04 ms. Allocated memory is still 304.6 MB. Free memory was 251.5 MB in the beginning and 231.9 MB in the end (delta: 19.6 MB). Peak memory consumption was 19.6 MB. Max. memory is 5.3 GB. [2018-01-24 23:11:22,964 INFO L168 Benchmark]: TraceAbstraction took 57084.35 ms. Allocated memory was 304.6 MB in the beginning and 1.7 GB in the end (delta: 1.4 GB). Free memory was 230.9 MB in the beginning and 1.3 GB in the end (delta: -1.1 GB). Peak memory consumption was 372.1 MB. Max. memory is 5.3 GB. [2018-01-24 23:11:22,965 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.27 ms. Allocated memory is still 304.6 MB. Free memory is still 270.6 MB. There was no memory consumed. Max. memory is 5.3 GB. * CACSL2BoogieTranslator took 281.20 ms. Allocated memory is still 304.6 MB. Free memory was 263.7 MB in the beginning and 253.5 MB in the end (delta: 10.1 MB). Peak memory consumption was 10.1 MB. Max. memory is 5.3 GB. * Boogie Preprocessor took 39.76 ms. Allocated memory is still 304.6 MB. Free memory was 253.5 MB in the beginning and 251.5 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 5.3 GB. * RCFGBuilder took 328.04 ms. Allocated memory is still 304.6 MB. Free memory was 251.5 MB in the beginning and 231.9 MB in the end (delta: 19.6 MB). Peak memory consumption was 19.6 MB. Max. memory is 5.3 GB. * TraceAbstraction took 57084.35 ms. Allocated memory was 304.6 MB in the beginning and 1.7 GB in the end (delta: 1.4 GB). Free memory was 230.9 MB in the beginning and 1.3 GB in the end (delta: -1.1 GB). Peak memory consumption was 372.1 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.795621 RENAME_VARIABLES(MILLISECONDS) : 0.295729 UNFREEZE(MILLISECONDS) : 0.000000 CONJOIN(MILLISECONDS) : 1.748228 PROJECTAWAY(MILLISECONDS) : 1.043356 ADD_WEAK_EQUALITY(MILLISECONDS) : 0.073179 DISJOIN(MILLISECONDS) : 0.461492 RENAME_VARIABLES_DISJUNCTIVE(MILLISECONDS) : 0.326927 ADD_EQUALITY(MILLISECONDS) : 0.016559 DISJOIN_DISJUNCTIVE(MILLISECONDS) : 0.000000 ADD_DISEQUALITY(MILLISECONDS) : 0.016056 #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 * 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 30 with TraceHistMax 4, while InterpolatingTraceCheckCraig was constructing Craig interpolants, while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 28. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 569). Cancelled while BasicCegarLoop was analyzing trace of length 30 with TraceHistMax 4, while InterpolatingTraceCheckCraig was constructing Craig interpolants, while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 28. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 570). Cancelled while BasicCegarLoop was analyzing trace of length 30 with TraceHistMax 4, while InterpolatingTraceCheckCraig was constructing Craig interpolants, while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 28. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 569). Cancelled while BasicCegarLoop was analyzing trace of length 30 with TraceHistMax 4, while InterpolatingTraceCheckCraig was constructing Craig interpolants, while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 28. - TimeoutResultAtElement [Line: 553]: Timeout (TraceAbstraction) Unable to prove that all allocated memory was freed (line 553). Cancelled while BasicCegarLoop was analyzing trace of length 30 with TraceHistMax 4, while InterpolatingTraceCheckCraig was constructing Craig interpolants, while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 28. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 549). Cancelled while BasicCegarLoop was analyzing trace of length 30 with TraceHistMax 4, while InterpolatingTraceCheckCraig was constructing Craig interpolants, while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 28. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 545). Cancelled while BasicCegarLoop was analyzing trace of length 30 with TraceHistMax 4, while InterpolatingTraceCheckCraig was constructing Craig interpolants, while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 28. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 543). Cancelled while BasicCegarLoop was analyzing trace of length 30 with TraceHistMax 4, while InterpolatingTraceCheckCraig was constructing Craig interpolants, while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 28. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 545). Cancelled while BasicCegarLoop was analyzing trace of length 30 with TraceHistMax 4, while InterpolatingTraceCheckCraig was constructing Craig interpolants, while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 28. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 550). Cancelled while BasicCegarLoop was analyzing trace of length 30 with TraceHistMax 4, while InterpolatingTraceCheckCraig was constructing Craig interpolants, while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 28. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 543). Cancelled while BasicCegarLoop was analyzing trace of length 30 with TraceHistMax 4, while InterpolatingTraceCheckCraig was constructing Craig interpolants, while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 28. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 545). Cancelled while BasicCegarLoop was analyzing trace of length 30 with TraceHistMax 4, while InterpolatingTraceCheckCraig was constructing Craig interpolants, while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 28. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 550). Cancelled while BasicCegarLoop was analyzing trace of length 30 with TraceHistMax 4, while InterpolatingTraceCheckCraig was constructing Craig interpolants, while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 28. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 549). Cancelled while BasicCegarLoop was analyzing trace of length 30 with TraceHistMax 4, while InterpolatingTraceCheckCraig was constructing Craig interpolants, while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 28. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 545). Cancelled while BasicCegarLoop was analyzing trace of length 30 with TraceHistMax 4, while InterpolatingTraceCheckCraig was constructing Craig interpolants, while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 28. - StatisticsResult: Ultimate Automizer benchmark data CFG has 4 procedures, 58 locations, 15 error locations. TIMEOUT Result, 57.0s OverallTime, 14 OverallIterations, 4 TraceHistogramMax, 11.5s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 607 SDtfs, 1500 SDslu, 2715 SDs, 0 SdLazy, 2275 SolverSat, 396 SolverUnsat, 2 SolverUnknown, 0 SolverNotchecked, 5.7s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 470 GetRequests, 197 SyntacticMatches, 25 SemanticMatches, 248 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3416 ImplicationChecksByTransitivity, 16.6s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=150occurred in iteration=13, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 29.6s AbstIntTime, 1 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, AutomataMinimizationStatistics: 0.1s AutomataMinimizationTime, 13 MinimizatonAttempts, 285 StatesRemovedByMinimization, 6 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.5s SatisfiabilityAnalysisTime, 14.2s InterpolantComputationTime, 412 NumberOfCodeBlocks, 412 NumberOfCodeBlocksAsserted, 27 NumberOfCheckSat, 543 ConstructedInterpolants, 76 QuantifiedInterpolants, 159141 SizeOfPredicates, 108 NumberOfNonLiveVariables, 780 ConjunctsInSsa, 240 ConjunctsInUnsatCore, 25 InterpolantComputations, 10 PerfectInterpolantSequences, 4/120 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_precise.epf_AutomizerC.xml/Csv-Benchmark-0-2018-01-24_23-11-22-976.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_precise.epf_AutomizerC.xml/Csv-VPDomainBenchmark-0-2018-01-24_23-11-22-976.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_precise.epf_AutomizerC.xml/Csv-BenchmarkWithCounters-0-2018-01-24_23-11-22-976.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_precise.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-0-2018-01-24_23-11-22-976.csv Completed graceful shutdown