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_Camel+AI_EQ.epf -i ../../../trunk/examples/svcomp/array-memsafety/openbsd_cstrncat-alloca_true-valid-memsafety_true-termination.i -------------------------------------------------------------------------------- This is Ultimate 0.1.23-6b94a2f [2018-01-24 11:46:34,603 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-01-24 11:46:34,679 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-01-24 11:46:34,691 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-01-24 11:46:34,691 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-01-24 11:46:34,692 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-01-24 11:46:34,693 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-01-24 11:46:34,694 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-01-24 11:46:34,695 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-01-24 11:46:34,696 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-01-24 11:46:34,697 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-01-24 11:46:34,697 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-01-24 11:46:34,698 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-01-24 11:46:34,700 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-01-24 11:46:34,701 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-01-24 11:46:34,703 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-01-24 11:46:34,705 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-01-24 11:46:34,707 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-01-24 11:46:34,708 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-01-24 11:46:34,709 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-01-24 11:46:34,711 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-01-24 11:46:34,712 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-01-24 11:46:34,712 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-01-24 11:46:34,713 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-01-24 11:46:34,714 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-01-24 11:46:34,715 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-01-24 11:46:34,715 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-01-24 11:46:34,716 INFO L177 SettingsManager]: PEA to Boogie provides no preferences, ignoring... [2018-01-24 11:46:34,716 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-01-24 11:46:34,716 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-01-24 11:46:34,717 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-01-24 11:46:34,717 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/ai/eq-bench/svcomp-DerefFreeMemtrack-32bit-Automizer_Camel+AI_EQ.epf [2018-01-24 11:46:34,727 INFO L110 SettingsManager]: Loading preferences was successful [2018-01-24 11:46:34,727 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-01-24 11:46:34,728 INFO L131 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2018-01-24 11:46:34,728 INFO L133 SettingsManager]: * to procedures, called more than once=true [2018-01-24 11:46:34,728 INFO L131 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2018-01-24 11:46:34,728 INFO L133 SettingsManager]: * Abstract domain for RCFG-of-the-future=VPDomain [2018-01-24 11:46:34,729 INFO L133 SettingsManager]: * Use the RCFG-of-the-future interface=true [2018-01-24 11:46:34,729 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-01-24 11:46:34,729 INFO L133 SettingsManager]: * sizeof long=4 [2018-01-24 11:46:34,729 INFO L133 SettingsManager]: * Check unreachability of error function in SV-COMP mode=false [2018-01-24 11:46:34,730 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-01-24 11:46:34,730 INFO L133 SettingsManager]: * sizeof POINTER=4 [2018-01-24 11:46:34,730 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-01-24 11:46:34,730 INFO L133 SettingsManager]: * Check for the main procedure if all allocated memory was freed=true [2018-01-24 11:46:34,730 INFO L133 SettingsManager]: * Bitprecise bitfields=true [2018-01-24 11:46:34,731 INFO L133 SettingsManager]: * SV-COMP memtrack compatibility mode=true [2018-01-24 11:46:34,731 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-01-24 11:46:34,731 INFO L133 SettingsManager]: * sizeof long double=12 [2018-01-24 11:46:34,731 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-01-24 11:46:34,731 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-01-24 11:46:34,731 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-01-24 11:46:34,732 INFO L133 SettingsManager]: * Add additional assume for each assert=false [2018-01-24 11:46:34,732 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-01-24 11:46:34,732 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-01-24 11:46:34,732 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-01-24 11:46:34,732 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-01-24 11:46:34,733 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-01-24 11:46:34,733 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-01-24 11:46:34,733 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-01-24 11:46:34,733 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-01-24 11:46:34,733 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-01-24 11:46:34,734 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-01-24 11:46:34,734 INFO L131 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2018-01-24 11:46:34,735 INFO L133 SettingsManager]: * TransformationType=HEAP_SEPARATOR [2018-01-24 11:46:34,768 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-01-24 11:46:34,777 INFO L266 ainManager$Toolchain]: [Toolchain 1]: Parser(s) successfully initialized [2018-01-24 11:46:34,779 INFO L222 ainManager$Toolchain]: [Toolchain 1]: Toolchain data selected. [2018-01-24 11:46:34,780 INFO L271 PluginConnector]: Initializing CDTParser... [2018-01-24 11:46:34,781 INFO L276 PluginConnector]: CDTParser initialized [2018-01-24 11:46:34,781 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/array-memsafety/openbsd_cstrncat-alloca_true-valid-memsafety_true-termination.i [2018-01-24 11:46:34,926 INFO L304 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-01-24 11:46:34,932 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2018-01-24 11:46:34,933 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2018-01-24 11:46:34,933 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2018-01-24 11:46:34,938 INFO L276 PluginConnector]: CACSL2BoogieTranslator initialized [2018-01-24 11:46:34,938 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 24.01 11:46:34" (1/1) ... [2018-01-24 11:46:34,940 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@5e437857 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.01 11:46:34, skipping insertion in model container [2018-01-24 11:46:34,941 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 24.01 11:46:34" (1/1) ... [2018-01-24 11:46:34,957 INFO L153 Dispatcher]: Using SV-COMP mode [2018-01-24 11:46:34,997 INFO L153 Dispatcher]: Using SV-COMP mode [2018-01-24 11:46:35,113 INFO L450 PostProcessor]: Settings: Checked method=main [2018-01-24 11:46:35,129 INFO L450 PostProcessor]: Settings: Checked method=main [2018-01-24 11:46:35,135 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.01 11:46:35 WrapperNode [2018-01-24 11:46:35,135 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2018-01-24 11:46:35,135 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-01-24 11:46:35,135 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-01-24 11:46:35,136 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-01-24 11:46:35,147 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.01 11:46:35" (1/1) ... [2018-01-24 11:46:35,147 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.01 11:46:35" (1/1) ... [2018-01-24 11:46:35,158 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.01 11:46:35" (1/1) ... [2018-01-24 11:46:35,158 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.01 11:46:35" (1/1) ... [2018-01-24 11:46:35,162 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.01 11:46:35" (1/1) ... [2018-01-24 11:46:35,165 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.01 11:46:35" (1/1) ... [2018-01-24 11:46:35,166 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.01 11:46:35" (1/1) ... [2018-01-24 11:46:35,168 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-01-24 11:46:35,168 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-01-24 11:46:35,168 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-01-24 11:46:35,169 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-01-24 11:46:35,169 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.01 11:46:35" (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 11:46:35,216 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2018-01-24 11:46:35,217 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-01-24 11:46:35,217 INFO L136 BoogieDeclarations]: Found implementation of procedure cstrncat [2018-01-24 11:46:35,217 INFO L136 BoogieDeclarations]: Found implementation of procedure main [2018-01-24 11:46:35,217 INFO L128 BoogieDeclarations]: Found specification of procedure write~int [2018-01-24 11:46:35,217 INFO L128 BoogieDeclarations]: Found specification of procedure read~int [2018-01-24 11:46:35,217 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.free [2018-01-24 11:46:35,217 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2018-01-24 11:46:35,217 INFO L128 BoogieDeclarations]: Found specification of procedure #Ultimate.alloc [2018-01-24 11:46:35,217 INFO L128 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2018-01-24 11:46:35,218 INFO L128 BoogieDeclarations]: Found specification of procedure cstrncat [2018-01-24 11:46:35,218 INFO L128 BoogieDeclarations]: Found specification of procedure main [2018-01-24 11:46:35,218 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2018-01-24 11:46:35,218 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-01-24 11:46:35,443 INFO L257 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-01-24 11:46:35,444 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 24.01 11:46:35 BoogieIcfgContainer [2018-01-24 11:46:35,444 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-01-24 11:46:35,445 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-01-24 11:46:35,445 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-01-24 11:46:35,446 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-01-24 11:46:35,447 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 24.01 11:46:34" (1/3) ... [2018-01-24 11:46:35,447 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4ea4ba66 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 24.01 11:46:35, skipping insertion in model container [2018-01-24 11:46:35,448 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.01 11:46:35" (2/3) ... [2018-01-24 11:46:35,448 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4ea4ba66 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 24.01 11:46:35, skipping insertion in model container [2018-01-24 11:46:35,448 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 24.01 11:46:35" (3/3) ... [2018-01-24 11:46:35,451 INFO L105 eAbstractionObserver]: Analyzing ICFG openbsd_cstrncat-alloca_true-valid-memsafety_true-termination.i [2018-01-24 11:46:35,459 INFO L130 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-01-24 11:46:35,464 INFO L142 ceAbstractionStarter]: Appying trace abstraction to program that has 13 error locations. [2018-01-24 11:46:35,503 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-24 11:46:35,503 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-24 11:46:35,503 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-24 11:46:35,503 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-24 11:46:35,504 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-24 11:46:35,504 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-24 11:46:35,504 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-24 11:46:35,504 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-01-24 11:46:35,505 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-24 11:46:35,526 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states. [2018-01-24 11:46:35,533 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2018-01-24 11:46:35,533 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 11:46:35,534 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-24 11:46:35,534 INFO L371 AbstractCegarLoop]: === Iteration 1 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 11:46:35,538 INFO L82 PathProgramCache]: Analyzing trace with hash 2055638365, now seen corresponding path program 1 times [2018-01-24 11:46:35,539 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-24 11:46:35,539 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-24 11:46:35,578 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 11:46:35,578 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 11:46:35,578 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 11:46:35,622 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 11:46:35,630 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 11:46:35,682 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-24 11:46:35,685 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 11:46:35,685 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-01-24 11:46:35,687 INFO L409 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-01-24 11:46:35,701 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-01-24 11:46:35,702 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-24 11:46:35,704 INFO L87 Difference]: Start difference. First operand 54 states. Second operand 3 states. [2018-01-24 11:46:35,903 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 11:46:35,903 INFO L93 Difference]: Finished difference Result 81 states and 93 transitions. [2018-01-24 11:46:35,904 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-01-24 11:46:35,905 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 11 [2018-01-24 11:46:35,906 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 11:46:35,918 INFO L225 Difference]: With dead ends: 81 [2018-01-24 11:46:35,918 INFO L226 Difference]: Without dead ends: 51 [2018-01-24 11:46:35,922 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 11:46:35,941 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2018-01-24 11:46:35,960 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 51. [2018-01-24 11:46:35,961 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 51 states. [2018-01-24 11:46:35,963 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 57 transitions. [2018-01-24 11:46:35,965 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 57 transitions. Word has length 11 [2018-01-24 11:46:35,965 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 11:46:35,965 INFO L432 AbstractCegarLoop]: Abstraction has 51 states and 57 transitions. [2018-01-24 11:46:35,966 INFO L433 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-01-24 11:46:35,966 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 57 transitions. [2018-01-24 11:46:35,966 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2018-01-24 11:46:35,966 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 11:46:35,967 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-24 11:46:35,967 INFO L371 AbstractCegarLoop]: === Iteration 2 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 11:46:35,967 INFO L82 PathProgramCache]: Analyzing trace with hash -1872133330, now seen corresponding path program 1 times [2018-01-24 11:46:35,967 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-24 11:46:35,967 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-24 11:46:35,969 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 11:46:35,969 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 11:46:35,969 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 11:46:35,980 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 11:46:35,981 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 11:46:36,028 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 11:46:36,028 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 11:46:36,029 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-01-24 11:46:36,030 INFO L409 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-01-24 11:46:36,031 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-01-24 11:46:36,031 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-01-24 11:46:36,031 INFO L87 Difference]: Start difference. First operand 51 states and 57 transitions. Second operand 5 states. [2018-01-24 11:46:36,114 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 11:46:36,114 INFO L93 Difference]: Finished difference Result 95 states and 106 transitions. [2018-01-24 11:46:36,115 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-01-24 11:46:36,115 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 15 [2018-01-24 11:46:36,115 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 11:46:36,116 INFO L225 Difference]: With dead ends: 95 [2018-01-24 11:46:36,116 INFO L226 Difference]: Without dead ends: 51 [2018-01-24 11:46:36,118 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 11:46:36,118 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2018-01-24 11:46:36,123 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 51. [2018-01-24 11:46:36,123 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 51 states. [2018-01-24 11:46:36,125 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 56 transitions. [2018-01-24 11:46:36,125 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 56 transitions. Word has length 15 [2018-01-24 11:46:36,125 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 11:46:36,126 INFO L432 AbstractCegarLoop]: Abstraction has 51 states and 56 transitions. [2018-01-24 11:46:36,126 INFO L433 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-01-24 11:46:36,126 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 56 transitions. [2018-01-24 11:46:36,126 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2018-01-24 11:46:36,127 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 11:46:36,127 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-24 11:46:36,127 INFO L371 AbstractCegarLoop]: === Iteration 3 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 11:46:36,127 INFO L82 PathProgramCache]: Analyzing trace with hash -1192074960, now seen corresponding path program 1 times [2018-01-24 11:46:36,127 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-24 11:46:36,127 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-24 11:46:36,128 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 11:46:36,129 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 11:46:36,129 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 11:46:36,148 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 11:46:36,149 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 11:46:36,211 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 11:46:36,212 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 11:46:36,212 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-01-24 11:46:36,212 INFO L409 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-01-24 11:46:36,212 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-01-24 11:46:36,212 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-01-24 11:46:36,213 INFO L87 Difference]: Start difference. First operand 51 states and 56 transitions. Second operand 4 states. [2018-01-24 11:46:36,284 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 11:46:36,284 INFO L93 Difference]: Finished difference Result 51 states and 56 transitions. [2018-01-24 11:46:36,285 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-01-24 11:46:36,285 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 15 [2018-01-24 11:46:36,285 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 11:46:36,286 INFO L225 Difference]: With dead ends: 51 [2018-01-24 11:46:36,286 INFO L226 Difference]: Without dead ends: 50 [2018-01-24 11:46:36,287 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 1 SyntacticMatches, 1 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 11:46:36,287 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 50 states. [2018-01-24 11:46:36,292 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 50 to 50. [2018-01-24 11:46:36,292 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 50 states. [2018-01-24 11:46:36,294 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 50 states to 50 states and 55 transitions. [2018-01-24 11:46:36,294 INFO L78 Accepts]: Start accepts. Automaton has 50 states and 55 transitions. Word has length 15 [2018-01-24 11:46:36,294 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 11:46:36,294 INFO L432 AbstractCegarLoop]: Abstraction has 50 states and 55 transitions. [2018-01-24 11:46:36,294 INFO L433 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-01-24 11:46:36,294 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 55 transitions. [2018-01-24 11:46:36,295 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2018-01-24 11:46:36,295 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 11:46:36,295 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-24 11:46:36,295 INFO L371 AbstractCegarLoop]: === Iteration 4 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 11:46:36,296 INFO L82 PathProgramCache]: Analyzing trace with hash -1192074959, now seen corresponding path program 1 times [2018-01-24 11:46:36,296 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-24 11:46:36,296 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-24 11:46:36,297 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 11:46:36,297 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 11:46:36,297 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 11:46:36,312 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 11:46:36,313 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 11:46:36,476 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 11:46:36,476 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 11:46:36,476 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2018-01-24 11:46:36,476 INFO L409 AbstractCegarLoop]: Interpolant automaton has 8 states [2018-01-24 11:46:36,476 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2018-01-24 11:46:36,477 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=38, Unknown=0, NotChecked=0, Total=56 [2018-01-24 11:46:36,477 INFO L87 Difference]: Start difference. First operand 50 states and 55 transitions. Second operand 8 states. [2018-01-24 11:46:36,593 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 11:46:36,593 INFO L93 Difference]: Finished difference Result 50 states and 55 transitions. [2018-01-24 11:46:36,593 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-01-24 11:46:36,593 INFO L78 Accepts]: Start accepts. Automaton has 8 states. Word has length 15 [2018-01-24 11:46:36,594 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 11:46:36,594 INFO L225 Difference]: With dead ends: 50 [2018-01-24 11:46:36,594 INFO L226 Difference]: Without dead ends: 49 [2018-01-24 11:46:36,595 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=48, Invalid=84, Unknown=0, NotChecked=0, Total=132 [2018-01-24 11:46:36,595 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 49 states. [2018-01-24 11:46:36,598 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 49 to 49. [2018-01-24 11:46:36,599 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 49 states. [2018-01-24 11:46:36,599 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 49 states to 49 states and 54 transitions. [2018-01-24 11:46:36,599 INFO L78 Accepts]: Start accepts. Automaton has 49 states and 54 transitions. Word has length 15 [2018-01-24 11:46:36,600 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 11:46:36,600 INFO L432 AbstractCegarLoop]: Abstraction has 49 states and 54 transitions. [2018-01-24 11:46:36,600 INFO L433 AbstractCegarLoop]: Interpolant automaton has 8 states. [2018-01-24 11:46:36,600 INFO L276 IsEmpty]: Start isEmpty. Operand 49 states and 54 transitions. [2018-01-24 11:46:36,600 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2018-01-24 11:46:36,600 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 11:46:36,600 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-24 11:46:36,601 INFO L371 AbstractCegarLoop]: === Iteration 5 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 11:46:36,601 INFO L82 PathProgramCache]: Analyzing trace with hash 1700381909, now seen corresponding path program 1 times [2018-01-24 11:46:36,601 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-24 11:46:36,601 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-24 11:46:36,602 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 11:46:36,602 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 11:46:36,602 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 11:46:36,614 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 11:46:36,615 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 11:46:36,642 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 11:46:36,642 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 11:46:36,642 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-01-24 11:46:36,643 INFO L409 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-01-24 11:46:36,643 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-01-24 11:46:36,643 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-01-24 11:46:36,644 INFO L87 Difference]: Start difference. First operand 49 states and 54 transitions. Second operand 4 states. [2018-01-24 11:46:36,703 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 11:46:36,703 INFO L93 Difference]: Finished difference Result 49 states and 54 transitions. [2018-01-24 11:46:36,703 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-01-24 11:46:36,704 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 16 [2018-01-24 11:46:36,704 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 11:46:36,705 INFO L225 Difference]: With dead ends: 49 [2018-01-24 11:46:36,705 INFO L226 Difference]: Without dead ends: 48 [2018-01-24 11:46:36,705 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 11:46:36,705 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states. [2018-01-24 11:46:36,710 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 48. [2018-01-24 11:46:36,711 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 48 states. [2018-01-24 11:46:36,712 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 53 transitions. [2018-01-24 11:46:36,712 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 53 transitions. Word has length 16 [2018-01-24 11:46:36,712 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 11:46:36,712 INFO L432 AbstractCegarLoop]: Abstraction has 48 states and 53 transitions. [2018-01-24 11:46:36,712 INFO L433 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-01-24 11:46:36,713 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 53 transitions. [2018-01-24 11:46:36,713 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2018-01-24 11:46:36,713 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 11:46:36,713 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-24 11:46:36,714 INFO L371 AbstractCegarLoop]: === Iteration 6 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 11:46:36,714 INFO L82 PathProgramCache]: Analyzing trace with hash 1700381910, now seen corresponding path program 1 times [2018-01-24 11:46:36,714 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-24 11:46:36,714 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-24 11:46:36,715 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 11:46:36,715 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 11:46:36,716 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 11:46:36,728 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 11:46:36,729 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 11:46:36,802 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 11:46:36,802 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 11:46:36,802 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-01-24 11:46:36,802 INFO L409 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-01-24 11:46:36,803 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-01-24 11:46:36,803 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-01-24 11:46:36,803 INFO L87 Difference]: Start difference. First operand 48 states and 53 transitions. Second operand 5 states. [2018-01-24 11:46:36,830 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 11:46:36,830 INFO L93 Difference]: Finished difference Result 48 states and 53 transitions. [2018-01-24 11:46:36,831 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-01-24 11:46:36,831 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 16 [2018-01-24 11:46:36,831 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 11:46:36,831 INFO L225 Difference]: With dead ends: 48 [2018-01-24 11:46:36,832 INFO L226 Difference]: Without dead ends: 47 [2018-01-24 11:46:36,832 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 11:46:36,832 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2018-01-24 11:46:36,837 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 47. [2018-01-24 11:46:36,837 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 47 states. [2018-01-24 11:46:36,838 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 47 states to 47 states and 52 transitions. [2018-01-24 11:46:36,838 INFO L78 Accepts]: Start accepts. Automaton has 47 states and 52 transitions. Word has length 16 [2018-01-24 11:46:36,838 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 11:46:36,838 INFO L432 AbstractCegarLoop]: Abstraction has 47 states and 52 transitions. [2018-01-24 11:46:36,838 INFO L433 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-01-24 11:46:36,839 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 52 transitions. [2018-01-24 11:46:36,839 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2018-01-24 11:46:36,839 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 11:46:36,840 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-24 11:46:36,840 INFO L371 AbstractCegarLoop]: === Iteration 7 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 11:46:36,840 INFO L82 PathProgramCache]: Analyzing trace with hash -275307336, now seen corresponding path program 1 times [2018-01-24 11:46:36,840 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-24 11:46:36,840 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-24 11:46:36,841 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 11:46:36,841 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 11:46:36,841 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 11:46:36,854 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 11:46:36,855 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 11:46:36,899 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 11:46:36,899 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 11:46:36,899 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-01-24 11:46:36,899 INFO L409 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-01-24 11:46:36,900 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-01-24 11:46:36,900 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2018-01-24 11:46:36,900 INFO L87 Difference]: Start difference. First operand 47 states and 52 transitions. Second operand 6 states. [2018-01-24 11:46:36,969 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 11:46:36,969 INFO L93 Difference]: Finished difference Result 50 states and 55 transitions. [2018-01-24 11:46:36,969 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-01-24 11:46:36,969 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 21 [2018-01-24 11:46:36,970 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 11:46:36,973 INFO L225 Difference]: With dead ends: 50 [2018-01-24 11:46:36,973 INFO L226 Difference]: Without dead ends: 47 [2018-01-24 11:46:36,973 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 11:46:36,974 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2018-01-24 11:46:36,978 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 44. [2018-01-24 11:46:36,979 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 44 states. [2018-01-24 11:46:36,979 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 44 states to 44 states and 49 transitions. [2018-01-24 11:46:36,980 INFO L78 Accepts]: Start accepts. Automaton has 44 states and 49 transitions. Word has length 21 [2018-01-24 11:46:36,980 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 11:46:36,980 INFO L432 AbstractCegarLoop]: Abstraction has 44 states and 49 transitions. [2018-01-24 11:46:36,980 INFO L433 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-01-24 11:46:36,980 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 49 transitions. [2018-01-24 11:46:36,981 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2018-01-24 11:46:36,981 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 11:46:36,981 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-24 11:46:36,982 INFO L371 AbstractCegarLoop]: === Iteration 8 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 11:46:36,982 INFO L82 PathProgramCache]: Analyzing trace with hash -275307335, now seen corresponding path program 1 times [2018-01-24 11:46:36,982 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-24 11:46:36,982 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-24 11:46:36,983 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 11:46:36,983 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 11:46:36,983 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 11:46:36,997 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 11:46:36,998 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 11:46:37,109 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 11:46:37,110 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 11:46:37,110 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2018-01-24 11:46:37,110 INFO L409 AbstractCegarLoop]: Interpolant automaton has 10 states [2018-01-24 11:46:37,111 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2018-01-24 11:46:37,111 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=71, Unknown=0, NotChecked=0, Total=90 [2018-01-24 11:46:37,111 INFO L87 Difference]: Start difference. First operand 44 states and 49 transitions. Second operand 10 states. [2018-01-24 11:46:37,278 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 11:46:37,278 INFO L93 Difference]: Finished difference Result 60 states and 67 transitions. [2018-01-24 11:46:37,278 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-01-24 11:46:37,278 INFO L78 Accepts]: Start accepts. Automaton has 10 states. Word has length 21 [2018-01-24 11:46:37,278 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 11:46:37,279 INFO L225 Difference]: With dead ends: 60 [2018-01-24 11:46:37,279 INFO L226 Difference]: Without dead ends: 57 [2018-01-24 11:46:37,279 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 16 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 25 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=65, Invalid=207, Unknown=0, NotChecked=0, Total=272 [2018-01-24 11:46:37,280 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 57 states. [2018-01-24 11:46:37,283 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 57 to 52. [2018-01-24 11:46:37,283 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 52 states. [2018-01-24 11:46:37,284 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 52 states to 52 states and 61 transitions. [2018-01-24 11:46:37,284 INFO L78 Accepts]: Start accepts. Automaton has 52 states and 61 transitions. Word has length 21 [2018-01-24 11:46:37,284 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 11:46:37,284 INFO L432 AbstractCegarLoop]: Abstraction has 52 states and 61 transitions. [2018-01-24 11:46:37,284 INFO L433 AbstractCegarLoop]: Interpolant automaton has 10 states. [2018-01-24 11:46:37,284 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 61 transitions. [2018-01-24 11:46:37,285 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2018-01-24 11:46:37,285 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 11:46:37,285 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] [2018-01-24 11:46:37,285 INFO L371 AbstractCegarLoop]: === Iteration 9 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 11:46:37,285 INFO L82 PathProgramCache]: Analyzing trace with hash 1706718631, now seen corresponding path program 1 times [2018-01-24 11:46:37,285 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-24 11:46:37,286 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-24 11:46:37,286 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 11:46:37,286 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 11:46:37,286 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 11:46:37,298 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 11:46:37,299 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 11:46:37,364 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 11:46:37,364 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 11:46:37,364 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2018-01-24 11:46:37,364 INFO L409 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-01-24 11:46:37,365 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-01-24 11:46:37,365 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2018-01-24 11:46:37,365 INFO L87 Difference]: Start difference. First operand 52 states and 61 transitions. Second operand 7 states. [2018-01-24 11:46:37,459 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 11:46:37,460 INFO L93 Difference]: Finished difference Result 55 states and 64 transitions. [2018-01-24 11:46:37,460 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-01-24 11:46:37,460 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 24 [2018-01-24 11:46:37,461 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 11:46:37,461 INFO L225 Difference]: With dead ends: 55 [2018-01-24 11:46:37,461 INFO L226 Difference]: Without dead ends: 54 [2018-01-24 11:46:37,461 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 9 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=29, Invalid=61, Unknown=0, NotChecked=0, Total=90 [2018-01-24 11:46:37,462 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2018-01-24 11:46:37,466 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 51. [2018-01-24 11:46:37,467 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 51 states. [2018-01-24 11:46:37,467 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 59 transitions. [2018-01-24 11:46:37,468 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 59 transitions. Word has length 24 [2018-01-24 11:46:37,468 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 11:46:37,468 INFO L432 AbstractCegarLoop]: Abstraction has 51 states and 59 transitions. [2018-01-24 11:46:37,468 INFO L433 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-01-24 11:46:37,468 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 59 transitions. [2018-01-24 11:46:37,469 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2018-01-24 11:46:37,469 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 11:46:37,469 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] [2018-01-24 11:46:37,469 INFO L371 AbstractCegarLoop]: === Iteration 10 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 11:46:37,470 INFO L82 PathProgramCache]: Analyzing trace with hash 1706718632, now seen corresponding path program 1 times [2018-01-24 11:46:37,470 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-24 11:46:37,470 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-24 11:46:37,471 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 11:46:37,471 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 11:46:37,471 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 11:46:37,482 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 11:46:37,483 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 11:46:37,601 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 11:46:37,602 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 11:46:37,602 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2018-01-24 11:46:37,602 INFO L409 AbstractCegarLoop]: Interpolant automaton has 10 states [2018-01-24 11:46:37,602 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2018-01-24 11:46:37,602 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=70, Unknown=0, NotChecked=0, Total=90 [2018-01-24 11:46:37,603 INFO L87 Difference]: Start difference. First operand 51 states and 59 transitions. Second operand 10 states. [2018-01-24 11:46:37,748 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 11:46:37,748 INFO L93 Difference]: Finished difference Result 57 states and 66 transitions. [2018-01-24 11:46:37,748 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-01-24 11:46:37,748 INFO L78 Accepts]: Start accepts. Automaton has 10 states. Word has length 24 [2018-01-24 11:46:37,748 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 11:46:37,749 INFO L225 Difference]: With dead ends: 57 [2018-01-24 11:46:37,749 INFO L226 Difference]: Without dead ends: 56 [2018-01-24 11:46:37,750 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 24 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=42, Invalid=140, Unknown=0, NotChecked=0, Total=182 [2018-01-24 11:46:37,750 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 56 states. [2018-01-24 11:46:37,755 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 56 to 53. [2018-01-24 11:46:37,755 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 53 states. [2018-01-24 11:46:37,756 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 53 states to 53 states and 60 transitions. [2018-01-24 11:46:37,756 INFO L78 Accepts]: Start accepts. Automaton has 53 states and 60 transitions. Word has length 24 [2018-01-24 11:46:37,757 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 11:46:37,757 INFO L432 AbstractCegarLoop]: Abstraction has 53 states and 60 transitions. [2018-01-24 11:46:37,757 INFO L433 AbstractCegarLoop]: Interpolant automaton has 10 states. [2018-01-24 11:46:37,757 INFO L276 IsEmpty]: Start isEmpty. Operand 53 states and 60 transitions. [2018-01-24 11:46:37,758 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2018-01-24 11:46:37,758 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 11:46:37,758 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, 1] [2018-01-24 11:46:37,758 INFO L371 AbstractCegarLoop]: === Iteration 11 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 11:46:37,758 INFO L82 PathProgramCache]: Analyzing trace with hash 1706720075, now seen corresponding path program 1 times [2018-01-24 11:46:37,758 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-24 11:46:37,759 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-24 11:46:37,759 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 11:46:37,760 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 11:46:37,760 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 11:46:37,773 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 11:46:37,774 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 11:46:38,039 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 11:46:38,039 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-24 11:46:38,040 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 2 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-24 11:46:38,046 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 11:46:38,077 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 11:46:38,086 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-24 11:46:38,173 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 11:46:38,174 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 11:46:38,185 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 11:46:38,185 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 11:46:38,192 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 11:46:38,192 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:24, output treesize:19 [2018-01-24 11:46:38,251 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:46:38,252 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:46:38,255 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 11:46:38,255 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 11:46:38,265 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:46:38,265 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:46:38,266 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 11:46:38,266 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 11:46:38,272 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 11:46:38,273 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:30, output treesize:18 [2018-01-24 11:46:38,457 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 11:46:38,485 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-24 11:46:38,485 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 13] total 23 [2018-01-24 11:46:38,486 INFO L409 AbstractCegarLoop]: Interpolant automaton has 24 states [2018-01-24 11:46:38,486 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2018-01-24 11:46:38,486 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=61, Invalid=491, Unknown=0, NotChecked=0, Total=552 [2018-01-24 11:46:38,486 INFO L87 Difference]: Start difference. First operand 53 states and 60 transitions. Second operand 24 states. [2018-01-24 11:46:39,114 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 11:46:39,114 INFO L93 Difference]: Finished difference Result 75 states and 85 transitions. [2018-01-24 11:46:39,114 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-01-24 11:46:39,114 INFO L78 Accepts]: Start accepts. Automaton has 24 states. Word has length 24 [2018-01-24 11:46:39,115 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 11:46:39,115 INFO L225 Difference]: With dead ends: 75 [2018-01-24 11:46:39,115 INFO L226 Difference]: Without dead ends: 72 [2018-01-24 11:46:39,116 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 45 GetRequests, 13 SyntacticMatches, 0 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 192 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=169, Invalid=953, Unknown=0, NotChecked=0, Total=1122 [2018-01-24 11:46:39,116 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 72 states. [2018-01-24 11:46:39,122 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 72 to 64. [2018-01-24 11:46:39,122 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 64 states. [2018-01-24 11:46:39,123 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 64 states to 64 states and 75 transitions. [2018-01-24 11:46:39,123 INFO L78 Accepts]: Start accepts. Automaton has 64 states and 75 transitions. Word has length 24 [2018-01-24 11:46:39,123 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 11:46:39,124 INFO L432 AbstractCegarLoop]: Abstraction has 64 states and 75 transitions. [2018-01-24 11:46:39,124 INFO L433 AbstractCegarLoop]: Interpolant automaton has 24 states. [2018-01-24 11:46:39,124 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 75 transitions. [2018-01-24 11:46:39,125 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2018-01-24 11:46:39,125 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 11:46:39,125 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, 1] [2018-01-24 11:46:39,125 INFO L371 AbstractCegarLoop]: === Iteration 12 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 11:46:39,126 INFO L82 PathProgramCache]: Analyzing trace with hash 1074905977, now seen corresponding path program 2 times [2018-01-24 11:46:39,126 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-24 11:46:39,126 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-24 11:46:39,127 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 11:46:39,127 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 11:46:39,127 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 11:46:39,146 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 11:46:39,147 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 11:46:39,532 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 11:46:39,532 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-24 11:46:39,532 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-24 11:46:39,537 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-01-24 11:46:39,549 INFO L201 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-24 11:46:39,553 INFO L214 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-24 11:46:39,555 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-24 11:46:39,558 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-24 11:46:39,584 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 11:46:39,584 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 11:46:39,588 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 11:46:39,588 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:18, output treesize:17 [2018-01-24 11:46:39,626 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:46:39,627 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:46:39,646 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 11:46:39,647 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 11:46:39,652 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 11:46:39,652 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:22, output treesize:16 [2018-01-24 11:46:39,704 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 17 treesize of output 14 [2018-01-24 11:46:39,706 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 13 [2018-01-24 11:46:39,706 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 11:46:39,709 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 11:46:39,717 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 11:46:39,718 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:42, output treesize:38 [2018-01-24 11:46:39,762 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 28 treesize of output 29 [2018-01-24 11:46:39,765 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 11 treesize of output 10 [2018-01-24 11:46:39,765 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 11:46:39,769 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 11:46:39,778 INFO L267 ElimStorePlain]: Start of recursive call 1: 5 dim-0 vars, 1 dim-2 vars, End of recursive call: 5 dim-0 vars, and 1 xjuncts. [2018-01-24 11:46:39,779 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 6 variables, input treesize:52, output treesize:48 [2018-01-24 11:46:42,069 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 41 treesize of output 37 [2018-01-24 11:46:42,072 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2018-01-24 11:46:42,073 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 11:46:42,080 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:46:42,086 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 25 treesize of output 37 [2018-01-24 11:46:42,087 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 2 xjuncts. [2018-01-24 11:46:42,100 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-24 11:46:42,131 INFO L267 ElimStorePlain]: Start of recursive call 1: 5 dim-0 vars, 1 dim-2 vars, End of recursive call: and 2 xjuncts. [2018-01-24 11:46:42,131 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 6 variables, input treesize:66, output treesize:43 [2018-01-24 11:46:42,177 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 5 refuted. 2 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-24 11:46:42,197 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-24 11:46:42,197 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 16] total 27 [2018-01-24 11:46:42,197 INFO L409 AbstractCegarLoop]: Interpolant automaton has 28 states [2018-01-24 11:46:42,197 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2018-01-24 11:46:42,198 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=67, Invalid=688, Unknown=1, NotChecked=0, Total=756 [2018-01-24 11:46:42,198 INFO L87 Difference]: Start difference. First operand 64 states and 75 transitions. Second operand 28 states. [2018-01-24 11:46:46,124 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 11:46:46,125 INFO L93 Difference]: Finished difference Result 111 states and 126 transitions. [2018-01-24 11:46:46,125 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2018-01-24 11:46:46,125 INFO L78 Accepts]: Start accepts. Automaton has 28 states. Word has length 27 [2018-01-24 11:46:46,126 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 11:46:46,127 INFO L225 Difference]: With dead ends: 111 [2018-01-24 11:46:46,127 INFO L226 Difference]: Without dead ends: 108 [2018-01-24 11:46:46,128 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 62 GetRequests, 13 SyntacticMatches, 1 SemanticMatches, 48 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 387 ImplicationChecksByTransitivity, 5.8s TimeCoverageRelationStatistics Valid=328, Invalid=2120, Unknown=2, NotChecked=0, Total=2450 [2018-01-24 11:46:46,128 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 108 states. [2018-01-24 11:46:46,142 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 108 to 67. [2018-01-24 11:46:46,143 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 67 states. [2018-01-24 11:46:46,143 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 67 states to 67 states and 79 transitions. [2018-01-24 11:46:46,143 INFO L78 Accepts]: Start accepts. Automaton has 67 states and 79 transitions. Word has length 27 [2018-01-24 11:46:46,144 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 11:46:46,144 INFO L432 AbstractCegarLoop]: Abstraction has 67 states and 79 transitions. [2018-01-24 11:46:46,144 INFO L433 AbstractCegarLoop]: Interpolant automaton has 28 states. [2018-01-24 11:46:46,144 INFO L276 IsEmpty]: Start isEmpty. Operand 67 states and 79 transitions. [2018-01-24 11:46:46,145 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2018-01-24 11:46:46,145 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 11:46:46,145 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-24 11:46:46,145 INFO L371 AbstractCegarLoop]: === Iteration 13 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 11:46:46,145 INFO L82 PathProgramCache]: Analyzing trace with hash 94248296, now seen corresponding path program 1 times [2018-01-24 11:46:46,146 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-24 11:46:46,146 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-24 11:46:46,147 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 11:46:46,147 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-01-24 11:46:46,147 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 11:46:46,158 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 11:46:46,158 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 11:46:46,229 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 11:46:46,229 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 11:46:46,230 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-01-24 11:46:46,230 INFO L409 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-01-24 11:46:46,230 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-01-24 11:46:46,230 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-01-24 11:46:46,231 INFO L87 Difference]: Start difference. First operand 67 states and 79 transitions. Second operand 5 states. [2018-01-24 11:46:46,298 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 11:46:46,298 INFO L93 Difference]: Finished difference Result 104 states and 119 transitions. [2018-01-24 11:46:46,299 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-01-24 11:46:46,299 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 28 [2018-01-24 11:46:46,299 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 11:46:46,301 INFO L225 Difference]: With dead ends: 104 [2018-01-24 11:46:46,301 INFO L226 Difference]: Without dead ends: 97 [2018-01-24 11:46:46,302 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 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 11:46:46,302 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 97 states. [2018-01-24 11:46:46,318 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 97 to 78. [2018-01-24 11:46:46,318 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 78 states. [2018-01-24 11:46:46,319 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 78 states to 78 states and 91 transitions. [2018-01-24 11:46:46,319 INFO L78 Accepts]: Start accepts. Automaton has 78 states and 91 transitions. Word has length 28 [2018-01-24 11:46:46,320 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 11:46:46,320 INFO L432 AbstractCegarLoop]: Abstraction has 78 states and 91 transitions. [2018-01-24 11:46:46,320 INFO L433 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-01-24 11:46:46,320 INFO L276 IsEmpty]: Start isEmpty. Operand 78 states and 91 transitions. [2018-01-24 11:46:46,321 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2018-01-24 11:46:46,321 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 11:46:46,321 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-24 11:46:46,322 INFO L371 AbstractCegarLoop]: === Iteration 14 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 11:46:46,322 INFO L82 PathProgramCache]: Analyzing trace with hash -723400154, now seen corresponding path program 1 times [2018-01-24 11:46:46,322 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-24 11:46:46,322 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-24 11:46:46,323 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 11:46:46,323 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 11:46:46,323 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 11:46:46,336 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 11:46:46,337 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 11:46:46,487 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 11:46:46,487 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 11:46:46,488 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-01-24 11:46:46,488 INFO L409 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-01-24 11:46:46,488 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-01-24 11:46:46,488 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2018-01-24 11:46:46,488 INFO L87 Difference]: Start difference. First operand 78 states and 91 transitions. Second operand 6 states. [2018-01-24 11:46:46,632 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 11:46:46,632 INFO L93 Difference]: Finished difference Result 78 states and 91 transitions. [2018-01-24 11:46:46,632 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-01-24 11:46:46,632 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 28 [2018-01-24 11:46:46,633 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 11:46:46,633 INFO L225 Difference]: With dead ends: 78 [2018-01-24 11:46:46,633 INFO L226 Difference]: Without dead ends: 64 [2018-01-24 11:46:46,633 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2018-01-24 11:46:46,633 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 64 states. [2018-01-24 11:46:46,641 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 64 to 56. [2018-01-24 11:46:46,641 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 56 states. [2018-01-24 11:46:46,642 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 56 states to 56 states and 64 transitions. [2018-01-24 11:46:46,642 INFO L78 Accepts]: Start accepts. Automaton has 56 states and 64 transitions. Word has length 28 [2018-01-24 11:46:46,642 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 11:46:46,642 INFO L432 AbstractCegarLoop]: Abstraction has 56 states and 64 transitions. [2018-01-24 11:46:46,643 INFO L433 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-01-24 11:46:46,643 INFO L276 IsEmpty]: Start isEmpty. Operand 56 states and 64 transitions. [2018-01-24 11:46:46,644 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2018-01-24 11:46:46,644 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 11:46:46,644 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, 1, 1, 1, 1, 1, 1, 1] [2018-01-24 11:46:46,644 INFO L371 AbstractCegarLoop]: === Iteration 15 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 11:46:46,644 INFO L82 PathProgramCache]: Analyzing trace with hash -1208652779, now seen corresponding path program 1 times [2018-01-24 11:46:46,644 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-24 11:46:46,644 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-24 11:46:46,645 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 11:46:46,645 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 11:46:46,645 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 11:46:46,662 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 11:46:46,662 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 11:46:46,799 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-24 11:46:46,799 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-24 11:46:46,799 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2018-01-24 11:46:46,799 INFO L409 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-01-24 11:46:46,799 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-01-24 11:46:46,799 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2018-01-24 11:46:46,800 INFO L87 Difference]: Start difference. First operand 56 states and 64 transitions. Second operand 7 states. [2018-01-24 11:46:46,974 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 11:46:46,975 INFO L93 Difference]: Finished difference Result 114 states and 128 transitions. [2018-01-24 11:46:46,975 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-01-24 11:46:46,975 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 30 [2018-01-24 11:46:46,975 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 11:46:46,976 INFO L225 Difference]: With dead ends: 114 [2018-01-24 11:46:46,976 INFO L226 Difference]: Without dead ends: 94 [2018-01-24 11:46:46,976 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2018-01-24 11:46:46,976 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 94 states. [2018-01-24 11:46:46,990 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 94 to 88. [2018-01-24 11:46:46,990 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 88 states. [2018-01-24 11:46:46,991 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 88 states to 88 states and 101 transitions. [2018-01-24 11:46:46,991 INFO L78 Accepts]: Start accepts. Automaton has 88 states and 101 transitions. Word has length 30 [2018-01-24 11:46:46,991 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 11:46:46,992 INFO L432 AbstractCegarLoop]: Abstraction has 88 states and 101 transitions. [2018-01-24 11:46:46,992 INFO L433 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-01-24 11:46:46,992 INFO L276 IsEmpty]: Start isEmpty. Operand 88 states and 101 transitions. [2018-01-24 11:46:46,992 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2018-01-24 11:46:46,993 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 11:46:46,993 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, 1] [2018-01-24 11:46:46,993 INFO L371 AbstractCegarLoop]: === Iteration 16 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 11:46:46,993 INFO L82 PathProgramCache]: Analyzing trace with hash -752196469, now seen corresponding path program 3 times [2018-01-24 11:46:46,993 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-24 11:46:46,993 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-24 11:46:46,994 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 11:46:46,994 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 11:46:46,994 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 11:46:47,008 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 11:46:47,009 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 11:46:47,475 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 11:46:47,475 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-24 11:46:47,475 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-24 11:46:47,483 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-01-24 11:46:47,496 INFO L254 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued a check-sat command [2018-01-24 11:46:47,499 INFO L254 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued a check-sat command [2018-01-24 11:46:47,502 INFO L254 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued a check-sat command [2018-01-24 11:46:47,504 INFO L254 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued a check-sat command [2018-01-24 11:46:47,506 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-24 11:46:47,509 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-24 11:46:47,514 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 11:46:47,514 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 11:46:47,520 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 11:46:47,520 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 11:46:47,525 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 11:46:47,526 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:22, output treesize:20 [2018-01-24 11:46:47,551 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:46:47,552 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 11:46:47,552 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 11:46:47,562 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:46:47,563 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:46:47,563 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 11:46:47,564 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 11:46:47,569 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 11:46:47,570 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:31, output treesize:24 [2018-01-24 11:46:47,619 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 11:46:47,620 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 11:46:47,621 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 11:46:47,622 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 11:46:47,627 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 11:46:47,627 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:34, output treesize:30 [2018-01-24 11:46:47,654 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 11:46:47,656 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 11:46:47,656 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 11:46:47,661 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 11:46:47,667 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 11:46:47,667 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:41, output treesize:37 [2018-01-24 11:46:47,813 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 11:46:47,815 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 11:46:47,815 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 11:46:47,823 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 11:46:47,823 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 2 xjuncts. [2018-01-24 11:46:47,826 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-24 11:46:47,833 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 11:46:47,833 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 4 variables, input treesize:44, output treesize:18 [2018-01-24 11:46:47,874 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 11:46:47,895 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-24 11:46:47,895 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 15] total 24 [2018-01-24 11:46:47,895 INFO L409 AbstractCegarLoop]: Interpolant automaton has 25 states [2018-01-24 11:46:47,895 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2018-01-24 11:46:47,896 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=57, Invalid=543, Unknown=0, NotChecked=0, Total=600 [2018-01-24 11:46:47,896 INFO L87 Difference]: Start difference. First operand 88 states and 101 transitions. Second operand 25 states. [2018-01-24 11:46:49,007 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 11:46:49,007 INFO L93 Difference]: Finished difference Result 93 states and 103 transitions. [2018-01-24 11:46:49,007 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2018-01-24 11:46:49,007 INFO L78 Accepts]: Start accepts. Automaton has 25 states. Word has length 30 [2018-01-24 11:46:49,008 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 11:46:49,008 INFO L225 Difference]: With dead ends: 93 [2018-01-24 11:46:49,008 INFO L226 Difference]: Without dead ends: 56 [2018-01-24 11:46:49,009 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 60 GetRequests, 18 SyntacticMatches, 4 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 215 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=219, Invalid=1341, Unknown=0, NotChecked=0, Total=1560 [2018-01-24 11:46:49,009 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 56 states. [2018-01-24 11:46:49,015 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 56 to 56. [2018-01-24 11:46:49,015 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 56 states. [2018-01-24 11:46:49,015 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 56 states to 56 states and 63 transitions. [2018-01-24 11:46:49,016 INFO L78 Accepts]: Start accepts. Automaton has 56 states and 63 transitions. Word has length 30 [2018-01-24 11:46:49,016 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 11:46:49,016 INFO L432 AbstractCegarLoop]: Abstraction has 56 states and 63 transitions. [2018-01-24 11:46:49,016 INFO L433 AbstractCegarLoop]: Interpolant automaton has 25 states. [2018-01-24 11:46:49,016 INFO L276 IsEmpty]: Start isEmpty. Operand 56 states and 63 transitions. [2018-01-24 11:46:49,017 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2018-01-24 11:46:49,017 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 11:46:49,017 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, 1, 1, 1, 1, 1, 1, 1] [2018-01-24 11:46:49,017 INFO L371 AbstractCegarLoop]: === Iteration 17 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 11:46:49,017 INFO L82 PathProgramCache]: Analyzing trace with hash -989798061, now seen corresponding path program 1 times [2018-01-24 11:46:49,017 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-24 11:46:49,018 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-24 11:46:49,018 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 11:46:49,018 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-01-24 11:46:49,019 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 11:46:49,034 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 11:46:49,035 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 11:46:49,228 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 11:46:49,229 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-24 11:46:49,229 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-24 11:46:49,236 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 11:46:49,255 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 11:46:49,258 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-24 11:46:49,271 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 14 treesize of output 11 [2018-01-24 11:46:49,273 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 11 treesize of output 10 [2018-01-24 11:46:49,273 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 11:46:49,275 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 11:46:49,279 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 11:46:49,280 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:25, output treesize:21 [2018-01-24 11:46:49,407 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 20 treesize of output 16 [2018-01-24 11:46:49,412 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 16 treesize of output 13 [2018-01-24 11:46:49,412 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-24 11:46:49,415 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-24 11:46:49,423 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 11:46:49,424 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:38, output treesize:29 [2018-01-24 11:46:49,460 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 11:46:49,480 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-24 11:46:49,480 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 10] total 18 [2018-01-24 11:46:49,480 INFO L409 AbstractCegarLoop]: Interpolant automaton has 19 states [2018-01-24 11:46:49,481 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2018-01-24 11:46:49,481 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=40, Invalid=302, Unknown=0, NotChecked=0, Total=342 [2018-01-24 11:46:49,481 INFO L87 Difference]: Start difference. First operand 56 states and 63 transitions. Second operand 19 states. [2018-01-24 11:46:49,925 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 11:46:49,925 INFO L93 Difference]: Finished difference Result 71 states and 80 transitions. [2018-01-24 11:46:49,925 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-01-24 11:46:49,925 INFO L78 Accepts]: Start accepts. Automaton has 19 states. Word has length 30 [2018-01-24 11:46:49,925 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 11:46:49,926 INFO L225 Difference]: With dead ends: 71 [2018-01-24 11:46:49,927 INFO L226 Difference]: Without dead ends: 70 [2018-01-24 11:46:49,927 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 49 GetRequests, 24 SyntacticMatches, 0 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 77 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=103, Invalid=599, Unknown=0, NotChecked=0, Total=702 [2018-01-24 11:46:49,927 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 70 states. [2018-01-24 11:46:49,934 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 70 to 64. [2018-01-24 11:46:49,934 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 64 states. [2018-01-24 11:46:49,934 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 64 states to 64 states and 73 transitions. [2018-01-24 11:46:49,935 INFO L78 Accepts]: Start accepts. Automaton has 64 states and 73 transitions. Word has length 30 [2018-01-24 11:46:49,935 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 11:46:49,935 INFO L432 AbstractCegarLoop]: Abstraction has 64 states and 73 transitions. [2018-01-24 11:46:49,935 INFO L433 AbstractCegarLoop]: Interpolant automaton has 19 states. [2018-01-24 11:46:49,935 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 73 transitions. [2018-01-24 11:46:49,936 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2018-01-24 11:46:49,936 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 11:46:49,936 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, 1] [2018-01-24 11:46:49,936 INFO L371 AbstractCegarLoop]: === Iteration 18 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 11:46:49,936 INFO L82 PathProgramCache]: Analyzing trace with hash -533341751, now seen corresponding path program 1 times [2018-01-24 11:46:49,936 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-24 11:46:49,936 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-24 11:46:49,937 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 11:46:49,937 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 11:46:49,937 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 11:46:49,952 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 11:46:49,953 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 11:46:50,218 WARN L146 SmtUtils]: Spent 141ms on a formula simplification. DAG size of input: 30 DAG size of output 24 [2018-01-24 11:46:50,510 WARN L146 SmtUtils]: Spent 150ms on a formula simplification. DAG size of input: 30 DAG size of output 24 [2018-01-24 11:46:50,811 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 11:46:50,811 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-24 11:46:50,811 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-24 11:46:50,819 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 11:46:50,844 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 11:46:50,847 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-24 11:46:50,915 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 11:46:50,916 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 11:46:50,923 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 11:46:50,923 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 11:46:50,933 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 11:46:50,933 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:27, output treesize:25 [2018-01-24 11:46:50,986 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:46:50,986 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:46:50,987 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 11:46:50,987 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 11:46:50,996 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:46:50,996 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 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 11:46:50,997 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 11:46:51,004 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 11:46:51,004 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:36, output treesize:25 [2018-01-24 11:46:51,059 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 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 11:46:51,061 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 15 [2018-01-24 11:46:51,061 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 11:46:51,063 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 11:46:51,071 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 11:46:51,071 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:41, output treesize:37 [2018-01-24 11:46:51,105 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:46:51,108 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 11:46:51,110 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 11:46:51,110 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 11:46:51,114 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 11:46:51,122 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 11:46:51,122 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:52, output treesize:48 [2018-01-24 11:46:51,421 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:46:51,422 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 11:46:51,461 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:46:51,467 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 11:46:51,468 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-24 11:46:51,486 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 11:46:51,486 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-24 11:46:51,495 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-24 11:46:51,514 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 11:46:51,515 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 5 variables, input treesize:73, output treesize:122 [2018-01-24 11:46:51,701 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 11:46:51,721 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-24 11:46:51,722 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 18] total 33 [2018-01-24 11:46:51,722 INFO L409 AbstractCegarLoop]: Interpolant automaton has 34 states [2018-01-24 11:46:51,722 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 34 interpolants. [2018-01-24 11:46:51,723 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=108, Invalid=1014, Unknown=0, NotChecked=0, Total=1122 [2018-01-24 11:46:51,723 INFO L87 Difference]: Start difference. First operand 64 states and 73 transitions. Second operand 34 states. [2018-01-24 11:46:53,409 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 11:46:53,409 INFO L93 Difference]: Finished difference Result 100 states and 113 transitions. [2018-01-24 11:46:53,410 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2018-01-24 11:46:53,410 INFO L78 Accepts]: Start accepts. Automaton has 34 states. Word has length 30 [2018-01-24 11:46:53,410 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 11:46:53,410 INFO L225 Difference]: With dead ends: 100 [2018-01-24 11:46:53,411 INFO L226 Difference]: Without dead ends: 95 [2018-01-24 11:46:53,411 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 65 GetRequests, 13 SyntacticMatches, 1 SemanticMatches, 51 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 543 ImplicationChecksByTransitivity, 2.5s TimeCoverageRelationStatistics Valid=320, Invalid=2436, Unknown=0, NotChecked=0, Total=2756 [2018-01-24 11:46:53,411 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 95 states. [2018-01-24 11:46:53,419 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 95 to 67. [2018-01-24 11:46:53,420 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 67 states. [2018-01-24 11:46:53,420 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 67 states to 67 states and 77 transitions. [2018-01-24 11:46:53,420 INFO L78 Accepts]: Start accepts. Automaton has 67 states and 77 transitions. Word has length 30 [2018-01-24 11:46:53,421 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 11:46:53,421 INFO L432 AbstractCegarLoop]: Abstraction has 67 states and 77 transitions. [2018-01-24 11:46:53,421 INFO L433 AbstractCegarLoop]: Interpolant automaton has 34 states. [2018-01-24 11:46:53,421 INFO L276 IsEmpty]: Start isEmpty. Operand 67 states and 77 transitions. [2018-01-24 11:46:53,421 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2018-01-24 11:46:53,422 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 11:46:53,422 INFO L322 BasicCegarLoop]: trace histogram [5, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-24 11:46:53,422 INFO L371 AbstractCegarLoop]: === Iteration 19 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 11:46:53,422 INFO L82 PathProgramCache]: Analyzing trace with hash -1700074437, now seen corresponding path program 2 times [2018-01-24 11:46:53,422 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-24 11:46:53,422 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-24 11:46:53,423 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 11:46:53,423 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 11:46:53,423 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 11:46:53,442 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 11:46:53,442 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 11:46:53,974 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-24 11:46:53,975 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-24 11:46:53,975 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-24 11:46:53,980 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-01-24 11:46:53,989 INFO L201 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-24 11:46:53,995 INFO L214 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-24 11:46:53,997 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-24 11:46:54,000 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-24 11:46:54,068 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 11:46:54,068 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 11:46:54,076 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 11:46:54,076 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 11:46:54,082 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 11:46:54,082 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:27, output treesize:25 [2018-01-24 11:46:54,133 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:46:54,134 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:46:54,135 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 4 [2018-01-24 11:46:54,135 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 11:46:54,144 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:46:54,144 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 11:46:54,144 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 11:46:54,152 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 11:46:54,152 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:36, output treesize:25 [2018-01-24 11:46:54,206 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 11:46:54,208 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 11:46:54,208 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 11:46:54,209 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 11:46:54,216 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 11:46:54,216 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:41, output treesize:37 [2018-01-24 11:46:54,252 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:46:54,255 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 11:46:54,257 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 11:46:54,257 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 11:46:54,261 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 11:46:54,269 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 11:46:54,269 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:52, output treesize:48 [2018-01-24 11:46:54,599 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:46:54,601 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 50 treesize of output 44 [2018-01-24 11:46:54,602 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 11:46:54,603 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 11:46:54,611 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:46:54,611 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:46:54,618 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 4 select indices, 4 select index equivalence classes, 7 disjoint index pairs (out of 6 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 30 treesize of output 54 [2018-01-24 11:46:54,618 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 2 xjuncts. [2018-01-24 11:46:54,632 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-24 11:46:54,649 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-2 vars, End of recursive call: 6 dim-0 vars, and 2 xjuncts. [2018-01-24 11:46:54,649 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 4 variables, input treesize:70, output treesize:204 [2018-01-24 11:46:54,844 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-24 11:46:54,864 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-24 11:46:54,864 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 20] total 36 [2018-01-24 11:46:54,864 INFO L409 AbstractCegarLoop]: Interpolant automaton has 37 states [2018-01-24 11:46:54,865 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 37 interpolants. [2018-01-24 11:46:54,865 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=115, Invalid=1217, Unknown=0, NotChecked=0, Total=1332 [2018-01-24 11:46:54,865 INFO L87 Difference]: Start difference. First operand 67 states and 77 transitions. Second operand 37 states. [2018-01-24 11:46:56,420 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 11:46:56,420 INFO L93 Difference]: Finished difference Result 103 states and 118 transitions. [2018-01-24 11:46:56,420 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2018-01-24 11:46:56,420 INFO L78 Accepts]: Start accepts. Automaton has 37 states. Word has length 33 [2018-01-24 11:46:56,420 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 11:46:56,421 INFO L225 Difference]: With dead ends: 103 [2018-01-24 11:46:56,421 INFO L226 Difference]: Without dead ends: 99 [2018-01-24 11:46:56,422 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 68 GetRequests, 14 SyntacticMatches, 1 SemanticMatches, 53 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 645 ImplicationChecksByTransitivity, 1.8s TimeCoverageRelationStatistics Valid=306, Invalid=2664, Unknown=0, NotChecked=0, Total=2970 [2018-01-24 11:46:56,422 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 99 states. [2018-01-24 11:46:56,430 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 99 to 70. [2018-01-24 11:46:56,458 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 70 states. [2018-01-24 11:46:56,459 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 70 states to 70 states and 81 transitions. [2018-01-24 11:46:56,459 INFO L78 Accepts]: Start accepts. Automaton has 70 states and 81 transitions. Word has length 33 [2018-01-24 11:46:56,459 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 11:46:56,459 INFO L432 AbstractCegarLoop]: Abstraction has 70 states and 81 transitions. [2018-01-24 11:46:56,459 INFO L433 AbstractCegarLoop]: Interpolant automaton has 37 states. [2018-01-24 11:46:56,460 INFO L276 IsEmpty]: Start isEmpty. Operand 70 states and 81 transitions. [2018-01-24 11:46:56,460 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2018-01-24 11:46:56,460 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 11:46:56,460 INFO L322 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-24 11:46:56,460 INFO L371 AbstractCegarLoop]: === Iteration 20 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 11:46:56,461 INFO L82 PathProgramCache]: Analyzing trace with hash -608695935, now seen corresponding path program 1 times [2018-01-24 11:46:56,461 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-24 11:46:56,461 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-24 11:46:56,461 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 11:46:56,461 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-01-24 11:46:56,462 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 11:46:56,470 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 11:46:56,470 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 11:46:56,814 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-24 11:46:56,814 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-24 11:46:56,814 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-24 11:46:56,822 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 11:46:56,846 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 11:46:56,849 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-24 11:46:56,854 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 11:46:56,854 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 11:46:56,860 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 11:46:56,861 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 11:46:56,865 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 11:46:56,866 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:21, output treesize:16 [2018-01-24 11:46:56,906 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:46:56,907 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:46:56,908 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 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 11:46:56,908 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 11:46:56,918 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:46:56,919 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:46:56,919 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 11:46:56,919 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 11:46:56,926 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 11:46:56,926 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:27, output treesize:13 [2018-01-24 11:46:57,260 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-24 11:46:57,280 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-24 11:46:57,280 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 17] total 32 [2018-01-24 11:46:57,281 INFO L409 AbstractCegarLoop]: Interpolant automaton has 33 states [2018-01-24 11:46:57,281 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2018-01-24 11:46:57,281 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=91, Invalid=965, Unknown=0, NotChecked=0, Total=1056 [2018-01-24 11:46:57,282 INFO L87 Difference]: Start difference. First operand 70 states and 81 transitions. Second operand 33 states. [2018-01-24 11:46:57,856 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 11:46:57,856 INFO L93 Difference]: Finished difference Result 90 states and 102 transitions. [2018-01-24 11:46:57,856 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2018-01-24 11:46:57,856 INFO L78 Accepts]: Start accepts. Automaton has 33 states. Word has length 35 [2018-01-24 11:46:57,856 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 11:46:57,857 INFO L225 Difference]: With dead ends: 90 [2018-01-24 11:46:57,857 INFO L226 Difference]: Without dead ends: 87 [2018-01-24 11:46:57,857 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 64 GetRequests, 21 SyntacticMatches, 0 SemanticMatches, 43 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 402 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=217, Invalid=1763, Unknown=0, NotChecked=0, Total=1980 [2018-01-24 11:46:57,858 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 87 states. [2018-01-24 11:46:57,866 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 87 to 84. [2018-01-24 11:46:57,866 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 84 states. [2018-01-24 11:46:57,866 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 84 states to 84 states and 96 transitions. [2018-01-24 11:46:57,866 INFO L78 Accepts]: Start accepts. Automaton has 84 states and 96 transitions. Word has length 35 [2018-01-24 11:46:57,867 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 11:46:57,867 INFO L432 AbstractCegarLoop]: Abstraction has 84 states and 96 transitions. [2018-01-24 11:46:57,867 INFO L433 AbstractCegarLoop]: Interpolant automaton has 33 states. [2018-01-24 11:46:57,867 INFO L276 IsEmpty]: Start isEmpty. Operand 84 states and 96 transitions. [2018-01-24 11:46:57,867 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2018-01-24 11:46:57,867 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 11:46:57,867 INFO L322 BasicCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-24 11:46:57,867 INFO L371 AbstractCegarLoop]: === Iteration 21 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 11:46:57,867 INFO L82 PathProgramCache]: Analyzing trace with hash -1689703552, now seen corresponding path program 2 times [2018-01-24 11:46:57,867 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-24 11:46:57,868 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-24 11:46:57,868 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 11:46:57,868 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 11:46:57,868 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 11:46:57,884 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 11:46:57,884 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 11:46:58,439 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-24 11:46:58,440 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-24 11:46:58,440 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-24 11:46:58,447 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-01-24 11:46:58,459 INFO L201 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-24 11:46:58,465 INFO L214 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-24 11:46:58,467 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-24 11:46:58,470 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-24 11:46:58,472 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 11:46:58,472 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 11:46:58,473 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 11:46:58,474 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:6, output treesize:5 [2018-01-24 11:46:58,476 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 11:46:58,476 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 11:46:58,482 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:46:58,483 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:46:58,483 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 11:46:58,483 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 11:46:58,486 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 11:46:58,486 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:20, output treesize:13 [2018-01-24 11:46:58,521 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 11:46:58,522 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 11:46:58,522 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 11:46:58,524 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 11:46:58,528 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 11:46:58,528 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:27, output treesize:23 [2018-01-24 11:46:58,694 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 24 treesize of output 25 [2018-01-24 11:46:58,696 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-01-24 11:46:58,696 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 11:46:58,700 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 11:46:58,707 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-24 11:46:58,708 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:37, output treesize:26 [2018-01-24 11:46:58,775 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 18 [2018-01-24 11:46:58,781 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 11:46:58,781 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-24 11:46:58,784 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-24 11:46:58,791 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 11:46:58,791 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:36, output treesize:37 [2018-01-24 11:46:58,837 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-24 11:46:58,856 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-24 11:46:58,856 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 27 [2018-01-24 11:46:58,856 INFO L409 AbstractCegarLoop]: Interpolant automaton has 28 states [2018-01-24 11:46:58,857 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2018-01-24 11:46:58,857 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=64, Invalid=692, Unknown=0, NotChecked=0, Total=756 [2018-01-24 11:46:58,857 INFO L87 Difference]: Start difference. First operand 84 states and 96 transitions. Second operand 28 states. [2018-01-24 11:46:59,808 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 11:46:59,808 INFO L93 Difference]: Finished difference Result 94 states and 104 transitions. [2018-01-24 11:46:59,808 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2018-01-24 11:46:59,808 INFO L78 Accepts]: Start accepts. Automaton has 28 states. Word has length 36 [2018-01-24 11:46:59,808 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 11:46:59,809 INFO L225 Difference]: With dead ends: 94 [2018-01-24 11:46:59,809 INFO L226 Difference]: Without dead ends: 93 [2018-01-24 11:46:59,809 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 68 GetRequests, 25 SyntacticMatches, 1 SemanticMatches, 42 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 228 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=205, Invalid=1687, Unknown=0, NotChecked=0, Total=1892 [2018-01-24 11:46:59,810 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 93 states. [2018-01-24 11:46:59,818 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 93 to 63. [2018-01-24 11:46:59,818 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 63 states. [2018-01-24 11:46:59,818 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 71 transitions. [2018-01-24 11:46:59,819 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 71 transitions. Word has length 36 [2018-01-24 11:46:59,819 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 11:46:59,819 INFO L432 AbstractCegarLoop]: Abstraction has 63 states and 71 transitions. [2018-01-24 11:46:59,819 INFO L433 AbstractCegarLoop]: Interpolant automaton has 28 states. [2018-01-24 11:46:59,819 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 71 transitions. [2018-01-24 11:46:59,819 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2018-01-24 11:46:59,819 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 11:46:59,819 INFO L322 BasicCegarLoop]: trace histogram [6, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-24 11:46:59,819 INFO L371 AbstractCegarLoop]: === Iteration 22 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 11:46:59,820 INFO L82 PathProgramCache]: Analyzing trace with hash -663196535, now seen corresponding path program 3 times [2018-01-24 11:46:59,820 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-24 11:46:59,820 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-24 11:46:59,820 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 11:46:59,820 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-01-24 11:46:59,820 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 11:46:59,833 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 11:46:59,833 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 11:47:00,643 WARN L146 SmtUtils]: Spent 245ms on a formula simplification. DAG size of input: 51 DAG size of output 41 [2018-01-24 11:47:00,890 WARN L146 SmtUtils]: Spent 165ms on a formula simplification. DAG size of input: 54 DAG size of output 44 [2018-01-24 11:47:01,022 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-24 11:47:01,022 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-24 11:47:01,022 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-24 11:47:01,027 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-01-24 11:47:01,038 INFO L254 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued a check-sat command [2018-01-24 11:47:01,043 INFO L254 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued a check-sat command [2018-01-24 11:47:01,046 INFO L254 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued a check-sat command [2018-01-24 11:47:01,049 INFO L254 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued a check-sat command [2018-01-24 11:47:01,052 INFO L254 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued a check-sat command [2018-01-24 11:47:01,055 INFO L254 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued a check-sat command [2018-01-24 11:47:01,057 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-24 11:47:01,061 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-24 11:47:01,126 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-24 11:47:01,126 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 11:47:01,134 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 11:47:01,135 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 11:47:01,141 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 11:47:01,141 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:27, output treesize:25 [2018-01-24 11:47:01,206 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:47:01,207 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:47:01,207 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 11:47:01,208 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 11:47:01,222 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:47:01,222 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:47:01,223 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 11:47:01,223 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 11:47:01,231 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 11:47:01,231 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:39, output treesize:28 [2018-01-24 11:47:01,293 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 11:47:01,295 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 11:47:01,295 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 11:47:01,297 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 11:47:01,305 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 11:47:01,305 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:44, output treesize:40 [2018-01-24 11:47:01,344 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:47:01,347 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 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 11:47:01,349 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 11 [2018-01-24 11:47:01,349 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 11:47:01,353 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 11:47:01,361 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 11:47:01,362 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:51, output treesize:47 [2018-01-24 11:47:01,911 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:47:01,912 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 57 treesize of output 49 [2018-01-24 11:47:01,914 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 9 treesize of output 1 [2018-01-24 11:47:01,915 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 11:47:01,974 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 5 select indices, 5 select index equivalence classes, 6 disjoint index pairs (out of 10 index pairs), introduced 3 new quantified variables, introduced 7 case distinctions, treesize of input 36 treesize of output 109 [2018-01-24 11:47:01,974 WARN L130 XnfTransformerHelper]: expecting exponential blowup for input size 7 [2018-01-24 11:47:02,006 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 72 xjuncts. [2018-01-24 11:47:02,208 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-24 11:47:02,256 INFO L267 ElimStorePlain]: Start of recursive call 1: 5 dim-0 vars, 1 dim-2 vars, End of recursive call: 18 dim-0 vars, and 2 xjuncts. [2018-01-24 11:47:02,257 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 6 variables, input treesize:92, output treesize:940 [2018-01-24 11:47:02,662 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-24 11:47:02,682 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-24 11:47:02,682 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 23] total 42 [2018-01-24 11:47:02,682 INFO L409 AbstractCegarLoop]: Interpolant automaton has 43 states [2018-01-24 11:47:02,682 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 43 interpolants. [2018-01-24 11:47:02,683 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=179, Invalid=1627, Unknown=0, NotChecked=0, Total=1806 [2018-01-24 11:47:02,683 INFO L87 Difference]: Start difference. First operand 63 states and 71 transitions. Second operand 43 states. [2018-01-24 11:47:04,322 WARN L146 SmtUtils]: Spent 105ms on a formula simplification. DAG size of input: 159 DAG size of output 90 [2018-01-24 11:47:04,912 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 11:47:04,913 INFO L93 Difference]: Finished difference Result 118 states and 136 transitions. [2018-01-24 11:47:04,913 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2018-01-24 11:47:04,913 INFO L78 Accepts]: Start accepts. Automaton has 43 states. Word has length 36 [2018-01-24 11:47:04,914 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 11:47:04,914 INFO L225 Difference]: With dead ends: 118 [2018-01-24 11:47:04,914 INFO L226 Difference]: Without dead ends: 112 [2018-01-24 11:47:04,915 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 77 GetRequests, 14 SyntacticMatches, 1 SemanticMatches, 62 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 968 ImplicationChecksByTransitivity, 3.8s TimeCoverageRelationStatistics Valid=553, Invalid=3479, Unknown=0, NotChecked=0, Total=4032 [2018-01-24 11:47:04,915 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 112 states. [2018-01-24 11:47:04,929 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 112 to 69. [2018-01-24 11:47:04,947 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 69 states. [2018-01-24 11:47:04,948 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 69 states to 69 states and 79 transitions. [2018-01-24 11:47:04,948 INFO L78 Accepts]: Start accepts. Automaton has 69 states and 79 transitions. Word has length 36 [2018-01-24 11:47:04,948 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 11:47:04,948 INFO L432 AbstractCegarLoop]: Abstraction has 69 states and 79 transitions. [2018-01-24 11:47:04,948 INFO L433 AbstractCegarLoop]: Interpolant automaton has 43 states. [2018-01-24 11:47:04,948 INFO L276 IsEmpty]: Start isEmpty. Operand 69 states and 79 transitions. [2018-01-24 11:47:04,949 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2018-01-24 11:47:04,949 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 11:47:04,949 INFO L322 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-24 11:47:04,949 INFO L371 AbstractCegarLoop]: === Iteration 23 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 11:47:04,949 INFO L82 PathProgramCache]: Analyzing trace with hash -601444785, now seen corresponding path program 1 times [2018-01-24 11:47:04,949 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-24 11:47:04,949 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-24 11:47:04,950 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 11:47:04,950 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-01-24 11:47:04,950 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 11:47:04,962 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 11:47:04,963 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 11:47:05,366 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 0 proven. 9 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-24 11:47:05,366 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-24 11:47:05,366 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-24 11:47:05,372 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 11:47:05,399 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 11:47:05,403 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-24 11:47:05,435 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 11:47:05,435 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 11:47:05,447 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 11:47:05,448 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 11:47:05,454 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 11:47:05,454 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:21, output treesize:16 [2018-01-24 11:47:05,512 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:47:05,513 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:47:05,514 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 11:47:05,514 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 11:47:05,525 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:47:05,526 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:47:05,526 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 11:47:05,526 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 11:47:05,532 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 11:47:05,532 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:30, output treesize:19 [2018-01-24 11:47:05,584 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 15 treesize of output 12 [2018-01-24 11:47:05,586 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 11 [2018-01-24 11:47:05,587 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 11:47:05,589 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 11:47:05,595 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-24 11:47:05,595 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:28, output treesize:24 [2018-01-24 11:47:05,839 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:47:05,843 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 23 treesize of output 24 [2018-01-24 11:47:05,848 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-01-24 11:47:05,849 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 11:47:05,869 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 11:47:05,877 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-24 11:47:05,877 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:41, output treesize:30 [2018-01-24 11:47:05,969 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 15 [2018-01-24 11:47:05,977 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 12 [2018-01-24 11:47:05,977 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-24 11:47:05,981 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-24 11:47:05,992 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 2 xjuncts. [2018-01-24 11:47:05,992 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:44, output treesize:51 [2018-01-24 11:47:06,083 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 0 proven. 9 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-24 11:47:06,103 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-24 11:47:06,103 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 19] total 39 [2018-01-24 11:47:06,103 INFO L409 AbstractCegarLoop]: Interpolant automaton has 40 states [2018-01-24 11:47:06,104 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 40 interpolants. [2018-01-24 11:47:06,104 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=118, Invalid=1442, Unknown=0, NotChecked=0, Total=1560 [2018-01-24 11:47:06,104 INFO L87 Difference]: Start difference. First operand 69 states and 79 transitions. Second operand 40 states. [2018-01-24 11:47:08,526 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 11:47:08,526 INFO L93 Difference]: Finished difference Result 116 states and 129 transitions. [2018-01-24 11:47:08,526 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 35 states. [2018-01-24 11:47:08,526 INFO L78 Accepts]: Start accepts. Automaton has 40 states. Word has length 38 [2018-01-24 11:47:08,526 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 11:47:08,527 INFO L225 Difference]: With dead ends: 116 [2018-01-24 11:47:08,527 INFO L226 Difference]: Without dead ends: 112 [2018-01-24 11:47:08,529 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 88 GetRequests, 21 SyntacticMatches, 0 SemanticMatches, 67 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1141 ImplicationChecksByTransitivity, 2.5s TimeCoverageRelationStatistics Valid=446, Invalid=4246, Unknown=0, NotChecked=0, Total=4692 [2018-01-24 11:47:08,529 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 112 states. [2018-01-24 11:47:08,542 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 112 to 75. [2018-01-24 11:47:08,542 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 75 states. [2018-01-24 11:47:08,542 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 75 states to 75 states and 85 transitions. [2018-01-24 11:47:08,542 INFO L78 Accepts]: Start accepts. Automaton has 75 states and 85 transitions. Word has length 38 [2018-01-24 11:47:08,542 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 11:47:08,542 INFO L432 AbstractCegarLoop]: Abstraction has 75 states and 85 transitions. [2018-01-24 11:47:08,542 INFO L433 AbstractCegarLoop]: Interpolant automaton has 40 states. [2018-01-24 11:47:08,543 INFO L276 IsEmpty]: Start isEmpty. Operand 75 states and 85 transitions. [2018-01-24 11:47:08,543 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2018-01-24 11:47:08,543 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 11:47:08,543 INFO L322 BasicCegarLoop]: trace histogram [3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-24 11:47:08,543 INFO L371 AbstractCegarLoop]: === Iteration 24 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 11:47:08,543 INFO L82 PathProgramCache]: Analyzing trace with hash 669200065, now seen corresponding path program 2 times [2018-01-24 11:47:08,543 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-24 11:47:08,543 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-24 11:47:08,544 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 11:47:08,544 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-24 11:47:08,544 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 11:47:08,557 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 11:47:08,558 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 11:47:09,263 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 11:47:09,263 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-24 11:47:09,263 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-24 11:47:09,268 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-01-24 11:47:09,280 INFO L201 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-24 11:47:09,286 INFO L214 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-24 11:47:09,290 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-24 11:47:09,293 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-24 11:47:09,295 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 11:47:09,296 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 11:47:09,303 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 11:47:09,303 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 11:47:09,308 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 11:47:09,308 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:24, output treesize:22 [2018-01-24 11:47:09,365 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:47:09,366 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:47:09,366 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 4 [2018-01-24 11:47:09,366 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 11:47:09,374 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:47:09,374 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 11:47:09,375 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 11:47:09,381 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 11:47:09,381 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:33, output treesize:22 [2018-01-24 11:47:09,440 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 11:47:09,442 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 11:47:09,442 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 11:47:09,443 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 11:47:09,448 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-24 11:47:09,449 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:38, output treesize:34 [2018-01-24 11:47:09,483 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:47:09,485 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 32 treesize of output 33 [2018-01-24 11:47:09,487 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 11:47:09,487 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 11:47:09,491 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 11:47:09,497 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-24 11:47:09,497 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:47, output treesize:43 [2018-01-24 11:47:09,741 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:47:09,742 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 35 treesize of output 33 [2018-01-24 11:47:09,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, 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 11:47:09,745 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 11:47:09,755 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 19 treesize of output 16 [2018-01-24 11:47:09,755 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 2 xjuncts. [2018-01-24 11:47:09,759 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-24 11:47:09,767 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 11:47:09,768 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 3 variables, input treesize:55, output treesize:57 [2018-01-24 11:47:10,479 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 11:47:10,499 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-24 11:47:10,499 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [23, 24] total 44 [2018-01-24 11:47:10,500 INFO L409 AbstractCegarLoop]: Interpolant automaton has 45 states [2018-01-24 11:47:10,500 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 45 interpolants. [2018-01-24 11:47:10,500 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=115, Invalid=1865, Unknown=0, NotChecked=0, Total=1980 [2018-01-24 11:47:10,500 INFO L87 Difference]: Start difference. First operand 75 states and 85 transitions. Second operand 45 states. [2018-01-24 11:47:13,939 WARN L146 SmtUtils]: Spent 143ms on a formula simplification. DAG size of input: 82 DAG size of output 76 [2018-01-24 11:47:14,194 WARN L146 SmtUtils]: Spent 100ms on a formula simplification. DAG size of input: 93 DAG size of output 64 [2018-01-24 11:47:14,592 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 11:47:14,593 INFO L93 Difference]: Finished difference Result 129 states and 140 transitions. [2018-01-24 11:47:14,593 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 37 states. [2018-01-24 11:47:14,593 INFO L78 Accepts]: Start accepts. Automaton has 45 states. Word has length 41 [2018-01-24 11:47:14,593 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 11:47:14,594 INFO L225 Difference]: With dead ends: 129 [2018-01-24 11:47:14,594 INFO L226 Difference]: Without dead ends: 126 [2018-01-24 11:47:14,595 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 91 GetRequests, 21 SyntacticMatches, 0 SemanticMatches, 70 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 961 ImplicationChecksByTransitivity, 4.4s TimeCoverageRelationStatistics Valid=375, Invalid=4737, Unknown=0, NotChecked=0, Total=5112 [2018-01-24 11:47:14,595 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 126 states. [2018-01-24 11:47:14,608 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 126 to 75. [2018-01-24 11:47:14,608 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 75 states. [2018-01-24 11:47:14,609 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 75 states to 75 states and 85 transitions. [2018-01-24 11:47:14,609 INFO L78 Accepts]: Start accepts. Automaton has 75 states and 85 transitions. Word has length 41 [2018-01-24 11:47:14,609 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 11:47:14,609 INFO L432 AbstractCegarLoop]: Abstraction has 75 states and 85 transitions. [2018-01-24 11:47:14,609 INFO L433 AbstractCegarLoop]: Interpolant automaton has 45 states. [2018-01-24 11:47:14,609 INFO L276 IsEmpty]: Start isEmpty. Operand 75 states and 85 transitions. [2018-01-24 11:47:14,609 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2018-01-24 11:47:14,609 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 11:47:14,610 INFO L322 BasicCegarLoop]: trace histogram [8, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-24 11:47:14,610 INFO L371 AbstractCegarLoop]: === Iteration 25 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 11:47:14,610 INFO L82 PathProgramCache]: Analyzing trace with hash 296873801, now seen corresponding path program 4 times [2018-01-24 11:47:14,610 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-24 11:47:14,610 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-24 11:47:14,611 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 11:47:14,611 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-01-24 11:47:14,611 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 11:47:14,630 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 11:47:14,631 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 11:47:14,965 WARN L146 SmtUtils]: Spent 120ms on a formula simplification. DAG size of input: 30 DAG size of output 24 [2018-01-24 11:47:15,188 WARN L146 SmtUtils]: Spent 140ms on a formula simplification. DAG size of input: 90 DAG size of output 75 [2018-01-24 11:47:15,339 WARN L146 SmtUtils]: Spent 104ms on a formula simplification. DAG size of input: 65 DAG size of output 52 [2018-01-24 11:47:15,573 WARN L146 SmtUtils]: Spent 109ms on a formula simplification. DAG size of input: 65 DAG size of output 52 [2018-01-24 11:47:15,712 WARN L146 SmtUtils]: Spent 117ms on a formula simplification. DAG size of input: 68 DAG size of output 55 [2018-01-24 11:47:15,862 WARN L146 SmtUtils]: Spent 126ms on a formula simplification. DAG size of input: 82 DAG size of output 60 [2018-01-24 11:47:16,022 WARN L146 SmtUtils]: Spent 133ms on a formula simplification. DAG size of input: 85 DAG size of output 63 [2018-01-24 11:47:16,416 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 0 proven. 77 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-24 11:47:16,416 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-24 11:47:16,416 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-24 11:47:16,421 INFO L101 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-01-24 11:47:16,442 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-24 11:47:16,446 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-24 11:47:16,508 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-24 11:47:16,509 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 11:47:16,516 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 11:47:16,516 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 11:47:16,522 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 11:47:16,522 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:27, output treesize:25 [2018-01-24 11:47:16,584 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:47:16,585 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:47:16,585 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 11:47:16,585 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 11:47:16,598 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:47:16,599 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:47:16,599 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 11:47:16,599 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 11:47:16,607 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 11:47:16,607 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:39, output treesize:28 [2018-01-24 11:47:16,672 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 11:47:16,673 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 11:47:16,673 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 11:47:16,675 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 11:47:16,683 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 11:47:16,683 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:44, output treesize:40 [2018-01-24 11:47:16,723 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:47:16,726 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 11:47:16,728 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 11 [2018-01-24 11:47:16,728 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 11:47:16,732 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 11:47:16,740 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 11:47:16,740 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:51, output treesize:47 [2018-01-24 11:47:17,551 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:47:17,595 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 83 treesize of output 71 [2018-01-24 11:47:17,600 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 9 treesize of output 1 [2018-01-24 11:47:17,600 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 11:47:17,619 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:47:17,620 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:47:17,621 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:47:17,622 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:47:17,622 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:47:17,625 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:47:17,626 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:47:17,626 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:47:17,627 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:47:17,628 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:47:17,629 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:47:17,630 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:47:17,630 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:47:17,631 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:47:17,632 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:47:17,651 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 7 select indices, 7 select index equivalence classes, 25 disjoint index pairs (out of 21 index pairs), introduced 5 new quantified variables, introduced 1 case distinctions, treesize of input 58 treesize of output 211 [2018-01-24 11:47:17,652 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 2 xjuncts. [2018-01-24 11:47:17,734 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-24 11:47:17,775 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: 4 dim-0 vars, and 2 xjuncts. [2018-01-24 11:47:17,776 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 3 variables, input treesize:106, output treesize:228 [2018-01-24 11:47:18,057 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 0 proven. 77 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-24 11:47:18,078 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-24 11:47:18,078 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [24, 26] total 49 [2018-01-24 11:47:18,078 INFO L409 AbstractCegarLoop]: Interpolant automaton has 50 states [2018-01-24 11:47:18,078 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 50 interpolants. [2018-01-24 11:47:18,079 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=273, Invalid=2177, Unknown=0, NotChecked=0, Total=2450 [2018-01-24 11:47:18,079 INFO L87 Difference]: Start difference. First operand 75 states and 85 transitions. Second operand 50 states. [2018-01-24 11:47:20,528 WARN L146 SmtUtils]: Spent 189ms on a formula simplification. DAG size of input: 203 DAG size of output 111 [2018-01-24 11:47:22,472 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 11:47:22,472 INFO L93 Difference]: Finished difference Result 171 states and 200 transitions. [2018-01-24 11:47:22,472 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 41 states. [2018-01-24 11:47:22,472 INFO L78 Accepts]: Start accepts. Automaton has 50 states. Word has length 42 [2018-01-24 11:47:22,473 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 11:47:22,473 INFO L225 Difference]: With dead ends: 171 [2018-01-24 11:47:22,473 INFO L226 Difference]: Without dead ends: 163 [2018-01-24 11:47:22,475 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 99 GetRequests, 17 SyntacticMatches, 1 SemanticMatches, 81 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1928 ImplicationChecksByTransitivity, 5.8s TimeCoverageRelationStatistics Valid=879, Invalid=5927, Unknown=0, NotChecked=0, Total=6806 [2018-01-24 11:47:22,475 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 163 states. [2018-01-24 11:47:22,494 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 163 to 87. [2018-01-24 11:47:22,494 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 87 states. [2018-01-24 11:47:22,504 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 87 states to 87 states and 101 transitions. [2018-01-24 11:47:22,505 INFO L78 Accepts]: Start accepts. Automaton has 87 states and 101 transitions. Word has length 42 [2018-01-24 11:47:22,505 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 11:47:22,505 INFO L432 AbstractCegarLoop]: Abstraction has 87 states and 101 transitions. [2018-01-24 11:47:22,505 INFO L433 AbstractCegarLoop]: Interpolant automaton has 50 states. [2018-01-24 11:47:22,505 INFO L276 IsEmpty]: Start isEmpty. Operand 87 states and 101 transitions. [2018-01-24 11:47:22,505 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2018-01-24 11:47:22,505 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 11:47:22,505 INFO L322 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 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] [2018-01-24 11:47:22,505 INFO L371 AbstractCegarLoop]: === Iteration 26 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 11:47:22,506 INFO L82 PathProgramCache]: Analyzing trace with hash -889231934, now seen corresponding path program 3 times [2018-01-24 11:47:22,506 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-24 11:47:22,506 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-24 11:47:22,506 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 11:47:22,506 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-01-24 11:47:22,506 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 11:47:22,519 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 11:47:22,520 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 11:47:22,996 INFO L134 CoverageAnalysis]: Checked inductivity of 21 backedges. 1 proven. 20 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-24 11:47:22,997 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-24 11:47:22,997 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-24 11:47:23,002 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-01-24 11:47:23,015 INFO L254 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued a check-sat command [2018-01-24 11:47:23,021 INFO L254 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued a check-sat command [2018-01-24 11:47:23,027 INFO L254 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued a check-sat command [2018-01-24 11:47:23,030 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-24 11:47:23,033 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-24 11:47:23,050 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 11:47:23,050 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 11:47:23,058 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 11:47:23,058 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 11:47:23,063 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 11:47:23,063 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:21, output treesize:16 [2018-01-24 11:47:23,108 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:47:23,108 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:47:23,109 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 11:47:23,109 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 11:47:23,119 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:47:23,120 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:47:23,120 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 11:47:23,121 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 11:47:23,126 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 11:47:23,126 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:30, output treesize:19 [2018-01-24 11:47:23,174 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 16 treesize of output 13 [2018-01-24 11:47:23,176 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 11:47:23,176 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 11:47:23,177 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 11:47:23,182 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-24 11:47:23,182 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:32, output treesize:28 [2018-01-24 11:47:23,388 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:47:23,391 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 24 treesize of output 25 [2018-01-24 11:47:23,393 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-01-24 11:47:23,393 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 11:47:23,397 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 11:47:23,404 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-24 11:47:23,405 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:44, output treesize:33 [2018-01-24 11:47:23,484 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:47:23,487 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 24 treesize of output 25 [2018-01-24 11:47:23,489 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-01-24 11:47:23,489 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 11:47:23,493 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 11:47:23,500 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-24 11:47:23,501 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:44, output treesize:33 [2018-01-24 11:47:23,585 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 20 treesize of output 16 [2018-01-24 11:47:23,591 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 16 treesize of output 13 [2018-01-24 11:47:23,591 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-24 11:47:23,594 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-24 11:47:23,604 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-2 vars, End of recursive call: 2 dim-0 vars, and 2 xjuncts. [2018-01-24 11:47:23,604 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:47, output treesize:45 [2018-01-24 11:47:23,767 INFO L134 CoverageAnalysis]: Checked inductivity of 21 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-24 11:47:23,787 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-24 11:47:23,787 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [23, 20] total 41 [2018-01-24 11:47:23,787 INFO L409 AbstractCegarLoop]: Interpolant automaton has 42 states [2018-01-24 11:47:23,788 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 42 interpolants. [2018-01-24 11:47:23,788 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=114, Invalid=1608, Unknown=0, NotChecked=0, Total=1722 [2018-01-24 11:47:23,788 INFO L87 Difference]: Start difference. First operand 87 states and 101 transitions. Second operand 42 states. [2018-01-24 11:47:26,554 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-24 11:47:26,554 INFO L93 Difference]: Finished difference Result 154 states and 172 transitions. [2018-01-24 11:47:26,554 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 43 states. [2018-01-24 11:47:26,555 INFO L78 Accepts]: Start accepts. Automaton has 42 states. Word has length 44 [2018-01-24 11:47:26,555 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-24 11:47:26,555 INFO L225 Difference]: With dead ends: 154 [2018-01-24 11:47:26,555 INFO L226 Difference]: Without dead ends: 120 [2018-01-24 11:47:26,557 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 108 GetRequests, 31 SyntacticMatches, 0 SemanticMatches, 77 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1478 ImplicationChecksByTransitivity, 2.8s TimeCoverageRelationStatistics Valid=467, Invalid=5695, Unknown=0, NotChecked=0, Total=6162 [2018-01-24 11:47:26,557 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 120 states. [2018-01-24 11:47:26,574 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 120 to 87. [2018-01-24 11:47:26,574 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 87 states. [2018-01-24 11:47:26,575 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 87 states to 87 states and 100 transitions. [2018-01-24 11:47:26,575 INFO L78 Accepts]: Start accepts. Automaton has 87 states and 100 transitions. Word has length 44 [2018-01-24 11:47:26,575 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-24 11:47:26,575 INFO L432 AbstractCegarLoop]: Abstraction has 87 states and 100 transitions. [2018-01-24 11:47:26,575 INFO L433 AbstractCegarLoop]: Interpolant automaton has 42 states. [2018-01-24 11:47:26,575 INFO L276 IsEmpty]: Start isEmpty. Operand 87 states and 100 transitions. [2018-01-24 11:47:26,576 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2018-01-24 11:47:26,576 INFO L314 BasicCegarLoop]: Found error trace [2018-01-24 11:47:26,576 INFO L322 BasicCegarLoop]: trace histogram [4, 4, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-24 11:47:26,576 INFO L371 AbstractCegarLoop]: === Iteration 27 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-24 11:47:26,576 INFO L82 PathProgramCache]: Analyzing trace with hash -1391820529, now seen corresponding path program 4 times [2018-01-24 11:47:26,576 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-24 11:47:26,576 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-24 11:47:26,577 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 11:47:26,577 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-01-24 11:47:26,577 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-24 11:47:26,591 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-24 11:47:26,592 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-24 11:47:27,590 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-01-24 11:47:27,591 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-24 11:47:27,591 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 15 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 15 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-24 11:47:27,596 INFO L101 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-01-24 11:47:27,621 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-24 11:47:27,625 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-24 11:47:27,676 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 11:47:27,676 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-24 11:47:27,684 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 11:47:27,684 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 11:47:27,690 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-24 11:47:27,691 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:27, output treesize:25 [2018-01-24 11:47:27,746 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:47:27,746 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:47:27,747 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 11:47:27,747 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. Received shutdown request... [2018-01-24 11:47:27,761 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:47:27,761 INFO L700 Elim1Store]: detected not equals via solver [2018-01-24 11:47:27,762 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 11:47:27,762 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-24 11:47:27,768 INFO L175 TraceCheckSpWp]: Timeout while computing interpolants [2018-01-24 11:47:27,768 WARN L491 AbstractCegarLoop]: Verification canceled [2018-01-24 11:47:27,773 WARN L187 ceAbstractionStarter]: Timeout [2018-01-24 11:47:27,773 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 24.01 11:47:27 BoogieIcfgContainer [2018-01-24 11:47:27,773 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-01-24 11:47:27,774 INFO L168 Benchmark]: Toolchain (without parser) took 52847.16 ms. Allocated memory was 307.2 MB in the beginning and 718.3 MB in the end (delta: 411.0 MB). Free memory was 267.2 MB in the beginning and 680.5 MB in the end (delta: -413.3 MB). Peak memory consumption was 374.1 MB. Max. memory is 5.3 GB. [2018-01-24 11:47:27,775 INFO L168 Benchmark]: CDTParser took 0.11 ms. Allocated memory is still 307.2 MB. Free memory is still 273.2 MB. There was no memory consumed. Max. memory is 5.3 GB. [2018-01-24 11:47:27,775 INFO L168 Benchmark]: CACSL2BoogieTranslator took 202.46 ms. Allocated memory is still 307.2 MB. Free memory was 266.2 MB in the beginning and 256.0 MB in the end (delta: 10.2 MB). Peak memory consumption was 10.2 MB. Max. memory is 5.3 GB. [2018-01-24 11:47:27,776 INFO L168 Benchmark]: Boogie Preprocessor took 32.78 ms. Allocated memory is still 307.2 MB. Free memory was 256.0 MB in the beginning and 254.0 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 5.3 GB. [2018-01-24 11:47:27,776 INFO L168 Benchmark]: RCFGBuilder took 275.83 ms. Allocated memory is still 307.2 MB. Free memory was 254.0 MB in the beginning and 234.0 MB in the end (delta: 20.0 MB). Peak memory consumption was 20.0 MB. Max. memory is 5.3 GB. [2018-01-24 11:47:27,776 INFO L168 Benchmark]: TraceAbstraction took 52328.54 ms. Allocated memory was 307.2 MB in the beginning and 718.3 MB in the end (delta: 411.0 MB). Free memory was 234.0 MB in the beginning and 680.5 MB in the end (delta: -446.5 MB). Peak memory consumption was 340.9 MB. Max. memory is 5.3 GB. [2018-01-24 11:47:27,778 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.11 ms. Allocated memory is still 307.2 MB. Free memory is still 273.2 MB. There was no memory consumed. Max. memory is 5.3 GB. * CACSL2BoogieTranslator took 202.46 ms. Allocated memory is still 307.2 MB. Free memory was 266.2 MB in the beginning and 256.0 MB in the end (delta: 10.2 MB). Peak memory consumption was 10.2 MB. Max. memory is 5.3 GB. * Boogie Preprocessor took 32.78 ms. Allocated memory is still 307.2 MB. Free memory was 256.0 MB in the beginning and 254.0 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 5.3 GB. * RCFGBuilder took 275.83 ms. Allocated memory is still 307.2 MB. Free memory was 254.0 MB in the beginning and 234.0 MB in the end (delta: 20.0 MB). Peak memory consumption was 20.0 MB. Max. memory is 5.3 GB. * TraceAbstraction took 52328.54 ms. Allocated memory was 307.2 MB in the beginning and 718.3 MB in the end (delta: 411.0 MB). Free memory was 234.0 MB in the beginning and 680.5 MB in the end (delta: -446.5 MB). Peak memory consumption was 340.9 MB. Max. memory is 5.3 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 574). Cancelled while BasicCegarLoop was analyzing trace of length 45 with TraceHistMax 4, while TraceCheckSpWp was constructing forward predicates, while PartialQuantifierElimination was eliminating quantifiers from formula with 0 quantifier alternations, while SimplifyDDAWithTimeout was simplifying term of DAG size 23. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 573). Cancelled while BasicCegarLoop was analyzing trace of length 45 with TraceHistMax 4, while TraceCheckSpWp was constructing forward predicates, while PartialQuantifierElimination was eliminating quantifiers from formula with 0 quantifier alternations, while SimplifyDDAWithTimeout was simplifying term of DAG size 23. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 574). Cancelled while BasicCegarLoop was analyzing trace of length 45 with TraceHistMax 4, while TraceCheckSpWp was constructing forward predicates, while PartialQuantifierElimination was eliminating quantifiers from formula with 0 quantifier alternations, while SimplifyDDAWithTimeout was simplifying term of DAG size 23. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 573). Cancelled while BasicCegarLoop was analyzing trace of length 45 with TraceHistMax 4, while TraceCheckSpWp was constructing forward predicates, while PartialQuantifierElimination was eliminating quantifiers from formula with 0 quantifier alternations, while SimplifyDDAWithTimeout was simplifying term of DAG size 23. - TimeoutResultAtElement [Line: 557]: Timeout (TraceAbstraction) Unable to prove that all allocated memory was freed (line 557). Cancelled while BasicCegarLoop was analyzing trace of length 45 with TraceHistMax 4, while TraceCheckSpWp was constructing forward predicates, while PartialQuantifierElimination was eliminating quantifiers from formula with 0 quantifier alternations, while SimplifyDDAWithTimeout was simplifying term of DAG size 23. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 553). Cancelled while BasicCegarLoop was analyzing trace of length 45 with TraceHistMax 4, while TraceCheckSpWp was constructing forward predicates, while PartialQuantifierElimination was eliminating quantifiers from formula with 0 quantifier alternations, while SimplifyDDAWithTimeout was simplifying term of DAG size 23. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 549). Cancelled while BasicCegarLoop was analyzing trace of length 45 with TraceHistMax 4, while TraceCheckSpWp was constructing forward predicates, while PartialQuantifierElimination was eliminating quantifiers from formula with 0 quantifier alternations, while SimplifyDDAWithTimeout was simplifying term of DAG size 23. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 546). Cancelled while BasicCegarLoop was analyzing trace of length 45 with TraceHistMax 4, while TraceCheckSpWp was constructing forward predicates, while PartialQuantifierElimination was eliminating quantifiers from formula with 0 quantifier alternations, while SimplifyDDAWithTimeout was simplifying term of DAG size 23. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 549). Cancelled while BasicCegarLoop was analyzing trace of length 45 with TraceHistMax 4, while TraceCheckSpWp was constructing forward predicates, while PartialQuantifierElimination was eliminating quantifiers from formula with 0 quantifier alternations, while SimplifyDDAWithTimeout was simplifying term of DAG size 23. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 546). Cancelled while BasicCegarLoop was analyzing trace of length 45 with TraceHistMax 4, while TraceCheckSpWp was constructing forward predicates, while PartialQuantifierElimination was eliminating quantifiers from formula with 0 quantifier alternations, while SimplifyDDAWithTimeout was simplifying term of DAG size 23. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 549). Cancelled while BasicCegarLoop was analyzing trace of length 45 with TraceHistMax 4, while TraceCheckSpWp was constructing forward predicates, while PartialQuantifierElimination was eliminating quantifiers from formula with 0 quantifier alternations, while SimplifyDDAWithTimeout was simplifying term of DAG size 23. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 553). Cancelled while BasicCegarLoop was analyzing trace of length 45 with TraceHistMax 4, while TraceCheckSpWp was constructing forward predicates, while PartialQuantifierElimination was eliminating quantifiers from formula with 0 quantifier alternations, while SimplifyDDAWithTimeout was simplifying term of DAG size 23. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 549). Cancelled while BasicCegarLoop was analyzing trace of length 45 with TraceHistMax 4, while TraceCheckSpWp was constructing forward predicates, while PartialQuantifierElimination was eliminating quantifiers from formula with 0 quantifier alternations, while SimplifyDDAWithTimeout was simplifying term of DAG size 23. - StatisticsResult: Ultimate Automizer benchmark data CFG has 4 procedures, 54 locations, 13 error locations. TIMEOUT Result, 52.2s OverallTime, 27 OverallIterations, 8 TraceHistogramMax, 28.2s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 917 SDtfs, 2884 SDslu, 7462 SDs, 0 SdLazy, 11523 SolverSat, 1000 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 8.0s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 1047 GetRequests, 262 SyntacticMatches, 11 SemanticMatches, 774 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9225 ImplicationChecksByTransitivity, 35.8s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=88occurred in iteration=15, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s AbstIntTime, 0 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, AutomataMinimizationStatistics: 0.3s AutomataMinimizationTime, 26 MinimizatonAttempts, 432 StatesRemovedByMinimization, 19 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.1s SsaConstructionTime, 0.5s SatisfiabilityAnalysisTime, 21.1s InterpolantComputationTime, 1156 NumberOfCodeBlocks, 1156 NumberOfCodeBlocksAsserted, 54 NumberOfCheckSat, 1117 ConstructedInterpolants, 183 QuantifiedInterpolants, 722272 SizeOfPredicates, 204 NumberOfNonLiveVariables, 2187 ConjunctsInSsa, 695 ConjunctsInUnsatCore, 39 InterpolantComputations, 13 PerfectInterpolantSequences, 5/492 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/openbsd_cstrncat-alloca_true-valid-memsafety_true-termination.i_svcomp-DerefFreeMemtrack-32bit-Automizer_Camel+AI_EQ.epf_AutomizerC.xml/Csv-Benchmark-0-2018-01-24_11-47-27-785.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/openbsd_cstrncat-alloca_true-valid-memsafety_true-termination.i_svcomp-DerefFreeMemtrack-32bit-Automizer_Camel+AI_EQ.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-0-2018-01-24_11-47-27-785.csv Completed graceful shutdown