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.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 15:13:35,946 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-01-24 15:13:35,948 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-01-24 15:13:35,963 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-01-24 15:13:35,964 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-01-24 15:13:35,965 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-01-24 15:13:35,966 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-01-24 15:13:35,967 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-01-24 15:13:35,969 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-01-24 15:13:35,970 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-01-24 15:13:35,971 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-01-24 15:13:35,971 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-01-24 15:13:35,972 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-01-24 15:13:35,973 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-01-24 15:13:35,974 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-01-24 15:13:35,977 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-01-24 15:13:35,979 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-01-24 15:13:35,981 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-01-24 15:13:35,982 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-01-24 15:13:35,984 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-01-24 15:13:35,986 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-01-24 15:13:35,986 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-01-24 15:13:35,987 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-01-24 15:13:35,988 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-01-24 15:13:35,988 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-01-24 15:13:35,990 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-01-24 15:13:35,990 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-01-24 15:13:35,991 INFO L177 SettingsManager]: PEA to Boogie provides no preferences, ignoring... [2018-01-24 15:13:35,991 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-01-24 15:13:35,991 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-01-24 15:13:35,992 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-01-24 15:13:35,992 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.epf [2018-01-24 15:13:36,000 INFO L110 SettingsManager]: Loading preferences was successful [2018-01-24 15:13:36,001 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-01-24 15:13:36,002 INFO L131 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2018-01-24 15:13:36,002 INFO L133 SettingsManager]: * to procedures, called more than once=true [2018-01-24 15:13:36,002 INFO L131 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2018-01-24 15:13:36,002 INFO L133 SettingsManager]: * Abstract domain for RCFG-of-the-future=VPDomain [2018-01-24 15:13:36,002 INFO L133 SettingsManager]: * Use the RCFG-of-the-future interface=true [2018-01-24 15:13:36,003 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-01-24 15:13:36,003 INFO L133 SettingsManager]: * sizeof long=4 [2018-01-24 15:13:36,003 INFO L133 SettingsManager]: * Check unreachability of error function in SV-COMP mode=false [2018-01-24 15:13:36,003 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-01-24 15:13:36,003 INFO L133 SettingsManager]: * sizeof POINTER=4 [2018-01-24 15:13:36,003 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-01-24 15:13:36,003 INFO L133 SettingsManager]: * Check for the main procedure if all allocated memory was freed=true [2018-01-24 15:13:36,004 INFO L133 SettingsManager]: * Bitprecise bitfields=true [2018-01-24 15:13:36,004 INFO L133 SettingsManager]: * SV-COMP memtrack compatibility mode=true [2018-01-24 15:13:36,004 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-01-24 15:13:36,004 INFO L133 SettingsManager]: * sizeof long double=12 [2018-01-24 15:13:36,004 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-01-24 15:13:36,004 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-01-24 15:13:36,004 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-01-24 15:13:36,004 INFO L133 SettingsManager]: * Add additional assume for each assert=false [2018-01-24 15:13:36,005 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-01-24 15:13:36,005 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-01-24 15:13:36,005 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-01-24 15:13:36,005 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-01-24 15:13:36,006 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-01-24 15:13:36,006 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-01-24 15:13:36,006 INFO L133 SettingsManager]: * Trace refinement strategy=TAIPAN [2018-01-24 15:13:36,006 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-01-24 15:13:36,006 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-01-24 15:13:36,006 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-01-24 15:13:36,006 INFO L133 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES [2018-01-24 15:13:36,007 INFO L131 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2018-01-24 15:13:36,007 INFO L133 SettingsManager]: * TransformationType=HEAP_SEPARATOR [2018-01-24 15:13:36,039 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-01-24 15:13:36,050 INFO L266 ainManager$Toolchain]: [Toolchain 1]: Parser(s) successfully initialized [2018-01-24 15:13:36,054 INFO L222 ainManager$Toolchain]: [Toolchain 1]: Toolchain data selected. [2018-01-24 15:13:36,055 INFO L271 PluginConnector]: Initializing CDTParser... [2018-01-24 15:13:36,056 INFO L276 PluginConnector]: CDTParser initialized [2018-01-24 15:13:36,056 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 15:13:36,232 INFO L304 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-01-24 15:13:36,237 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2018-01-24 15:13:36,237 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2018-01-24 15:13:36,237 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2018-01-24 15:13:36,242 INFO L276 PluginConnector]: CACSL2BoogieTranslator initialized [2018-01-24 15:13:36,243 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 24.01 03:13:36" (1/1) ... [2018-01-24 15:13:36,245 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@386958ea and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.01 03:13:36, skipping insertion in model container [2018-01-24 15:13:36,245 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 24.01 03:13:36" (1/1) ... [2018-01-24 15:13:36,258 INFO L153 Dispatcher]: Using SV-COMP mode [2018-01-24 15:13:36,296 INFO L153 Dispatcher]: Using SV-COMP mode [2018-01-24 15:13:36,412 INFO L450 PostProcessor]: Settings: Checked method=main [2018-01-24 15:13:36,436 INFO L450 PostProcessor]: Settings: Checked method=main [2018-01-24 15:13:36,444 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.01 03:13:36 WrapperNode [2018-01-24 15:13:36,445 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2018-01-24 15:13:36,445 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-01-24 15:13:36,446 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-01-24 15:13:36,446 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-01-24 15:13:36,460 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.01 03:13:36" (1/1) ... [2018-01-24 15:13:36,460 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.01 03:13:36" (1/1) ... [2018-01-24 15:13:36,468 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.01 03:13:36" (1/1) ... [2018-01-24 15:13:36,469 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.01 03:13:36" (1/1) ... [2018-01-24 15:13:36,474 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.01 03:13:36" (1/1) ... [2018-01-24 15:13:36,479 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.01 03:13:36" (1/1) ... [2018-01-24 15:13:36,481 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.01 03:13:36" (1/1) ... [2018-01-24 15:13:36,483 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-01-24 15:13:36,483 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-01-24 15:13:36,483 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-01-24 15:13:36,484 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-01-24 15:13:36,485 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.01 03:13:36" (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 15:13:36,538 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2018-01-24 15:13:36,538 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-01-24 15:13:36,538 INFO L136 BoogieDeclarations]: Found implementation of procedure cstrncat [2018-01-24 15:13:36,538 INFO L136 BoogieDeclarations]: Found implementation of procedure main [2018-01-24 15:13:36,538 INFO L128 BoogieDeclarations]: Found specification of procedure write~int [2018-01-24 15:13:36,539 INFO L128 BoogieDeclarations]: Found specification of procedure read~int [2018-01-24 15:13:36,539 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.free [2018-01-24 15:13:36,539 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2018-01-24 15:13:36,539 INFO L128 BoogieDeclarations]: Found specification of procedure #Ultimate.alloc [2018-01-24 15:13:36,539 INFO L128 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2018-01-24 15:13:36,539 INFO L128 BoogieDeclarations]: Found specification of procedure cstrncat [2018-01-24 15:13:36,540 INFO L128 BoogieDeclarations]: Found specification of procedure main [2018-01-24 15:13:36,540 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2018-01-24 15:13:36,540 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-01-24 15:13:36,790 INFO L257 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-01-24 15:13:36,791 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 24.01 03:13:36 BoogieIcfgContainer [2018-01-24 15:13:36,791 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-01-24 15:13:36,792 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-01-24 15:13:36,792 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-01-24 15:13:36,793 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-01-24 15:13:36,793 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 24.01 03:13:36" (1/3) ... [2018-01-24 15:13:36,794 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1953d3b5 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 24.01 03:13:36, skipping insertion in model container [2018-01-24 15:13:36,794 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.01 03:13:36" (2/3) ... [2018-01-24 15:13:36,795 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1953d3b5 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 24.01 03:13:36, skipping insertion in model container [2018-01-24 15:13:36,795 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 24.01 03:13:36" (3/3) ... [2018-01-24 15:13:36,796 INFO L105 eAbstractionObserver]: Analyzing ICFG cstrncat-alloca_true-valid-memsafety_true-termination.i [2018-01-24 15:13:36,803 INFO L130 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-01-24 15:13:36,809 INFO L142 ceAbstractionStarter]: Appying trace abstraction to program that has 15 error locations. [2018-01-24 15:13:36,856 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-24 15:13:36,856 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-24 15:13:36,857 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-24 15:13:36,857 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-24 15:13:36,857 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-24 15:13:36,857 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-24 15:13:36,857 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-24 15:13:36,857 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-01-24 15:13:36,858 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-24 15:13:36,879 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states. [2018-01-24 15:13:36,886 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2018-01-24 15:13:36,886 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 15:13:36,887 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-24 15:13:36,888 INFO L371 AbstractCegarLoop]: === Iteration 1 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 15:13:36,893 INFO L82 PathProgramCache]: Analyzing trace with hash 1927484354, now seen corresponding path program 1 times [2018-01-24 15:13:36,896 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 15:13:36,952 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:13:36,953 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 15:13:36,953 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:13:36,953 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 15:13:36,997 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 15:13:37,005 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 15:13:37,067 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 15:13:37,068 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 15:13:37,069 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-01-24 15:13:37,069 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-24 15:13:37,071 INFO L409 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-01-24 15:13:37,083 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-01-24 15:13:37,083 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-24 15:13:37,086 INFO L87 Difference]: Start difference. First operand 58 states. Second operand 3 states. [2018-01-24 15:13:37,310 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 15:13:37,310 INFO L93 Difference]: Finished difference Result 90 states and 103 transitions. [2018-01-24 15:13:37,310 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-01-24 15:13:37,311 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 11 [2018-01-24 15:13:37,312 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 15:13:37,319 INFO L225 Difference]: With dead ends: 90 [2018-01-24 15:13:37,319 INFO L226 Difference]: Without dead ends: 55 [2018-01-24 15:13:37,322 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 15:13:37,335 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2018-01-24 15:13:37,350 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 55. [2018-01-24 15:13:37,351 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 55 states. [2018-01-24 15:13:37,352 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 61 transitions. [2018-01-24 15:13:37,354 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 61 transitions. Word has length 11 [2018-01-24 15:13:37,354 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 15:13:37,354 INFO L432 AbstractCegarLoop]: Abstraction has 55 states and 61 transitions. [2018-01-24 15:13:37,354 INFO L433 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-01-24 15:13:37,354 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 61 transitions. [2018-01-24 15:13:37,355 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2018-01-24 15:13:37,355 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 15:13:37,355 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-24 15:13:37,355 INFO L371 AbstractCegarLoop]: === Iteration 2 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 15:13:37,356 INFO L82 PathProgramCache]: Analyzing trace with hash 1621249811, now seen corresponding path program 1 times [2018-01-24 15:13:37,356 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 15:13:37,357 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:13:37,357 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 15:13:37,357 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:13:37,357 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 15:13:37,370 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 15:13:37,371 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 15:13:37,447 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 15:13:37,448 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 15:13:37,449 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-01-24 15:13:37,449 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-24 15:13:37,451 INFO L409 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-01-24 15:13:37,451 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-01-24 15:13:37,451 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-01-24 15:13:37,451 INFO L87 Difference]: Start difference. First operand 55 states and 61 transitions. Second operand 5 states. [2018-01-24 15:13:37,528 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 15:13:37,528 INFO L93 Difference]: Finished difference Result 103 states and 114 transitions. [2018-01-24 15:13:37,529 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-01-24 15:13:37,529 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 15 [2018-01-24 15:13:37,529 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 15:13:37,530 INFO L225 Difference]: With dead ends: 103 [2018-01-24 15:13:37,530 INFO L226 Difference]: Without dead ends: 55 [2018-01-24 15:13:37,532 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 15:13:37,532 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2018-01-24 15:13:37,537 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 55. [2018-01-24 15:13:37,538 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 55 states. [2018-01-24 15:13:37,539 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 60 transitions. [2018-01-24 15:13:37,539 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 60 transitions. Word has length 15 [2018-01-24 15:13:37,540 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 15:13:37,540 INFO L432 AbstractCegarLoop]: Abstraction has 55 states and 60 transitions. [2018-01-24 15:13:37,540 INFO L433 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-01-24 15:13:37,540 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 60 transitions. [2018-01-24 15:13:37,541 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2018-01-24 15:13:37,541 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 15:13:37,541 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-24 15:13:37,541 INFO L371 AbstractCegarLoop]: === Iteration 3 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 15:13:37,541 INFO L82 PathProgramCache]: Analyzing trace with hash -1993659115, now seen corresponding path program 1 times [2018-01-24 15:13:37,542 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 15:13:37,543 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:13:37,543 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 15:13:37,543 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:13:37,543 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 15:13:37,564 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 15:13:37,565 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 15:13:37,646 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 15:13:37,646 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 15:13:37,646 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-01-24 15:13:37,646 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-24 15:13:37,647 INFO L409 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-01-24 15:13:37,647 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-01-24 15:13:37,647 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-01-24 15:13:37,647 INFO L87 Difference]: Start difference. First operand 55 states and 60 transitions. Second operand 4 states. [2018-01-24 15:13:37,721 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 15:13:37,721 INFO L93 Difference]: Finished difference Result 55 states and 60 transitions. [2018-01-24 15:13:37,721 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-01-24 15:13:37,722 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 15 [2018-01-24 15:13:37,722 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 15:13:37,723 INFO L225 Difference]: With dead ends: 55 [2018-01-24 15:13:37,723 INFO L226 Difference]: Without dead ends: 54 [2018-01-24 15:13:37,723 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 15:13:37,724 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2018-01-24 15:13:37,728 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 54. [2018-01-24 15:13:37,729 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 54 states. [2018-01-24 15:13:37,730 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 59 transitions. [2018-01-24 15:13:37,730 INFO L78 Accepts]: Start accepts. Automaton has 54 states and 59 transitions. Word has length 15 [2018-01-24 15:13:37,730 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 15:13:37,730 INFO L432 AbstractCegarLoop]: Abstraction has 54 states and 59 transitions. [2018-01-24 15:13:37,731 INFO L433 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-01-24 15:13:37,731 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states and 59 transitions. [2018-01-24 15:13:37,731 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2018-01-24 15:13:37,731 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 15:13:37,731 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-24 15:13:37,732 INFO L371 AbstractCegarLoop]: === Iteration 4 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 15:13:37,732 INFO L82 PathProgramCache]: Analyzing trace with hash -1993659114, now seen corresponding path program 1 times [2018-01-24 15:13:37,732 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 15:13:37,733 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:13:37,733 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 15:13:37,733 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:13:37,733 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 15:13:37,748 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 15:13:37,749 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 15:13:37,913 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 15:13:37,913 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 15:13:37,913 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2018-01-24 15:13:37,913 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-24 15:13:37,913 INFO L409 AbstractCegarLoop]: Interpolant automaton has 8 states [2018-01-24 15:13:37,914 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2018-01-24 15:13:37,914 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=38, Unknown=0, NotChecked=0, Total=56 [2018-01-24 15:13:37,914 INFO L87 Difference]: Start difference. First operand 54 states and 59 transitions. Second operand 8 states. [2018-01-24 15:13:38,117 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 15:13:38,117 INFO L93 Difference]: Finished difference Result 54 states and 59 transitions. [2018-01-24 15:13:38,117 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-01-24 15:13:38,117 INFO L78 Accepts]: Start accepts. Automaton has 8 states. Word has length 15 [2018-01-24 15:13:38,118 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 15:13:38,118 INFO L225 Difference]: With dead ends: 54 [2018-01-24 15:13:38,119 INFO L226 Difference]: Without dead ends: 53 [2018-01-24 15:13:38,119 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=48, Invalid=84, Unknown=0, NotChecked=0, Total=132 [2018-01-24 15:13:38,119 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 53 states. [2018-01-24 15:13:38,124 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 53 to 53. [2018-01-24 15:13:38,124 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 53 states. [2018-01-24 15:13:38,126 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 53 states to 53 states and 58 transitions. [2018-01-24 15:13:38,126 INFO L78 Accepts]: Start accepts. Automaton has 53 states and 58 transitions. Word has length 15 [2018-01-24 15:13:38,126 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 15:13:38,126 INFO L432 AbstractCegarLoop]: Abstraction has 53 states and 58 transitions. [2018-01-24 15:13:38,126 INFO L433 AbstractCegarLoop]: Interpolant automaton has 8 states. [2018-01-24 15:13:38,126 INFO L276 IsEmpty]: Start isEmpty. Operand 53 states and 58 transitions. [2018-01-24 15:13:38,127 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2018-01-24 15:13:38,127 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 15:13:38,127 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-24 15:13:38,127 INFO L371 AbstractCegarLoop]: === Iteration 5 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 15:13:38,127 INFO L82 PathProgramCache]: Analyzing trace with hash -1673890416, now seen corresponding path program 1 times [2018-01-24 15:13:38,127 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 15:13:38,128 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:13:38,128 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 15:13:38,128 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:13:38,128 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 15:13:38,141 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 15:13:38,141 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 15:13:38,180 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 15:13:38,181 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 15:13:38,181 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-01-24 15:13:38,181 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-24 15:13:38,182 INFO L409 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-01-24 15:13:38,182 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-01-24 15:13:38,182 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-01-24 15:13:38,182 INFO L87 Difference]: Start difference. First operand 53 states and 58 transitions. Second operand 4 states. [2018-01-24 15:13:38,253 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 15:13:38,253 INFO L93 Difference]: Finished difference Result 53 states and 58 transitions. [2018-01-24 15:13:38,253 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-01-24 15:13:38,254 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 16 [2018-01-24 15:13:38,254 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 15:13:38,254 INFO L225 Difference]: With dead ends: 53 [2018-01-24 15:13:38,255 INFO L226 Difference]: Without dead ends: 52 [2018-01-24 15:13:38,255 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 15:13:38,255 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 52 states. [2018-01-24 15:13:38,260 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 52 to 52. [2018-01-24 15:13:38,261 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 52 states. [2018-01-24 15:13:38,262 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 52 states to 52 states and 57 transitions. [2018-01-24 15:13:38,262 INFO L78 Accepts]: Start accepts. Automaton has 52 states and 57 transitions. Word has length 16 [2018-01-24 15:13:38,263 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 15:13:38,263 INFO L432 AbstractCegarLoop]: Abstraction has 52 states and 57 transitions. [2018-01-24 15:13:38,263 INFO L433 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-01-24 15:13:38,263 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 57 transitions. [2018-01-24 15:13:38,264 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2018-01-24 15:13:38,264 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 15:13:38,264 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-24 15:13:38,264 INFO L371 AbstractCegarLoop]: === Iteration 6 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 15:13:38,264 INFO L82 PathProgramCache]: Analyzing trace with hash -1673890415, now seen corresponding path program 1 times [2018-01-24 15:13:38,264 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 15:13:38,265 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:13:38,265 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 15:13:38,265 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:13:38,266 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 15:13:38,278 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 15:13:38,279 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 15:13:38,347 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 15:13:38,347 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 15:13:38,347 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-01-24 15:13:38,347 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-24 15:13:38,347 INFO L409 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-01-24 15:13:38,347 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-01-24 15:13:38,348 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-01-24 15:13:38,348 INFO L87 Difference]: Start difference. First operand 52 states and 57 transitions. Second operand 5 states. [2018-01-24 15:13:38,372 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 15:13:38,372 INFO L93 Difference]: Finished difference Result 52 states and 57 transitions. [2018-01-24 15:13:38,372 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-01-24 15:13:38,372 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 16 [2018-01-24 15:13:38,372 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 15:13:38,373 INFO L225 Difference]: With dead ends: 52 [2018-01-24 15:13:38,373 INFO L226 Difference]: Without dead ends: 51 [2018-01-24 15:13:38,373 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 15:13:38,373 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2018-01-24 15:13:38,376 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 51. [2018-01-24 15:13:38,376 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 51 states. [2018-01-24 15:13:38,377 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 56 transitions. [2018-01-24 15:13:38,377 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 56 transitions. Word has length 16 [2018-01-24 15:13:38,377 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 15:13:38,377 INFO L432 AbstractCegarLoop]: Abstraction has 51 states and 56 transitions. [2018-01-24 15:13:38,377 INFO L433 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-01-24 15:13:38,377 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 56 transitions. [2018-01-24 15:13:38,378 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2018-01-24 15:13:38,378 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 15:13:38,378 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 15:13:38,378 INFO L371 AbstractCegarLoop]: === Iteration 7 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 15:13:38,378 INFO L82 PathProgramCache]: Analyzing trace with hash 1745382581, now seen corresponding path program 1 times [2018-01-24 15:13:38,378 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 15:13:38,379 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:13:38,379 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 15:13:38,379 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:13:38,379 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 15:13:38,391 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 15:13:38,392 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 15:13:38,421 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 15:13:38,421 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 15:13:38,421 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-01-24 15:13:38,421 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-24 15:13:38,422 INFO L409 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-01-24 15:13:38,422 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-01-24 15:13:38,422 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-01-24 15:13:38,422 INFO L87 Difference]: Start difference. First operand 51 states and 56 transitions. Second operand 5 states. [2018-01-24 15:13:38,478 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 15:13:38,478 INFO L93 Difference]: Finished difference Result 51 states and 56 transitions. [2018-01-24 15:13:38,478 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-01-24 15:13:38,479 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 20 [2018-01-24 15:13:38,479 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 15:13:38,480 INFO L225 Difference]: With dead ends: 51 [2018-01-24 15:13:38,480 INFO L226 Difference]: Without dead ends: 47 [2018-01-24 15:13:38,480 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 15:13:38,480 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2018-01-24 15:13:38,484 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 47. [2018-01-24 15:13:38,485 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 47 states. [2018-01-24 15:13:38,486 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 47 states to 47 states and 52 transitions. [2018-01-24 15:13:38,486 INFO L78 Accepts]: Start accepts. Automaton has 47 states and 52 transitions. Word has length 20 [2018-01-24 15:13:38,486 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 15:13:38,486 INFO L432 AbstractCegarLoop]: Abstraction has 47 states and 52 transitions. [2018-01-24 15:13:38,486 INFO L433 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-01-24 15:13:38,487 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 52 transitions. [2018-01-24 15:13:38,487 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2018-01-24 15:13:38,487 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 15:13:38,487 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 15:13:38,488 INFO L371 AbstractCegarLoop]: === Iteration 8 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 15:13:38,488 INFO L82 PathProgramCache]: Analyzing trace with hash 1745382582, now seen corresponding path program 1 times [2018-01-24 15:13:38,488 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 15:13:38,489 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:13:38,489 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 15:13:38,489 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:13:38,489 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 15:13:38,501 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 15:13:38,502 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 15:13:38,637 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 15:13:38,637 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 15:13:38,637 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2018-01-24 15:13:38,637 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-24 15:13:38,638 INFO L409 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-01-24 15:13:38,638 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-01-24 15:13:38,638 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2018-01-24 15:13:38,638 INFO L87 Difference]: Start difference. First operand 47 states and 52 transitions. Second operand 9 states. [2018-01-24 15:13:38,803 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 15:13:38,803 INFO L93 Difference]: Finished difference Result 69 states and 78 transitions. [2018-01-24 15:13:38,803 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-01-24 15:13:38,803 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 20 [2018-01-24 15:13:38,804 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 15:13:38,806 INFO L225 Difference]: With dead ends: 69 [2018-01-24 15:13:38,807 INFO L226 Difference]: Without dead ends: 65 [2018-01-24 15:13:38,807 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 15:13:38,807 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 65 states. [2018-01-24 15:13:38,812 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 65 to 60. [2018-01-24 15:13:38,813 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 60 states. [2018-01-24 15:13:38,814 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 60 states to 60 states and 71 transitions. [2018-01-24 15:13:38,814 INFO L78 Accepts]: Start accepts. Automaton has 60 states and 71 transitions. Word has length 20 [2018-01-24 15:13:38,814 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 15:13:38,815 INFO L432 AbstractCegarLoop]: Abstraction has 60 states and 71 transitions. [2018-01-24 15:13:38,815 INFO L433 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-01-24 15:13:38,815 INFO L276 IsEmpty]: Start isEmpty. Operand 60 states and 71 transitions. [2018-01-24 15:13:38,816 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2018-01-24 15:13:38,816 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 15:13:38,816 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 15:13:38,816 INFO L371 AbstractCegarLoop]: === Iteration 9 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 15:13:38,816 INFO L82 PathProgramCache]: Analyzing trace with hash 1818413707, now seen corresponding path program 1 times [2018-01-24 15:13:38,816 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 15:13:38,817 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:13:38,817 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 15:13:38,817 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:13:38,817 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 15:13:38,830 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 15:13:38,831 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 15:13:38,985 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 15:13:38,985 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-24 15:13:38,985 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-01-24 15:13:38,987 INFO L199 CegarAbsIntRunner]: Running AI on error trace of length 24 with the following transitions: [2018-01-24 15:13:38,989 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 15:13:39,035 INFO L147 AbstractInterpreter]: Using domain VPDomain [2018-01-24 15:13:39,036 INFO L101 FixpointEngine]: Starting fixpoint engine with domain VPDomain (maxUnwinding=3, maxParallelStates=2) [2018-01-24 15:13:39,998 INFO L259 AbstractInterpreter]: Some error location(s) were reachable [2018-01-24 15:13:39,999 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 15:13:40,017 INFO L434 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: Unknown [2018-01-24 15:13:40,017 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-24 15:13:40,018 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 15:13:40,028 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 15:13:40,028 INFO L280 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-01-24 15:13:40,064 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 15:13:40,075 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-24 15:13:40,200 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 15:13:40,202 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:40,217 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 15:13:40,217 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:40,255 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 15:13:40,256 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:24, output treesize:19 [2018-01-24 15:13:40,326 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 15:13:40,327 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 15:13:40,328 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 15:13:40,328 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:40,337 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 15:13:40,338 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 15:13:40,338 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:40,347 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 15:13:40,347 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:30, output treesize:18 [2018-01-24 15:13:40,517 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 15:13:40,517 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-01-24 15:13:40,774 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 15:13:40,774 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:40,778 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 15:13:40,787 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 15:13:40,788 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:40,788 WARN L307 Elim1Store]: Array PQE input equivalent to true [2018-01-24 15:13:40,789 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:40,791 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:13:40,794 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 15:13:40,794 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 4 variables, input treesize:21, output treesize:3 [2018-01-24 15:13:40,820 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 15:13:40,848 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-24 15:13:40,849 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 15:13:40,853 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 15:13:40,853 INFO L280 anRefinementStrategy]: Using traceCheck mode CVC4_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-01-24 15:13:40,882 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 15:13:40,887 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-24 15:13:40,898 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 15:13:40,899 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:40,908 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 15:13:40,909 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:40,925 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 15:13:40,925 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:24, output treesize:19 [2018-01-24 15:13:40,981 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 15:13:40,981 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 15:13:40,982 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 15:13:40,982 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:40,993 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 15:13:40,993 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 15:13:40,994 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 15:13:40,994 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:41,000 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 15:13:41,000 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:30, output treesize:18 [2018-01-24 15:13:41,093 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 15:13:41,093 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-01-24 15:13:41,129 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 15:13:41,129 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:41,132 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 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 15:13:41,140 WARN L307 Elim1Store]: Array PQE input equivalent to true [2018-01-24 15:13:41,140 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:41,142 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 15:13:41,142 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:41,144 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:13:41,147 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 15:13:41,147 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 4 variables, input treesize:21, output treesize:3 [2018-01-24 15:13:41,192 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 15:13:41,194 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 5 imperfect interpolant sequences. [2018-01-24 15:13:41,194 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 12, 11, 11, 11] total 34 [2018-01-24 15:13:41,194 INFO L247 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-01-24 15:13:41,195 INFO L409 AbstractCegarLoop]: Interpolant automaton has 22 states [2018-01-24 15:13:41,195 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2018-01-24 15:13:41,196 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=137, Invalid=1053, Unknown=0, NotChecked=0, Total=1190 [2018-01-24 15:13:41,196 INFO L87 Difference]: Start difference. First operand 60 states and 71 transitions. Second operand 22 states. [2018-01-24 15:13:41,906 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 15:13:41,906 INFO L93 Difference]: Finished difference Result 87 states and 100 transitions. [2018-01-24 15:13:41,907 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-01-24 15:13:41,907 INFO L78 Accepts]: Start accepts. Automaton has 22 states. Word has length 23 [2018-01-24 15:13:41,907 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 15:13:41,907 INFO L225 Difference]: With dead ends: 87 [2018-01-24 15:13:41,908 INFO L226 Difference]: Without dead ends: 83 [2018-01-24 15:13:41,908 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 111 GetRequests, 62 SyntacticMatches, 8 SemanticMatches, 41 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 501 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=263, Invalid=1543, Unknown=0, NotChecked=0, Total=1806 [2018-01-24 15:13:41,909 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 83 states. [2018-01-24 15:13:41,915 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 83 to 70. [2018-01-24 15:13:41,916 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 70 states. [2018-01-24 15:13:41,917 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 70 states to 70 states and 86 transitions. [2018-01-24 15:13:41,917 INFO L78 Accepts]: Start accepts. Automaton has 70 states and 86 transitions. Word has length 23 [2018-01-24 15:13:41,917 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 15:13:41,917 INFO L432 AbstractCegarLoop]: Abstraction has 70 states and 86 transitions. [2018-01-24 15:13:41,917 INFO L433 AbstractCegarLoop]: Interpolant automaton has 22 states. [2018-01-24 15:13:41,917 INFO L276 IsEmpty]: Start isEmpty. Operand 70 states and 86 transitions. [2018-01-24 15:13:41,918 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2018-01-24 15:13:41,918 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 15:13:41,918 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 15:13:41,919 INFO L371 AbstractCegarLoop]: === Iteration 10 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 15:13:41,919 INFO L82 PathProgramCache]: Analyzing trace with hash -557502487, now seen corresponding path program 1 times [2018-01-24 15:13:41,919 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 15:13:41,920 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:13:41,920 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 15:13:41,920 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:13:41,920 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 15:13:41,932 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 15:13:41,933 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 15:13:41,977 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 15:13:41,977 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 15:13:41,977 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-01-24 15:13:41,977 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-24 15:13:41,978 INFO L409 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-01-24 15:13:41,978 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-01-24 15:13:41,978 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2018-01-24 15:13:41,978 INFO L87 Difference]: Start difference. First operand 70 states and 86 transitions. Second operand 6 states. [2018-01-24 15:13:42,050 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 15:13:42,050 INFO L93 Difference]: Finished difference Result 73 states and 92 transitions. [2018-01-24 15:13:42,050 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-01-24 15:13:42,050 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 25 [2018-01-24 15:13:42,051 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 15:13:42,052 INFO L225 Difference]: With dead ends: 73 [2018-01-24 15:13:42,052 INFO L226 Difference]: Without dead ends: 72 [2018-01-24 15:13:42,052 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 15:13:42,052 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 72 states. [2018-01-24 15:13:42,059 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 72 to 69. [2018-01-24 15:13:42,059 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 69 states. [2018-01-24 15:13:42,060 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 69 states to 69 states and 83 transitions. [2018-01-24 15:13:42,060 INFO L78 Accepts]: Start accepts. Automaton has 69 states and 83 transitions. Word has length 25 [2018-01-24 15:13:42,061 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 15:13:42,061 INFO L432 AbstractCegarLoop]: Abstraction has 69 states and 83 transitions. [2018-01-24 15:13:42,061 INFO L433 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-01-24 15:13:42,061 INFO L276 IsEmpty]: Start isEmpty. Operand 69 states and 83 transitions. [2018-01-24 15:13:42,062 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2018-01-24 15:13:42,062 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 15:13:42,062 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 15:13:42,062 INFO L371 AbstractCegarLoop]: === Iteration 11 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 15:13:42,062 INFO L82 PathProgramCache]: Analyzing trace with hash -557502486, now seen corresponding path program 1 times [2018-01-24 15:13:42,062 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 15:13:42,063 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:13:42,063 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 15:13:42,063 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:13:42,064 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 15:13:42,075 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 15:13:42,076 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 15:13:42,180 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 15:13:42,180 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 15:13:42,180 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2018-01-24 15:13:42,180 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-24 15:13:42,181 INFO L409 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-01-24 15:13:42,181 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-01-24 15:13:42,181 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=54, Unknown=0, NotChecked=0, Total=72 [2018-01-24 15:13:42,181 INFO L87 Difference]: Start difference. First operand 69 states and 83 transitions. Second operand 9 states. [2018-01-24 15:13:42,275 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 15:13:42,275 INFO L93 Difference]: Finished difference Result 99 states and 123 transitions. [2018-01-24 15:13:42,276 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-01-24 15:13:42,276 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 25 [2018-01-24 15:13:42,276 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 15:13:42,276 INFO L225 Difference]: With dead ends: 99 [2018-01-24 15:13:42,277 INFO L226 Difference]: Without dead ends: 98 [2018-01-24 15:13:42,277 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 18 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=32, Invalid=100, Unknown=0, NotChecked=0, Total=132 [2018-01-24 15:13:42,277 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 98 states. [2018-01-24 15:13:42,281 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 98 to 80. [2018-01-24 15:13:42,282 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 80 states. [2018-01-24 15:13:42,282 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 80 states to 80 states and 98 transitions. [2018-01-24 15:13:42,282 INFO L78 Accepts]: Start accepts. Automaton has 80 states and 98 transitions. Word has length 25 [2018-01-24 15:13:42,283 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 15:13:42,283 INFO L432 AbstractCegarLoop]: Abstraction has 80 states and 98 transitions. [2018-01-24 15:13:42,283 INFO L433 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-01-24 15:13:42,283 INFO L276 IsEmpty]: Start isEmpty. Operand 80 states and 98 transitions. [2018-01-24 15:13:42,283 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2018-01-24 15:13:42,283 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 15:13:42,283 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 15:13:42,284 INFO L371 AbstractCegarLoop]: === Iteration 12 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 15:13:42,284 INFO L82 PathProgramCache]: Analyzing trace with hash -59760490, now seen corresponding path program 2 times [2018-01-24 15:13:42,284 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 15:13:42,284 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:13:42,284 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 15:13:42,285 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:13:42,285 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 15:13:42,298 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 15:13:42,298 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 15:13:42,659 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 15:13:42,659 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-24 15:13:42,659 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-01-24 15:13:42,659 INFO L183 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-01-24 15:13:42,660 INFO L434 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-01-24 15:13:42,660 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-24 15:13:42,660 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 15:13:42,669 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-01-24 15:13:42,669 INFO L280 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST1 (IT: FPandBP) [2018-01-24 15:13:42,685 INFO L201 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-24 15:13:42,689 INFO L214 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-24 15:13:42,691 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-24 15:13:42,694 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-24 15:13:42,768 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 15:13:42,768 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:42,780 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 15:13:42,781 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:42,791 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:13:42,791 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:27, output treesize:25 [2018-01-24 15:13:42,867 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 15:13:42,868 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 15:13:42,868 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 15:13:42,869 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:42,888 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 15:13:42,889 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 15:13:42,889 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 15:13:42,890 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:42,901 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:13:42,901 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:36, output treesize:25 [2018-01-24 15:13:42,957 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 15:13:42,958 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 15:13:42,958 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:42,960 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:13:42,967 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 15:13:42,967 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:41, output treesize:37 [2018-01-24 15:13:43,004 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 15:13:43,008 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 15:13:43,026 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 15:13:43,027 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:43,056 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:13:43,068 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 15:13:43,069 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:52, output treesize:48 [2018-01-24 15:13:43,166 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 15:13:43,168 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 15:13:43,173 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 15:13:43,174 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-24 15:13:43,185 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 15:13:43,185 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:43,188 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-24 15:13:43,198 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 15:13:43,199 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 4 variables, input treesize:54, output treesize:69 [2018-01-24 15:13:43,362 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 15:13:43,362 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-01-24 15:13:43,592 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 15:13:43,616 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 15:13:43,616 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:43,620 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:13:43,622 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 15:13:43,642 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 15:13:43,642 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:43,646 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:13:43,654 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 2 xjuncts. [2018-01-24 15:13:43,654 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 1 variables, input treesize:47, output treesize:25 [2018-01-24 15:13:43,804 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 15:13:43,805 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:43,809 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 15:13:43,816 WARN L307 Elim1Store]: Array PQE input equivalent to true [2018-01-24 15:13:43,816 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:43,818 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 15:13:43,818 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:43,820 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:13:43,824 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 15:13:43,824 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 4 variables, input treesize:26, output treesize:9 [2018-01-24 15:13:43,903 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 15:13:43,923 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-24 15:13:43,923 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 15:13:43,926 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-01-24 15:13:43,926 INFO L280 anRefinementStrategy]: Using traceCheck mode CVC4_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST1 (IT: FPandBP) [2018-01-24 15:13:43,942 INFO L201 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-24 15:13:43,970 INFO L214 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-24 15:13:44,001 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-24 15:13:44,007 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-24 15:13:44,040 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 15:13:44,041 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:44,051 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 15:13:44,051 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:44,056 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:13:44,057 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:19, output treesize:17 [2018-01-24 15:13:44,131 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 15:13:44,132 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 15:13:44,132 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 15:13:44,132 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:44,139 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 15:13:44,139 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:44,144 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:13:44,144 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:28, output treesize:21 [2018-01-24 15:13:44,213 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 15:13:44,214 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 15:13:44,214 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:44,216 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:13:44,220 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:13:44,220 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:29, output treesize:25 [2018-01-24 15:13:44,260 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 15:13:44,270 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 15:13:44,270 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:44,274 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:13:44,279 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 15:13:44,280 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:36, output treesize:32 [2018-01-24 15:13:44,428 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 15:13:44,434 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 15:13:44,434 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-24 15:13:44,443 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 15:13:44,443 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:44,445 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-24 15:13:44,451 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 15:13:44,451 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 3 variables, input treesize:38, output treesize:20 [2018-01-24 15:13:44,623 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 15:13:44,623 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-01-24 15:13:44,889 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 15:13:44,898 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 15:13:44,899 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:44,900 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:13:44,906 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:13:44,906 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:36, output treesize:25 [2018-01-24 15:13:45,847 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 15:13:45,848 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:45,853 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 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 15:13:45,866 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 15:13:45,866 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:45,867 WARN L307 Elim1Store]: Array PQE input equivalent to true [2018-01-24 15:13:45,867 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:45,871 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:13:45,875 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 15:13:45,876 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 6 variables, input treesize:37, output treesize:7 [2018-01-24 15:13:45,902 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 15:13:45,903 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 5 imperfect interpolant sequences. [2018-01-24 15:13:45,903 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 15, 13, 14, 12] total 58 [2018-01-24 15:13:45,903 INFO L247 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-01-24 15:13:45,904 INFO L409 AbstractCegarLoop]: Interpolant automaton has 27 states [2018-01-24 15:13:45,904 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2018-01-24 15:13:45,905 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=245, Invalid=3176, Unknown=1, NotChecked=0, Total=3422 [2018-01-24 15:13:45,905 INFO L87 Difference]: Start difference. First operand 80 states and 98 transitions. Second operand 27 states. [2018-01-24 15:13:50,648 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 15:13:50,648 INFO L93 Difference]: Finished difference Result 183 states and 220 transitions. [2018-01-24 15:13:50,648 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2018-01-24 15:13:50,648 INFO L78 Accepts]: Start accepts. Automaton has 27 states. Word has length 26 [2018-01-24 15:13:50,649 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 15:13:50,649 INFO L225 Difference]: With dead ends: 183 [2018-01-24 15:13:50,650 INFO L226 Difference]: Without dead ends: 179 [2018-01-24 15:13:50,651 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 134 GetRequests, 53 SyntacticMatches, 6 SemanticMatches, 75 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1505 ImplicationChecksByTransitivity, 3.7s TimeCoverageRelationStatistics Valid=611, Invalid=5240, Unknown=1, NotChecked=0, Total=5852 [2018-01-24 15:13:50,651 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 179 states. [2018-01-24 15:13:50,656 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 179 to 83. [2018-01-24 15:13:50,657 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 83 states. [2018-01-24 15:13:50,657 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 83 states to 83 states and 102 transitions. [2018-01-24 15:13:50,658 INFO L78 Accepts]: Start accepts. Automaton has 83 states and 102 transitions. Word has length 26 [2018-01-24 15:13:50,658 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 15:13:50,658 INFO L432 AbstractCegarLoop]: Abstraction has 83 states and 102 transitions. [2018-01-24 15:13:50,658 INFO L433 AbstractCegarLoop]: Interpolant automaton has 27 states. [2018-01-24 15:13:50,658 INFO L276 IsEmpty]: Start isEmpty. Operand 83 states and 102 transitions. [2018-01-24 15:13:50,659 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2018-01-24 15:13:50,659 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 15:13:50,659 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 15:13:50,659 INFO L371 AbstractCegarLoop]: === Iteration 13 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 15:13:50,659 INFO L82 PathProgramCache]: Analyzing trace with hash 2086668971, now seen corresponding path program 3 times [2018-01-24 15:13:50,659 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 15:13:50,660 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:13:50,660 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-01-24 15:13:50,660 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:13:50,660 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 15:13:50,674 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 15:13:50,675 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 15:13:51,037 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 15:13:51,037 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-24 15:13:51,077 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-01-24 15:13:51,077 INFO L183 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-01-24 15:13:51,077 INFO L434 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-01-24 15:13:51,077 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-24 15:13:51,077 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 15:13:51,082 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-01-24 15:13:51,082 INFO L280 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST2 (IT: FPandBP) [2018-01-24 15:13:51,092 INFO L254 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued a check-sat command [2018-01-24 15:13:51,096 INFO L254 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued a check-sat command [2018-01-24 15:13:51,098 INFO L254 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued a check-sat command [2018-01-24 15:13:51,101 INFO L254 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued a check-sat command [2018-01-24 15:13:51,102 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-24 15:13:51,105 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-24 15:13:51,113 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 15:13:51,113 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:51,120 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 15:13:51,121 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:51,126 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:13:51,127 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:22, output treesize:20 [2018-01-24 15:13:51,151 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 15:13:51,152 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 15:13:51,152 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:51,163 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 15:13:51,164 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 15:13:51,164 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 15:13:51,164 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:51,171 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:13:51,171 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:31, output treesize:24 [2018-01-24 15:13:51,232 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 15:13:51,234 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 15:13:51,234 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:51,235 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:13:51,242 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 15:13:51,242 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:34, output treesize:30 [2018-01-24 15:13:51,270 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 15:13:51,272 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 15:13:51,272 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:51,276 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:13:51,282 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 15:13:51,282 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:41, output treesize:37 [2018-01-24 15:13:51,404 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 15:13:51,410 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 15:13:51,411 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-24 15:13:51,417 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 15:13:51,417 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:51,420 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-24 15:13:51,426 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 15:13:51,427 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 4 variables, input treesize:44, output treesize:18 [2018-01-24 15:13:51,464 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 15:13:51,465 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-01-24 15:13:51,735 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 15:13:51,744 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 15:13:51,744 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:51,745 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:13:51,756 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 15:13:51,757 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:36, output treesize:39 [2018-01-24 15:13:52,145 WARN L143 SmtUtils]: Spent 307ms on a formula simplification that was a NOOP. DAG size: 36 [2018-01-24 15:13:52,495 WARN L143 SmtUtils]: Spent 302ms on a formula simplification that was a NOOP. DAG size: 36 [2018-01-24 15:13:52,510 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 15:13:52,511 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:52,521 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 15:13:52,537 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 15:13:52,537 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:52,547 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:13:52,556 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 15:13:52,570 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 15:13:52,571 INFO L267 ElimStorePlain]: Start of recursive call 6: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:52,574 INFO L267 ElimStorePlain]: Start of recursive call 5: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:13:52,583 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 15:13:52,583 INFO L267 ElimStorePlain]: Start of recursive call 7: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:52,589 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 15:13:52,590 INFO L202 ElimStorePlain]: Needed 7 recursive calls to eliminate 12 variables, input treesize:71, output treesize:7 [2018-01-24 15:13:52,603 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 15:13:52,623 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-24 15:13:52,623 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 15:13:52,626 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-01-24 15:13:52,626 INFO L280 anRefinementStrategy]: Using traceCheck mode CVC4_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST2 (IT: FPandBP) [2018-01-24 15:13:52,641 INFO L254 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued a check-sat command [2018-01-24 15:13:52,669 INFO L254 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued a check-sat command [2018-01-24 15:13:52,701 INFO L254 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued a check-sat command [2018-01-24 15:13:52,738 INFO L254 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued a check-sat command [2018-01-24 15:13:52,774 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-24 15:13:52,780 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-24 15:13:52,786 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 15:13:52,786 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:52,797 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 15:13:52,797 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:52,802 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:13:52,803 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:22, output treesize:20 [2018-01-24 15:13:52,812 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 15:13:52,813 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 15:13:52,813 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 15:13:52,813 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:52,821 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 15:13:52,821 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:52,827 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:13:52,828 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:31, output treesize:24 [2018-01-24 15:13:52,834 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 15:13:52,835 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 15:13:52,835 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:52,836 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:13:52,843 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 15:13:52,843 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:38, output treesize:34 [2018-01-24 15:13:52,888 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 15:13:52,889 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 12 [2018-01-24 15:13:52,890 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:52,893 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:13:52,901 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 15:13:52,901 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:45, output treesize:41 [2018-01-24 15:13:53,082 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 15:13:53,087 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 15:13:53,087 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-24 15:13:53,094 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 15:13:53,094 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:53,097 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-24 15:13:53,104 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 15:13:53,104 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 4 variables, input treesize:50, output treesize:27 [2018-01-24 15:13:53,245 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 15:13:53,246 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-01-24 15:13:53,636 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 15:13:53,645 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 15:13:53,645 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:53,647 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:13:53,654 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 15:13:53,654 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:39, output treesize:58 [2018-01-24 15:13:55,204 WARN L143 SmtUtils]: Spent 411ms on a formula simplification that was a NOOP. DAG size: 39 [2018-01-24 15:13:57,146 WARN L143 SmtUtils]: Spent 1093ms on a formula simplification that was a NOOP. DAG size: 39 [2018-01-24 15:13:57,179 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 15:13:57,180 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:57,191 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 15:13:57,205 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 15:13:57,205 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:57,208 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:13:57,218 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 15:13:57,218 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:57,228 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 15:13:57,242 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 15:13:57,242 INFO L267 ElimStorePlain]: Start of recursive call 7: End of recursive call: and 1 xjuncts. [2018-01-24 15:13:57,245 INFO L267 ElimStorePlain]: Start of recursive call 6: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:13:57,251 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 15:13:57,252 INFO L202 ElimStorePlain]: Needed 7 recursive calls to eliminate 12 variables, input treesize:93, output treesize:7 [2018-01-24 15:13:57,257 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 15:13:57,259 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 5 imperfect interpolant sequences. [2018-01-24 15:13:57,259 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14, 12, 15, 13] total 50 [2018-01-24 15:13:57,259 INFO L247 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-01-24 15:13:57,259 INFO L409 AbstractCegarLoop]: Interpolant automaton has 23 states [2018-01-24 15:13:57,259 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2018-01-24 15:13:57,260 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=187, Invalid=2361, Unknown=2, NotChecked=0, Total=2550 [2018-01-24 15:13:57,260 INFO L87 Difference]: Start difference. First operand 83 states and 102 transitions. Second operand 23 states. [2018-01-24 15:13:58,899 WARN L146 SmtUtils]: Spent 1175ms on a formula simplification. DAG size of input: 65 DAG size of output 49 [2018-01-24 15:14:02,225 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 15:14:02,225 INFO L93 Difference]: Finished difference Result 304 states and 378 transitions. [2018-01-24 15:14:02,236 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2018-01-24 15:14:02,236 INFO L78 Accepts]: Start accepts. Automaton has 23 states. Word has length 29 [2018-01-24 15:14:02,237 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 15:14:02,238 INFO L225 Difference]: With dead ends: 304 [2018-01-24 15:14:02,238 INFO L226 Difference]: Without dead ends: 300 [2018-01-24 15:14:02,240 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 154 GetRequests, 70 SyntacticMatches, 11 SemanticMatches, 73 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1370 ImplicationChecksByTransitivity, 9.7s TimeCoverageRelationStatistics Valid=589, Invalid=4959, Unknown=2, NotChecked=0, Total=5550 [2018-01-24 15:14:02,240 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 300 states. [2018-01-24 15:14:02,251 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 300 to 150. [2018-01-24 15:14:02,251 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 150 states. [2018-01-24 15:14:02,252 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 150 states to 150 states and 194 transitions. [2018-01-24 15:14:02,252 INFO L78 Accepts]: Start accepts. Automaton has 150 states and 194 transitions. Word has length 29 [2018-01-24 15:14:02,253 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 15:14:02,253 INFO L432 AbstractCegarLoop]: Abstraction has 150 states and 194 transitions. [2018-01-24 15:14:02,253 INFO L433 AbstractCegarLoop]: Interpolant automaton has 23 states. [2018-01-24 15:14:02,253 INFO L276 IsEmpty]: Start isEmpty. Operand 150 states and 194 transitions. [2018-01-24 15:14:02,256 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2018-01-24 15:14:02,256 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 15:14:02,256 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 15:14:02,256 INFO L371 AbstractCegarLoop]: === Iteration 14 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 15:14:02,256 INFO L82 PathProgramCache]: Analyzing trace with hash -1785596499, now seen corresponding path program 1 times [2018-01-24 15:14:02,257 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 15:14:02,257 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:14:02,257 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-01-24 15:14:02,258 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:14:02,258 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 15:14:02,273 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 15:14:02,274 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 15:14:02,817 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 15:14:02,817 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-24 15:14:02,817 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-01-24 15:14:02,817 INFO L199 CegarAbsIntRunner]: Running AI on error trace of length 30 with the following transitions: [2018-01-24 15:14:02,817 INFO L201 CegarAbsIntRunner]: [0], [1], [5], [10], [16], [22], [27], [28], [29], [30], [31], [32], [35], [46], [50], [52], [54], [59], [103], [104], [105], [107] [2018-01-24 15:14:02,818 INFO L147 AbstractInterpreter]: Using domain VPDomain [2018-01-24 15:14:02,818 INFO L101 FixpointEngine]: Starting fixpoint engine with domain VPDomain (maxUnwinding=3, maxParallelStates=2) [2018-01-24 15:14:03,610 INFO L259 AbstractInterpreter]: Some error location(s) were reachable [2018-01-24 15:14:03,611 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 15:14:03,617 INFO L434 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: Unknown [2018-01-24 15:14:03,617 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-24 15:14:03,617 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-24 15:14:03,630 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 15:14:03,630 INFO L280 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-01-24 15:14:03,657 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 15:14:03,660 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-24 15:14:03,833 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 15:14:03,834 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 15:14:03,893 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 15:14:03,893 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 15:14:03,964 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:14:03,965 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:27, output treesize:25 [2018-01-24 15:14:04,256 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 15:14:04,269 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 15:14:04,270 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 15:14:04,270 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 15:14:04,346 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 15:14:04,346 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 15:14:04,347 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 15:14:04,368 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:14:04,368 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:36, output treesize:25 [2018-01-24 15:14:04,419 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 15:14:04,420 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 15:14:04,420 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 15:14:04,421 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:14:04,428 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 15:14:04,428 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:41, output treesize:37 [2018-01-24 15:14:04,459 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 15:14:04,462 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 15:14:04,467 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 15:14:04,467 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 15:14:04,473 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:14:04,481 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 15:14:04,481 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:52, output treesize:48 [2018-01-24 15:14:04,760 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 15:14:04,761 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 45 treesize of output 41 [2018-01-24 15:14:04,764 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 15:14:04,769 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 3 disjoint index pairs (out of 3 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 27 treesize of output 41 [2018-01-24 15:14:04,770 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-24 15:14:04,784 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 15:14:04,784 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-24 15:14:04,791 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-24 15:14:04,806 INFO L267 ElimStorePlain]: Start of recursive call 1: 4 dim-0 vars, 1 dim-2 vars, End of recursive call: 4 dim-0 vars, and 2 xjuncts. [2018-01-24 15:14:04,807 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 5 variables, input treesize:73, output treesize:122 [2018-01-24 15:14:04,965 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 15:14:04,966 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-01-24 15:14:05,318 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 35 treesize of output 31 [2018-01-24 15:14:05,335 INFO L682 Elim1Store]: detected equality via solver [2018-01-24 15:14:05,337 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 5 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 12 [2018-01-24 15:14:05,337 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 15:14:05,341 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:14:05,349 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 15:14:05,349 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:48, output treesize:64 [2018-01-24 15:14:05,559 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 24 treesize of output 27 [2018-01-24 15:14:05,574 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 15:14:05,575 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 15:14:05,579 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:14:05,591 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 15:14:05,591 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-24 15:14:05,608 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 26 treesize of output 20 [2018-01-24 15:14:05,609 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-24 15:14:05,618 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 20 treesize of output 23 [2018-01-24 15:14:05,631 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 15:14:05,631 INFO L267 ElimStorePlain]: Start of recursive call 7: End of recursive call: and 1 xjuncts. [2018-01-24 15:14:05,635 INFO L267 ElimStorePlain]: Start of recursive call 6: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:14:05,642 INFO L267 ElimStorePlain]: Start of recursive call 1: 4 dim-0 vars, 4 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-24 15:14:05,642 INFO L202 ElimStorePlain]: Needed 7 recursive calls to eliminate 8 variables, input treesize:64, output treesize:17 [2018-01-24 15:14:05,712 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 15:14:05,732 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-24 15:14:05,732 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode CVC4_IG No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 Starting monitored process 9 with cvc4 --tear-down-incremental --print-success --lang smt --rewrite-divk --tlimit-per=12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with cvc4 --tear-down-incremental --print-success --lang smt --rewrite-divk --tlimit-per=12000 [2018-01-24 15:14:05,735 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 15:14:05,735 INFO L280 anRefinementStrategy]: Using traceCheck mode CVC4_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-01-24 15:14:05,791 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 15:14:05,797 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-24 15:14:05,804 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 15:14:05,805 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 15:14:05,821 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 15:14:05,821 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 15:14:05,835 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:14:05,835 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:27, output treesize:25 [2018-01-24 15:14:05,925 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 15:14:05,926 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 15:14:05,926 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 15:14:05,927 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 15:14:05,939 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 15:14:05,939 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 15:14:05,940 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 15:14:05,940 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 15:14:05,947 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:14:05,947 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:36, output treesize:25 [2018-01-24 15:14:06,038 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 15:14:06,040 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 15:14:06,040 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 15:14:06,041 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:14:06,048 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 15:14:06,048 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:41, output treesize:37 [2018-01-24 15:14:06,099 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 15:14:06,106 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 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 15:14:06,108 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 15:14:06,108 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 15:14:06,113 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:14:06,121 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 15:14:06,121 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:52, output treesize:48 [2018-01-24 15:14:06,418 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 15:14:06,420 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 45 treesize of output 41 [2018-01-24 15:14:06,423 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 15:14:06,431 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 3 disjoint index pairs (out of 3 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 27 treesize of output 41 [2018-01-24 15:14:06,431 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-24 15:14:06,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, 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 15:14:06,447 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-24 15:14:06,456 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-24 15:14:06,475 INFO L267 ElimStorePlain]: Start of recursive call 1: 4 dim-0 vars, 1 dim-2 vars, End of recursive call: 4 dim-0 vars, and 2 xjuncts. [2018-01-24 15:14:06,475 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 5 variables, input treesize:76, output treesize:122 [2018-01-24 15:14:06,540 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 15:14:06,540 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-01-24 15:14:06,845 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 35 treesize of output 31 [2018-01-24 15:14:06,861 INFO L682 Elim1Store]: detected equality via solver [2018-01-24 15:14:06,863 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 12 [2018-01-24 15:14:06,863 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 15:14:06,867 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:14:06,876 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:14:06,877 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:47, output treesize:23 [2018-01-24 15:14:07,062 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 15:14:07,062 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 15:14:07,067 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 3 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 15 [2018-01-24 15:14:07,074 WARN L307 Elim1Store]: Array PQE input equivalent to true [2018-01-24 15:14:07,075 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-24 15:14:07,076 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 15:14:07,076 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-24 15:14:07,078 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 15:14:07,082 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 15:14:07,082 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 4 variables, input treesize:31, output treesize:14 [2018-01-24 15:14:07,200 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 15:14:07,202 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 5 imperfect interpolant sequences. [2018-01-24 15:14:07,202 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 17, 15, 17, 15] total 62 [2018-01-24 15:14:07,202 INFO L247 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-01-24 15:14:07,203 INFO L409 AbstractCegarLoop]: Interpolant automaton has 32 states [2018-01-24 15:14:07,203 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2018-01-24 15:14:07,204 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=345, Invalid=3561, Unknown=0, NotChecked=0, Total=3906 [2018-01-24 15:14:07,204 INFO L87 Difference]: Start difference. First operand 150 states and 194 transitions. Second operand 32 states. [2018-01-24 15:14:07,957 WARN L146 SmtUtils]: Spent 391ms on a formula simplification. DAG size of input: 81 DAG size of output 52 [2018-01-24 15:14:10,341 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 15:14:10,341 INFO L93 Difference]: Finished difference Result 427 states and 537 transitions. [2018-01-24 15:14:10,341 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2018-01-24 15:14:10,341 INFO L78 Accepts]: Start accepts. Automaton has 32 states. Word has length 29 [2018-01-24 15:14:10,342 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 15:14:10,343 INFO L225 Difference]: With dead ends: 427 [2018-01-24 15:14:10,343 INFO L226 Difference]: Without dead ends: 423 [2018-01-24 15:14:10,345 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 157 GetRequests, 64 SyntacticMatches, 10 SemanticMatches, 83 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2120 ImplicationChecksByTransitivity, 5.0s TimeCoverageRelationStatistics Valid=849, Invalid=6291, Unknown=0, NotChecked=0, Total=7140 [2018-01-24 15:14:10,345 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 423 states. [2018-01-24 15:14:10,361 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 423 to 181. [2018-01-24 15:14:10,362 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 181 states. [2018-01-24 15:14:10,363 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 181 states to 181 states and 237 transitions. [2018-01-24 15:14:10,363 INFO L78 Accepts]: Start accepts. Automaton has 181 states and 237 transitions. Word has length 29 [2018-01-24 15:14:10,363 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 15:14:10,364 INFO L432 AbstractCegarLoop]: Abstraction has 181 states and 237 transitions. [2018-01-24 15:14:10,364 INFO L433 AbstractCegarLoop]: Interpolant automaton has 32 states. [2018-01-24 15:14:10,364 INFO L276 IsEmpty]: Start isEmpty. Operand 181 states and 237 transitions. [2018-01-24 15:14:10,365 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2018-01-24 15:14:10,365 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 15:14:10,365 INFO L322 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-24 15:14:10,365 INFO L371 AbstractCegarLoop]: === Iteration 15 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 15:14:10,366 INFO L82 PathProgramCache]: Analyzing trace with hash 933708271, now seen corresponding path program 1 times [2018-01-24 15:14:10,366 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 15:14:10,367 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:14:10,367 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 15:14:10,367 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:14:10,367 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 15:14:10,378 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 15:14:10,379 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 15:14:10,439 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 1 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-24 15:14:10,439 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-24 15:14:10,439 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-01-24 15:14:10,440 INFO L199 CegarAbsIntRunner]: Running AI on error trace of length 33 with the following transitions: [2018-01-24 15:14:10,440 INFO L201 CegarAbsIntRunner]: [0], [1], [5], [10], [16], [20], [27], [28], [29], [30], [31], [32], [35], [46], [50], [52], [57], [65], [67], [70], [71], [73], [74], [77], [85], [103], [104], [105], [107] [2018-01-24 15:14:10,441 INFO L147 AbstractInterpreter]: Using domain VPDomain [2018-01-24 15:14:10,441 INFO L101 FixpointEngine]: Starting fixpoint engine with domain VPDomain (maxUnwinding=3, maxParallelStates=2) [2018-01-24 15:14:20,991 INFO L259 AbstractInterpreter]: Some error location(s) were reachable [2018-01-24 15:14:20,991 INFO L268 AbstractInterpreter]: Visited 29 different actions 51 times. Merged at 8 different actions 22 times. Never widened. Found 1 fixpoints after 1 different actions. Largest state had 30 variables. [2018-01-24 15:14:20,997 INFO L434 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: Unknown [2018-01-24 15:14:20,997 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-24 15:14:20,997 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-24 15:14:21,002 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 15:14:21,002 INFO L280 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-01-24 15:14:21,016 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 15:14:21,018 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-24 15:14:21,030 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 1 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-24 15:14:21,030 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-01-24 15:14:21,046 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 1 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-24 15:14:21,067 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-24 15:14:21,067 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode CVC4_IG No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 Starting monitored process 11 with cvc4 --tear-down-incremental --print-success --lang smt --rewrite-divk --tlimit-per=12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 11 with cvc4 --tear-down-incremental --print-success --lang smt --rewrite-divk --tlimit-per=12000 [2018-01-24 15:14:21,070 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 15:14:21,070 INFO L280 anRefinementStrategy]: Using traceCheck mode CVC4_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-01-24 15:14:21,104 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 15:14:21,108 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-24 15:14:21,119 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 1 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-24 15:14:21,119 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-01-24 15:14:21,128 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 1 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-24 15:14:21,129 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 5 imperfect interpolant sequences. [2018-01-24 15:14:21,129 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7, 7, 7] total 7 [2018-01-24 15:14:21,129 INFO L247 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-01-24 15:14:21,130 INFO L409 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-01-24 15:14:21,130 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-01-24 15:14:21,130 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2018-01-24 15:14:21,130 INFO L87 Difference]: Start difference. First operand 181 states and 237 transitions. Second operand 7 states. [2018-01-24 15:14:21,201 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 15:14:21,201 INFO L93 Difference]: Finished difference Result 257 states and 332 transitions. [2018-01-24 15:14:21,201 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-01-24 15:14:21,201 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 32 [2018-01-24 15:14:21,202 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 15:14:21,203 INFO L225 Difference]: With dead ends: 257 [2018-01-24 15:14:21,203 INFO L226 Difference]: Without dead ends: 171 [2018-01-24 15:14:21,204 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 137 GetRequests, 124 SyntacticMatches, 4 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=31, Invalid=79, Unknown=0, NotChecked=0, Total=110 [2018-01-24 15:14:21,204 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 171 states. [2018-01-24 15:14:21,212 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 171 to 114. [2018-01-24 15:14:21,212 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 114 states. [2018-01-24 15:14:21,212 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 114 states to 114 states and 135 transitions. [2018-01-24 15:14:21,212 INFO L78 Accepts]: Start accepts. Automaton has 114 states and 135 transitions. Word has length 32 [2018-01-24 15:14:21,213 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 15:14:21,213 INFO L432 AbstractCegarLoop]: Abstraction has 114 states and 135 transitions. [2018-01-24 15:14:21,213 INFO L433 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-01-24 15:14:21,213 INFO L276 IsEmpty]: Start isEmpty. Operand 114 states and 135 transitions. [2018-01-24 15:14:21,213 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2018-01-24 15:14:21,214 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 15:14:21,214 INFO L322 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-24 15:14:21,214 INFO L371 AbstractCegarLoop]: === Iteration 16 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 15:14:21,214 INFO L82 PathProgramCache]: Analyzing trace with hash 799694765, now seen corresponding path program 1 times [2018-01-24 15:14:21,214 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-24 15:14:21,215 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:14:21,215 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 15:14:21,215 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 15:14:21,215 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-24 15:14:21,224 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 15:14:21,225 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 15:14:21,420 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-24 15:14:21,420 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-24 15:14:21,420 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-01-24 15:14:21,420 INFO L199 CegarAbsIntRunner]: Running AI on error trace of length 33 with the following transitions: [2018-01-24 15:14:21,420 INFO L201 CegarAbsIntRunner]: [0], [1], [5], [10], [16], [22], [27], [28], [29], [30], [31], [32], [35], [46], [50], [52], [57], [65], [67], [70], [71], [73], [74], [77], [85], [103], [104], [105], [107] [2018-01-24 15:14:21,422 INFO L147 AbstractInterpreter]: Using domain VPDomain [2018-01-24 15:14:21,422 INFO L101 FixpointEngine]: Starting fixpoint engine with domain VPDomain (maxUnwinding=3, maxParallelStates=2) Received shutdown request... [2018-01-24 15:14:28,090 WARN L571 FixpointEngine]: Received timeout, aborting fixpoint engine [2018-01-24 15:14:28,090 WARN L157 AbstractInterpreter]: Abstract interpretation run out of time [2018-01-24 15:14:28,090 INFO L434 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-01-24 15:14:28,090 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-24 15:14:28,091 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-24 15:14:28,096 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 15:14:28,096 INFO L280 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-01-24 15:14:28,113 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 15:14:28,116 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-24 15:14:28,117 INFO L175 TraceCheckSpWp]: Timeout while computing interpolants [2018-01-24 15:14:28,118 WARN L491 AbstractCegarLoop]: Verification canceled [2018-01-24 15:14:28,121 WARN L187 ceAbstractionStarter]: Timeout [2018-01-24 15:14:28,122 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 24.01 03:14:28 BoogieIcfgContainer [2018-01-24 15:14:28,122 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-01-24 15:14:28,123 INFO L168 Benchmark]: Toolchain (without parser) took 51890.63 ms. Allocated memory was 303.6 MB in the beginning and 1.3 GB in the end (delta: 1.0 GB). Free memory was 263.6 MB in the beginning and 811.9 MB in the end (delta: -548.3 MB). Peak memory consumption was 452.0 MB. Max. memory is 5.3 GB. [2018-01-24 15:14:28,123 INFO L168 Benchmark]: CDTParser took 0.12 ms. Allocated memory is still 303.6 MB. Free memory is still 269.6 MB. There was no memory consumed. Max. memory is 5.3 GB. [2018-01-24 15:14:28,123 INFO L168 Benchmark]: CACSL2BoogieTranslator took 207.80 ms. Allocated memory is still 303.6 MB. Free memory was 262.6 MB in the beginning and 252.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 15:14:28,124 INFO L168 Benchmark]: Boogie Preprocessor took 37.54 ms. Allocated memory is still 303.6 MB. Free memory was 252.5 MB in the beginning and 250.4 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 5.3 GB. [2018-01-24 15:14:28,124 INFO L168 Benchmark]: RCFGBuilder took 307.73 ms. Allocated memory is still 303.6 MB. Free memory was 250.4 MB in the beginning and 230.8 MB in the end (delta: 19.6 MB). Peak memory consumption was 19.6 MB. Max. memory is 5.3 GB. [2018-01-24 15:14:28,124 INFO L168 Benchmark]: TraceAbstraction took 51330.14 ms. Allocated memory was 303.6 MB in the beginning and 1.3 GB in the end (delta: 1.0 GB). Free memory was 229.9 MB in the beginning and 811.9 MB in the end (delta: -582.1 MB). Peak memory consumption was 418.3 MB. Max. memory is 5.3 GB. [2018-01-24 15:14:28,126 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.12 ms. Allocated memory is still 303.6 MB. Free memory is still 269.6 MB. There was no memory consumed. Max. memory is 5.3 GB. * CACSL2BoogieTranslator took 207.80 ms. Allocated memory is still 303.6 MB. Free memory was 262.6 MB in the beginning and 252.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 37.54 ms. Allocated memory is still 303.6 MB. Free memory was 252.5 MB in the beginning and 250.4 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 5.3 GB. * RCFGBuilder took 307.73 ms. Allocated memory is still 303.6 MB. Free memory was 250.4 MB in the beginning and 230.8 MB in the end (delta: 19.6 MB). Peak memory consumption was 19.6 MB. Max. memory is 5.3 GB. * TraceAbstraction took 51330.14 ms. Allocated memory was 303.6 MB in the beginning and 1.3 GB in the end (delta: 1.0 GB). Free memory was 229.9 MB in the beginning and 811.9 MB in the end (delta: -582.1 MB). Peak memory consumption was 418.3 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) : 2.218077 RENAME_VARIABLES(MILLISECONDS) : 0.478358 UNFREEZE(MILLISECONDS) : 0.000000 CONJOIN(MILLISECONDS) : 2.145862 PROJECTAWAY(MILLISECONDS) : 1.236183 ADD_WEAK_EQUALITY(MILLISECONDS) : 0.121756 DISJOIN(MILLISECONDS) : 0.325382 RENAME_VARIABLES_DISJUNCTIVE(MILLISECONDS) : 0.518849 ADD_EQUALITY(MILLISECONDS) : 0.022508 DISJOIN_DISJUNCTIVE(MILLISECONDS) : 0.000000 ADD_DISEQUALITY(MILLISECONDS) : 0.018030 #CONJOIN_DISJUNCTIVE : 48 #RENAME_VARIABLES : 72 #UNFREEZE : 0 #CONJOIN : 96 #PROJECTAWAY : 66 #ADD_WEAK_EQUALITY : 9 #DISJOIN : 6 #RENAME_VARIABLES_DISJUNCTIVE : 69 #ADD_EQUALITY : 61 #DISJOIN_DISJUNCTIVE : 0 #ADD_DISEQUALITY : 3 - StatisticsResult: ArrayEqualityDomainStatistics #Locations : 21 LocStat_MAX_WEQGRAPH_SIZE : 5 LocStat_MAX_SIZEOF_WEQEDGELABEL : 2 LocStat_NO_SUPPORTING_EQUALITIES : 266 LocStat_NO_SUPPORTING_DISEQUALITIES : 35 LocStat_NO_DISJUNCTIONS : -42 LocStat_MAX_NO_DISJUNCTIONS : -1 #Transitions : 28 TransStat_MAX_WEQGRAPH_SIZE : 2 TransStat_MAX_SIZEOF_WEQEDGELABEL : 1 TransStat_NO_SUPPORTING_EQUALITIES : 59 TransStat_NO_SUPPORTING_DISEQUALITIES : 5 TransStat_NO_DISJUNCTIONS : 29 TransStat_MAX_NO_DISJUNCTIONS : 2 - StatisticsResult: EqConstraintFactoryStatistics CONJOIN_DISJUNCTIVE(MILLISECONDS) : 1.985980 RENAME_VARIABLES(MILLISECONDS) : 0.439160 UNFREEZE(MILLISECONDS) : 0.000000 CONJOIN(MILLISECONDS) : 1.937421 PROJECTAWAY(MILLISECONDS) : 0.948056 ADD_WEAK_EQUALITY(MILLISECONDS) : 0.133215 DISJOIN(MILLISECONDS) : 0.246912 RENAME_VARIABLES_DISJUNCTIVE(MILLISECONDS) : 0.470498 ADD_EQUALITY(MILLISECONDS) : 0.014335 DISJOIN_DISJUNCTIVE(MILLISECONDS) : 0.000000 ADD_DISEQUALITY(MILLISECONDS) : 0.009084 #CONJOIN_DISJUNCTIVE : 47 #RENAME_VARIABLES : 72 #UNFREEZE : 0 #CONJOIN : 95 #PROJECTAWAY : 66 #ADD_WEAK_EQUALITY : 9 #DISJOIN : 6 #RENAME_VARIABLES_DISJUNCTIVE : 69 #ADD_EQUALITY : 61 #DISJOIN_DISJUNCTIVE : 0 #ADD_DISEQUALITY : 3 - StatisticsResult: ArrayEqualityDomainStatistics #Locations : 28 LocStat_MAX_WEQGRAPH_SIZE : 5 LocStat_MAX_SIZEOF_WEQEDGELABEL : 2 LocStat_NO_SUPPORTING_EQUALITIES : 422 LocStat_NO_SUPPORTING_DISEQUALITIES : 56 LocStat_NO_DISJUNCTIONS : -56 LocStat_MAX_NO_DISJUNCTIONS : -1 #Transitions : 35 TransStat_MAX_WEQGRAPH_SIZE : 2 TransStat_MAX_SIZEOF_WEQEDGELABEL : 1 TransStat_NO_SUPPORTING_EQUALITIES : 77 TransStat_NO_SUPPORTING_DISEQUALITIES : 6 TransStat_NO_DISJUNCTIONS : 38 TransStat_MAX_NO_DISJUNCTIONS : 2 - StatisticsResult: EqConstraintFactoryStatistics CONJOIN_DISJUNCTIVE(MILLISECONDS) : 18.005771 RENAME_VARIABLES(MILLISECONDS) : 2.018503 UNFREEZE(MILLISECONDS) : 0.000000 CONJOIN(MILLISECONDS) : 17.952500 PROJECTAWAY(MILLISECONDS) : 14.062518 ADD_WEAK_EQUALITY(MILLISECONDS) : 0.053081 DISJOIN(MILLISECONDS) : 2.009082 RENAME_VARIABLES_DISJUNCTIVE(MILLISECONDS) : 2.047432 ADD_EQUALITY(MILLISECONDS) : 0.013173 DISJOIN_DISJUNCTIVE(MILLISECONDS) : 0.000000 ADD_DISEQUALITY(MILLISECONDS) : 0.009331 #CONJOIN_DISJUNCTIVE : 99 #RENAME_VARIABLES : 176 #UNFREEZE : 0 #CONJOIN : 172 #PROJECTAWAY : 131 #ADD_WEAK_EQUALITY : 11 #DISJOIN : 34 #RENAME_VARIABLES_DISJUNCTIVE : 157 #ADD_EQUALITY : 80 #DISJOIN_DISJUNCTIVE : 0 #ADD_DISEQUALITY : 4 * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 570). Cancelled while BasicCegarLoop was analyzing trace of length 33 with TraceHistMax 2, while TraceCheckSpWp was constructing forward predicates, while XnfDer was eliminating 1 quantified variables from 1 xjuncts. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 569). Cancelled while BasicCegarLoop was analyzing trace of length 33 with TraceHistMax 2, while TraceCheckSpWp was constructing forward predicates, while XnfDer was eliminating 1 quantified variables from 1 xjuncts. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 570). Cancelled while BasicCegarLoop was analyzing trace of length 33 with TraceHistMax 2, while TraceCheckSpWp was constructing forward predicates, while XnfDer was eliminating 1 quantified variables from 1 xjuncts. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 569). Cancelled while BasicCegarLoop was analyzing trace of length 33 with TraceHistMax 2, while TraceCheckSpWp was constructing forward predicates, while XnfDer was eliminating 1 quantified variables from 1 xjuncts. - TimeoutResultAtElement [Line: 553]: Timeout (TraceAbstraction) Unable to prove that all allocated memory was freed (line 553). Cancelled while BasicCegarLoop was analyzing trace of length 33 with TraceHistMax 2, while TraceCheckSpWp was constructing forward predicates, while XnfDer was eliminating 1 quantified variables from 1 xjuncts. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 549). Cancelled while BasicCegarLoop was analyzing trace of length 33 with TraceHistMax 2, while TraceCheckSpWp was constructing forward predicates, while XnfDer was eliminating 1 quantified variables from 1 xjuncts. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 545). Cancelled while BasicCegarLoop was analyzing trace of length 33 with TraceHistMax 2, while TraceCheckSpWp was constructing forward predicates, while XnfDer was eliminating 1 quantified variables from 1 xjuncts. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 543). Cancelled while BasicCegarLoop was analyzing trace of length 33 with TraceHistMax 2, while TraceCheckSpWp was constructing forward predicates, while XnfDer was eliminating 1 quantified variables from 1 xjuncts. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 545). Cancelled while BasicCegarLoop was analyzing trace of length 33 with TraceHistMax 2, while TraceCheckSpWp was constructing forward predicates, while XnfDer was eliminating 1 quantified variables from 1 xjuncts. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 550). Cancelled while BasicCegarLoop was analyzing trace of length 33 with TraceHistMax 2, while TraceCheckSpWp was constructing forward predicates, while XnfDer was eliminating 1 quantified variables from 1 xjuncts. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 543). Cancelled while BasicCegarLoop was analyzing trace of length 33 with TraceHistMax 2, while TraceCheckSpWp was constructing forward predicates, while XnfDer was eliminating 1 quantified variables from 1 xjuncts. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 545). Cancelled while BasicCegarLoop was analyzing trace of length 33 with TraceHistMax 2, while TraceCheckSpWp was constructing forward predicates, while XnfDer was eliminating 1 quantified variables from 1 xjuncts. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 550). Cancelled while BasicCegarLoop was analyzing trace of length 33 with TraceHistMax 2, while TraceCheckSpWp was constructing forward predicates, while XnfDer was eliminating 1 quantified variables from 1 xjuncts. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 549). Cancelled while BasicCegarLoop was analyzing trace of length 33 with TraceHistMax 2, while TraceCheckSpWp was constructing forward predicates, while XnfDer was eliminating 1 quantified variables from 1 xjuncts. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 545). Cancelled while BasicCegarLoop was analyzing trace of length 33 with TraceHistMax 2, while TraceCheckSpWp was constructing forward predicates, while XnfDer was eliminating 1 quantified variables from 1 xjuncts. - StatisticsResult: Ultimate Automizer benchmark data CFG has 4 procedures, 58 locations, 15 error locations. TIMEOUT Result, 51.2s OverallTime, 16 OverallIterations, 4 TraceHistogramMax, 14.7s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 721 SDtfs, 2013 SDslu, 3826 SDs, 0 SdLazy, 3122 SolverSat, 581 SolverUnsat, 2 SolverUnknown, 0 SolverNotchecked, 6.5s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 764 GetRequests, 385 SyntacticMatches, 39 SemanticMatches, 340 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5540 ImplicationChecksByTransitivity, 20.5s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=181occurred in iteration=14, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 19.0s AbstIntTime, 4 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, AutomataMinimizationStatistics: 0.1s AutomataMinimizationTime, 15 MinimizatonAttempts, 584 StatesRemovedByMinimization, 8 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.6s SatisfiabilityAnalysisTime, 15.9s InterpolantComputationTime, 595 NumberOfCodeBlocks, 595 NumberOfCodeBlocksAsserted, 33 NumberOfCheckSat, 838 ConstructedInterpolants, 111 QuantifiedInterpolants, 268695 SizeOfPredicates, 153 NumberOfNonLiveVariables, 1370 ConjunctsInSsa, 361 ConjunctsInUnsatCore, 35 InterpolantComputations, 10 PerfectInterpolantSequences, 9/215 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, REUSE_STATISTICS: No data available RESULT: Ultimate could not prove your program: Timeout Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/cstrncat-alloca_true-valid-memsafety_true-termination.i_svcomp-DerefFreeMemtrack-32bit-Automizer_Taipan+AI_EQ.epf_AutomizerC.xml/Csv-Benchmark-0-2018-01-24_15-14-28-139.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.epf_AutomizerC.xml/Csv-VPDomainBenchmark-0-2018-01-24_15-14-28-139.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.epf_AutomizerC.xml/Csv-BenchmarkWithCounters-0-2018-01-24_15-14-28-139.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.epf_AutomizerC.xml/Csv-VPDomainBenchmark-1-2018-01-24_15-14-28-139.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.epf_AutomizerC.xml/Csv-BenchmarkWithCounters-1-2018-01-24_15-14-28-139.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.epf_AutomizerC.xml/Csv-VPDomainBenchmark-2-2018-01-24_15-14-28-139.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.epf_AutomizerC.xml/Csv-BenchmarkWithCounters-2-2018-01-24_15-14-28-139.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.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-0-2018-01-24_15-14-28-139.csv Completed graceful shutdown