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_SS.epf -i ../../../trunk/examples/svcomp/array-memsafety/cstrncat-alloca_true-valid-memsafety_true-termination.i -------------------------------------------------------------------------------- This is Ultimate 0.1.23-acfac67 [2018-01-28 21:01:44,791 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-01-28 21:01:44,793 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-01-28 21:01:44,810 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-01-28 21:01:44,810 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-01-28 21:01:44,811 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-01-28 21:01:44,815 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-01-28 21:01:44,817 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-01-28 21:01:44,819 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-01-28 21:01:44,820 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-01-28 21:01:44,821 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-01-28 21:01:44,822 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-01-28 21:01:44,823 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-01-28 21:01:44,824 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-01-28 21:01:44,825 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-01-28 21:01:44,828 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-01-28 21:01:44,830 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-01-28 21:01:44,832 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-01-28 21:01:44,833 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-01-28 21:01:44,834 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-01-28 21:01:44,836 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-01-28 21:01:44,837 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-01-28 21:01:44,837 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-01-28 21:01:44,838 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-01-28 21:01:44,839 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-01-28 21:01:44,840 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-01-28 21:01:44,840 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-01-28 21:01:44,841 INFO L177 SettingsManager]: PEA to Boogie provides no preferences, ignoring... [2018-01-28 21:01:44,841 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-01-28 21:01:44,841 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-01-28 21:01:44,842 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-01-28 21:01:44,842 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_SS.epf [2018-01-28 21:01:44,852 INFO L110 SettingsManager]: Loading preferences was successful [2018-01-28 21:01:44,852 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-01-28 21:01:44,853 INFO L131 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2018-01-28 21:01:44,853 INFO L133 SettingsManager]: * to procedures, called more than once=true [2018-01-28 21:01:44,854 INFO L131 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2018-01-28 21:01:44,854 INFO L133 SettingsManager]: * Abstract domain for RCFG-of-the-future=VPDomain [2018-01-28 21:01:44,854 INFO L133 SettingsManager]: * Use the RCFG-of-the-future interface=true [2018-01-28 21:01:44,855 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-01-28 21:01:44,855 INFO L133 SettingsManager]: * sizeof long=4 [2018-01-28 21:01:44,855 INFO L133 SettingsManager]: * Check unreachability of error function in SV-COMP mode=false [2018-01-28 21:01:44,855 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-01-28 21:01:44,855 INFO L133 SettingsManager]: * sizeof POINTER=4 [2018-01-28 21:01:44,856 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-01-28 21:01:44,856 INFO L133 SettingsManager]: * Check for the main procedure if all allocated memory was freed=true [2018-01-28 21:01:44,856 INFO L133 SettingsManager]: * Bitprecise bitfields=true [2018-01-28 21:01:44,856 INFO L133 SettingsManager]: * SV-COMP memtrack compatibility mode=true [2018-01-28 21:01:44,856 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-01-28 21:01:44,856 INFO L133 SettingsManager]: * sizeof long double=12 [2018-01-28 21:01:44,857 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-01-28 21:01:44,857 INFO L133 SettingsManager]: * Size of a code block=SingleStatement [2018-01-28 21:01:44,857 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-01-28 21:01:44,857 INFO L133 SettingsManager]: * Add additional assume for each assert=false [2018-01-28 21:01:44,857 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-01-28 21:01:44,857 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-01-28 21:01:44,858 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-01-28 21:01:44,858 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-01-28 21:01:44,858 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-01-28 21:01:44,858 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-01-28 21:01:44,858 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-01-28 21:01:44,859 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-01-28 21:01:44,859 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-01-28 21:01:44,859 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-01-28 21:01:44,860 INFO L131 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2018-01-28 21:01:44,860 INFO L133 SettingsManager]: * TransformationType=HEAP_SEPARATOR [2018-01-28 21:01:44,895 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-01-28 21:01:44,907 INFO L266 ainManager$Toolchain]: [Toolchain 1]: Parser(s) successfully initialized [2018-01-28 21:01:44,911 INFO L222 ainManager$Toolchain]: [Toolchain 1]: Toolchain data selected. [2018-01-28 21:01:44,913 INFO L271 PluginConnector]: Initializing CDTParser... [2018-01-28 21:01:44,913 INFO L276 PluginConnector]: CDTParser initialized [2018-01-28 21:01:44,914 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/array-memsafety/cstrncat-alloca_true-valid-memsafety_true-termination.i [2018-01-28 21:01:45,157 INFO L304 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-01-28 21:01:45,162 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2018-01-28 21:01:45,163 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2018-01-28 21:01:45,163 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2018-01-28 21:01:45,168 INFO L276 PluginConnector]: CACSL2BoogieTranslator initialized [2018-01-28 21:01:45,169 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 28.01 09:01:45" (1/1) ... [2018-01-28 21:01:45,171 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@51fea89f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.01 09:01:45, skipping insertion in model container [2018-01-28 21:01:45,171 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 28.01 09:01:45" (1/1) ... [2018-01-28 21:01:45,189 INFO L153 Dispatcher]: Using SV-COMP mode [2018-01-28 21:01:45,232 INFO L153 Dispatcher]: Using SV-COMP mode [2018-01-28 21:01:45,348 INFO L450 PostProcessor]: Settings: Checked method=main [2018-01-28 21:01:45,372 INFO L450 PostProcessor]: Settings: Checked method=main [2018-01-28 21:01:45,379 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.01 09:01:45 WrapperNode [2018-01-28 21:01:45,380 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2018-01-28 21:01:45,380 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-01-28 21:01:45,381 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-01-28 21:01:45,381 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-01-28 21:01:45,394 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.01 09:01:45" (1/1) ... [2018-01-28 21:01:45,394 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.01 09:01:45" (1/1) ... [2018-01-28 21:01:45,402 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.01 09:01:45" (1/1) ... [2018-01-28 21:01:45,402 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.01 09:01:45" (1/1) ... [2018-01-28 21:01:45,408 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.01 09:01:45" (1/1) ... [2018-01-28 21:01:45,416 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.01 09:01:45" (1/1) ... [2018-01-28 21:01:45,418 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.01 09:01:45" (1/1) ... [2018-01-28 21:01:45,420 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-01-28 21:01:45,421 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-01-28 21:01:45,421 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-01-28 21:01:45,421 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-01-28 21:01:45,422 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.01 09:01:45" (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-28 21:01:45,473 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2018-01-28 21:01:45,473 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-01-28 21:01:45,473 INFO L136 BoogieDeclarations]: Found implementation of procedure cstrncat [2018-01-28 21:01:45,473 INFO L136 BoogieDeclarations]: Found implementation of procedure main [2018-01-28 21:01:45,473 INFO L128 BoogieDeclarations]: Found specification of procedure write~int [2018-01-28 21:01:45,473 INFO L128 BoogieDeclarations]: Found specification of procedure read~int [2018-01-28 21:01:45,473 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.free [2018-01-28 21:01:45,474 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2018-01-28 21:01:45,474 INFO L128 BoogieDeclarations]: Found specification of procedure #Ultimate.alloc [2018-01-28 21:01:45,474 INFO L128 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2018-01-28 21:01:45,474 INFO L128 BoogieDeclarations]: Found specification of procedure cstrncat [2018-01-28 21:01:45,474 INFO L128 BoogieDeclarations]: Found specification of procedure main [2018-01-28 21:01:45,474 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2018-01-28 21:01:45,475 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-01-28 21:01:45,753 INFO L257 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-01-28 21:01:45,754 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 28.01 09:01:45 BoogieIcfgContainer [2018-01-28 21:01:45,754 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-01-28 21:01:45,754 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-01-28 21:01:45,754 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-01-28 21:01:45,757 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-01-28 21:01:45,758 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 28.01 09:01:45" (1/3) ... [2018-01-28 21:01:45,758 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@295046da and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 28.01 09:01:45, skipping insertion in model container [2018-01-28 21:01:45,759 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.01 09:01:45" (2/3) ... [2018-01-28 21:01:45,759 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@295046da and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 28.01 09:01:45, skipping insertion in model container [2018-01-28 21:01:45,759 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 28.01 09:01:45" (3/3) ... [2018-01-28 21:01:45,761 INFO L107 eAbstractionObserver]: Analyzing ICFG cstrncat-alloca_true-valid-memsafety_true-termination.i [2018-01-28 21:01:45,769 INFO L128 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-01-28 21:01:45,777 INFO L140 ceAbstractionStarter]: Appying trace abstraction to program that has 15 error locations. [2018-01-28 21:01:45,834 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-28 21:01:45,834 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-28 21:01:45,834 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-28 21:01:45,834 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-28 21:01:45,835 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-28 21:01:45,835 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-28 21:01:45,835 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-28 21:01:45,835 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-01-28 21:01:45,836 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-28 21:01:45,855 INFO L276 IsEmpty]: Start isEmpty. Operand 96 states. [2018-01-28 21:01:45,861 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2018-01-28 21:01:45,862 INFO L322 BasicCegarLoop]: Found error trace [2018-01-28 21:01:45,863 INFO L330 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-28 21:01:45,863 INFO L371 AbstractCegarLoop]: === Iteration 1 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-28 21:01:45,868 INFO L82 PathProgramCache]: Analyzing trace with hash 533934611, now seen corresponding path program 1 times [2018-01-28 21:01:45,870 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-28 21:01:45,871 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-28 21:01:45,910 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-28 21:01:45,910 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-28 21:01:45,910 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-28 21:01:45,957 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-28 21:01:45,965 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-28 21:01:46,046 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-28 21:01:46,050 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-28 21:01:46,050 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-01-28 21:01:46,052 INFO L409 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-01-28 21:01:46,064 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-01-28 21:01:46,065 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-28 21:01:46,066 INFO L87 Difference]: Start difference. First operand 96 states. Second operand 3 states. [2018-01-28 21:01:46,245 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-28 21:01:46,245 INFO L93 Difference]: Finished difference Result 145 states and 158 transitions. [2018-01-28 21:01:46,246 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-01-28 21:01:46,247 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 21 [2018-01-28 21:01:46,248 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-28 21:01:46,260 INFO L225 Difference]: With dead ends: 145 [2018-01-28 21:01:46,260 INFO L226 Difference]: Without dead ends: 92 [2018-01-28 21:01:46,264 INFO L533 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-28 21:01:46,282 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 92 states. [2018-01-28 21:01:46,303 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 92 to 92. [2018-01-28 21:01:46,304 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 92 states. [2018-01-28 21:01:46,307 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 92 states to 92 states and 98 transitions. [2018-01-28 21:01:46,308 INFO L78 Accepts]: Start accepts. Automaton has 92 states and 98 transitions. Word has length 21 [2018-01-28 21:01:46,309 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-28 21:01:46,309 INFO L432 AbstractCegarLoop]: Abstraction has 92 states and 98 transitions. [2018-01-28 21:01:46,309 INFO L433 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-01-28 21:01:46,309 INFO L276 IsEmpty]: Start isEmpty. Operand 92 states and 98 transitions. [2018-01-28 21:01:46,310 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2018-01-28 21:01:46,310 INFO L322 BasicCegarLoop]: Found error trace [2018-01-28 21:01:46,310 INFO L330 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-28 21:01:46,310 INFO L371 AbstractCegarLoop]: === Iteration 2 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-28 21:01:46,311 INFO L82 PathProgramCache]: Analyzing trace with hash -2054226453, now seen corresponding path program 1 times [2018-01-28 21:01:46,311 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-28 21:01:46,311 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-28 21:01:46,312 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-28 21:01:46,312 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-28 21:01:46,312 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-28 21:01:46,334 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-28 21:01:46,335 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-28 21:01:46,410 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-28 21:01:46,410 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-28 21:01:46,410 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-01-28 21:01:46,411 INFO L409 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-01-28 21:01:46,411 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-01-28 21:01:46,412 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-01-28 21:01:46,412 INFO L87 Difference]: Start difference. First operand 92 states and 98 transitions. Second operand 4 states. [2018-01-28 21:01:46,476 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-28 21:01:46,476 INFO L93 Difference]: Finished difference Result 92 states and 98 transitions. [2018-01-28 21:01:46,477 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-01-28 21:01:46,477 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 24 [2018-01-28 21:01:46,477 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-28 21:01:46,478 INFO L225 Difference]: With dead ends: 92 [2018-01-28 21:01:46,478 INFO L226 Difference]: Without dead ends: 91 [2018-01-28 21:01:46,479 INFO L533 BasicCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-01-28 21:01:46,479 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 91 states. [2018-01-28 21:01:46,484 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 91 to 91. [2018-01-28 21:01:46,484 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 91 states. [2018-01-28 21:01:46,485 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 91 states to 91 states and 97 transitions. [2018-01-28 21:01:46,485 INFO L78 Accepts]: Start accepts. Automaton has 91 states and 97 transitions. Word has length 24 [2018-01-28 21:01:46,486 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-28 21:01:46,486 INFO L432 AbstractCegarLoop]: Abstraction has 91 states and 97 transitions. [2018-01-28 21:01:46,486 INFO L433 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-01-28 21:01:46,486 INFO L276 IsEmpty]: Start isEmpty. Operand 91 states and 97 transitions. [2018-01-28 21:01:46,486 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2018-01-28 21:01:46,487 INFO L322 BasicCegarLoop]: Found error trace [2018-01-28 21:01:46,487 INFO L330 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-28 21:01:46,487 INFO L371 AbstractCegarLoop]: === Iteration 3 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-28 21:01:46,487 INFO L82 PathProgramCache]: Analyzing trace with hash -2054226452, now seen corresponding path program 1 times [2018-01-28 21:01:46,487 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-28 21:01:46,487 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-28 21:01:46,488 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-28 21:01:46,488 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-28 21:01:46,488 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-28 21:01:46,505 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-28 21:01:46,506 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-28 21:01:46,647 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-28 21:01:46,647 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-28 21:01:46,647 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2018-01-28 21:01:46,648 INFO L409 AbstractCegarLoop]: Interpolant automaton has 8 states [2018-01-28 21:01:46,648 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2018-01-28 21:01:46,648 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=38, Unknown=0, NotChecked=0, Total=56 [2018-01-28 21:01:46,648 INFO L87 Difference]: Start difference. First operand 91 states and 97 transitions. Second operand 8 states. [2018-01-28 21:01:46,815 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-28 21:01:46,815 INFO L93 Difference]: Finished difference Result 91 states and 97 transitions. [2018-01-28 21:01:46,816 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-01-28 21:01:46,816 INFO L78 Accepts]: Start accepts. Automaton has 8 states. Word has length 24 [2018-01-28 21:01:46,816 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-28 21:01:46,817 INFO L225 Difference]: With dead ends: 91 [2018-01-28 21:01:46,817 INFO L226 Difference]: Without dead ends: 90 [2018-01-28 21:01:46,818 INFO L533 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-28 21:01:46,818 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 90 states. [2018-01-28 21:01:46,824 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 90 to 90. [2018-01-28 21:01:46,824 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 90 states. [2018-01-28 21:01:46,826 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 90 states to 90 states and 96 transitions. [2018-01-28 21:01:46,827 INFO L78 Accepts]: Start accepts. Automaton has 90 states and 96 transitions. Word has length 24 [2018-01-28 21:01:46,827 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-28 21:01:46,827 INFO L432 AbstractCegarLoop]: Abstraction has 90 states and 96 transitions. [2018-01-28 21:01:46,827 INFO L433 AbstractCegarLoop]: Interpolant automaton has 8 states. [2018-01-28 21:01:46,827 INFO L276 IsEmpty]: Start isEmpty. Operand 90 states and 96 transitions. [2018-01-28 21:01:46,828 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2018-01-28 21:01:46,828 INFO L322 BasicCegarLoop]: Found error trace [2018-01-28 21:01:46,828 INFO L330 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-28 21:01:46,828 INFO L371 AbstractCegarLoop]: === Iteration 4 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-28 21:01:46,829 INFO L82 PathProgramCache]: Analyzing trace with hash 743489415, now seen corresponding path program 1 times [2018-01-28 21:01:46,829 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-28 21:01:46,829 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-28 21:01:46,830 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-28 21:01:46,830 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-28 21:01:46,830 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-28 21:01:46,842 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-28 21:01:46,843 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-28 21:01:46,882 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-28 21:01:46,883 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-28 21:01:46,883 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-01-28 21:01:46,883 INFO L409 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-01-28 21:01:46,884 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-01-28 21:01:46,884 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-01-28 21:01:46,884 INFO L87 Difference]: Start difference. First operand 90 states and 96 transitions. Second operand 4 states. [2018-01-28 21:01:46,938 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-28 21:01:46,938 INFO L93 Difference]: Finished difference Result 90 states and 96 transitions. [2018-01-28 21:01:46,938 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-01-28 21:01:46,938 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 25 [2018-01-28 21:01:46,939 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-28 21:01:46,940 INFO L225 Difference]: With dead ends: 90 [2018-01-28 21:01:46,940 INFO L226 Difference]: Without dead ends: 89 [2018-01-28 21:01:46,940 INFO L533 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-28 21:01:46,941 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 89 states. [2018-01-28 21:01:46,947 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 89 to 89. [2018-01-28 21:01:46,947 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 89 states. [2018-01-28 21:01:46,949 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 89 states to 89 states and 95 transitions. [2018-01-28 21:01:46,949 INFO L78 Accepts]: Start accepts. Automaton has 89 states and 95 transitions. Word has length 25 [2018-01-28 21:01:46,949 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-28 21:01:46,949 INFO L432 AbstractCegarLoop]: Abstraction has 89 states and 95 transitions. [2018-01-28 21:01:46,950 INFO L433 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-01-28 21:01:46,950 INFO L276 IsEmpty]: Start isEmpty. Operand 89 states and 95 transitions. [2018-01-28 21:01:46,950 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2018-01-28 21:01:46,951 INFO L322 BasicCegarLoop]: Found error trace [2018-01-28 21:01:46,951 INFO L330 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-28 21:01:46,951 INFO L371 AbstractCegarLoop]: === Iteration 5 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-28 21:01:46,951 INFO L82 PathProgramCache]: Analyzing trace with hash 743489416, now seen corresponding path program 1 times [2018-01-28 21:01:46,951 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-28 21:01:46,951 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-28 21:01:46,953 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-28 21:01:46,953 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-28 21:01:46,953 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-28 21:01:46,967 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-28 21:01:46,968 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-28 21:01:47,077 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-28 21:01:47,078 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-28 21:01:47,078 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-01-28 21:01:47,078 INFO L409 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-01-28 21:01:47,078 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-01-28 21:01:47,078 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-01-28 21:01:47,079 INFO L87 Difference]: Start difference. First operand 89 states and 95 transitions. Second operand 5 states. [2018-01-28 21:01:47,159 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-28 21:01:47,159 INFO L93 Difference]: Finished difference Result 89 states and 95 transitions. [2018-01-28 21:01:47,159 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-01-28 21:01:47,159 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 25 [2018-01-28 21:01:47,160 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-28 21:01:47,160 INFO L225 Difference]: With dead ends: 89 [2018-01-28 21:01:47,161 INFO L226 Difference]: Without dead ends: 88 [2018-01-28 21:01:47,161 INFO L533 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-28 21:01:47,161 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 88 states. [2018-01-28 21:01:47,167 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 88 to 88. [2018-01-28 21:01:47,174 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 88 states. [2018-01-28 21:01:47,176 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 88 states to 88 states and 94 transitions. [2018-01-28 21:01:47,176 INFO L78 Accepts]: Start accepts. Automaton has 88 states and 94 transitions. Word has length 25 [2018-01-28 21:01:47,176 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-28 21:01:47,176 INFO L432 AbstractCegarLoop]: Abstraction has 88 states and 94 transitions. [2018-01-28 21:01:47,176 INFO L433 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-01-28 21:01:47,176 INFO L276 IsEmpty]: Start isEmpty. Operand 88 states and 94 transitions. [2018-01-28 21:01:47,177 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2018-01-28 21:01:47,177 INFO L322 BasicCegarLoop]: Found error trace [2018-01-28 21:01:47,178 INFO L330 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-28 21:01:47,178 INFO L371 AbstractCegarLoop]: === Iteration 6 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-28 21:01:47,178 INFO L82 PathProgramCache]: Analyzing trace with hash 441118832, now seen corresponding path program 1 times [2018-01-28 21:01:47,178 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-28 21:01:47,178 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-28 21:01:47,179 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-28 21:01:47,179 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-28 21:01:47,179 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-28 21:01:47,192 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-28 21:01:47,193 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-28 21:01:47,266 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-28 21:01:47,267 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-28 21:01:47,267 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-01-28 21:01:47,267 INFO L409 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-01-28 21:01:47,267 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-01-28 21:01:47,268 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2018-01-28 21:01:47,268 INFO L87 Difference]: Start difference. First operand 88 states and 94 transitions. Second operand 6 states. [2018-01-28 21:01:47,359 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-28 21:01:47,359 INFO L93 Difference]: Finished difference Result 118 states and 126 transitions. [2018-01-28 21:01:47,359 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-01-28 21:01:47,360 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 32 [2018-01-28 21:01:47,360 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-28 21:01:47,361 INFO L225 Difference]: With dead ends: 118 [2018-01-28 21:01:47,361 INFO L226 Difference]: Without dead ends: 114 [2018-01-28 21:01:47,361 INFO L533 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-28 21:01:47,361 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 114 states. [2018-01-28 21:01:47,367 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 114 to 101. [2018-01-28 21:01:47,367 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 101 states. [2018-01-28 21:01:47,368 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 101 states to 101 states and 114 transitions. [2018-01-28 21:01:47,369 INFO L78 Accepts]: Start accepts. Automaton has 101 states and 114 transitions. Word has length 32 [2018-01-28 21:01:47,369 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-28 21:01:47,369 INFO L432 AbstractCegarLoop]: Abstraction has 101 states and 114 transitions. [2018-01-28 21:01:47,369 INFO L433 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-01-28 21:01:47,370 INFO L276 IsEmpty]: Start isEmpty. Operand 101 states and 114 transitions. [2018-01-28 21:01:47,370 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2018-01-28 21:01:47,371 INFO L322 BasicCegarLoop]: Found error trace [2018-01-28 21:01:47,371 INFO L330 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-28 21:01:47,371 INFO L371 AbstractCegarLoop]: === Iteration 7 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-28 21:01:47,371 INFO L82 PathProgramCache]: Analyzing trace with hash 441118833, now seen corresponding path program 1 times [2018-01-28 21:01:47,372 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-28 21:01:47,372 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-28 21:01:47,373 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-28 21:01:47,373 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-28 21:01:47,373 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-28 21:01:47,388 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-28 21:01:47,388 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-28 21:01:47,545 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-28 21:01:47,545 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-28 21:01:47,545 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2018-01-28 21:01:47,546 INFO L409 AbstractCegarLoop]: Interpolant automaton has 10 states [2018-01-28 21:01:47,546 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2018-01-28 21:01:47,546 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=71, Unknown=0, NotChecked=0, Total=90 [2018-01-28 21:01:47,547 INFO L87 Difference]: Start difference. First operand 101 states and 114 transitions. Second operand 10 states. [2018-01-28 21:01:47,853 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-28 21:01:47,854 INFO L93 Difference]: Finished difference Result 140 states and 156 transitions. [2018-01-28 21:01:47,854 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-01-28 21:01:47,854 INFO L78 Accepts]: Start accepts. Automaton has 10 states. Word has length 32 [2018-01-28 21:01:47,855 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-28 21:01:47,858 INFO L225 Difference]: With dead ends: 140 [2018-01-28 21:01:47,858 INFO L226 Difference]: Without dead ends: 136 [2018-01-28 21:01:47,859 INFO L533 BasicCegarLoop]: 0 DeclaredPredicates, 16 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 25 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=65, Invalid=207, Unknown=0, NotChecked=0, Total=272 [2018-01-28 21:01:47,859 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 136 states. [2018-01-28 21:01:47,870 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 136 to 119. [2018-01-28 21:01:47,870 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 119 states. [2018-01-28 21:01:47,874 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 119 states to 119 states and 137 transitions. [2018-01-28 21:01:47,875 INFO L78 Accepts]: Start accepts. Automaton has 119 states and 137 transitions. Word has length 32 [2018-01-28 21:01:47,875 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-28 21:01:47,875 INFO L432 AbstractCegarLoop]: Abstraction has 119 states and 137 transitions. [2018-01-28 21:01:47,875 INFO L433 AbstractCegarLoop]: Interpolant automaton has 10 states. [2018-01-28 21:01:47,875 INFO L276 IsEmpty]: Start isEmpty. Operand 119 states and 137 transitions. [2018-01-28 21:01:47,877 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2018-01-28 21:01:47,877 INFO L322 BasicCegarLoop]: Found error trace [2018-01-28 21:01:47,877 INFO L330 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, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-28 21:01:47,877 INFO L371 AbstractCegarLoop]: === Iteration 8 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-28 21:01:47,877 INFO L82 PathProgramCache]: Analyzing trace with hash 906112675, now seen corresponding path program 1 times [2018-01-28 21:01:47,877 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-28 21:01:47,878 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-28 21:01:47,879 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-28 21:01:47,879 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-28 21:01:47,879 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-28 21:01:47,891 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-28 21:01:47,892 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-28 21:01:47,936 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-01-28 21:01:47,936 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-28 21:01:47,936 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2018-01-28 21:01:47,937 INFO L409 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-01-28 21:01:47,937 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-01-28 21:01:47,937 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2018-01-28 21:01:47,937 INFO L87 Difference]: Start difference. First operand 119 states and 137 transitions. Second operand 7 states. [2018-01-28 21:01:48,113 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-28 21:01:48,114 INFO L93 Difference]: Finished difference Result 131 states and 145 transitions. [2018-01-28 21:01:48,114 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-01-28 21:01:48,114 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 39 [2018-01-28 21:01:48,114 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-28 21:01:48,115 INFO L225 Difference]: With dead ends: 131 [2018-01-28 21:01:48,115 INFO L226 Difference]: Without dead ends: 130 [2018-01-28 21:01:48,115 INFO L533 BasicCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 2 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-28 21:01:48,116 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 130 states. [2018-01-28 21:01:48,122 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 130 to 118. [2018-01-28 21:01:48,122 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 118 states. [2018-01-28 21:01:48,123 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 118 states to 118 states and 136 transitions. [2018-01-28 21:01:48,123 INFO L78 Accepts]: Start accepts. Automaton has 118 states and 136 transitions. Word has length 39 [2018-01-28 21:01:48,124 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-28 21:01:48,124 INFO L432 AbstractCegarLoop]: Abstraction has 118 states and 136 transitions. [2018-01-28 21:01:48,124 INFO L433 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-01-28 21:01:48,124 INFO L276 IsEmpty]: Start isEmpty. Operand 118 states and 136 transitions. [2018-01-28 21:01:48,125 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2018-01-28 21:01:48,125 INFO L322 BasicCegarLoop]: Found error trace [2018-01-28 21:01:48,125 INFO L330 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, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-28 21:01:48,126 INFO L371 AbstractCegarLoop]: === Iteration 9 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-28 21:01:48,126 INFO L82 PathProgramCache]: Analyzing trace with hash 906112676, now seen corresponding path program 1 times [2018-01-28 21:01:48,126 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-28 21:01:48,126 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-28 21:01:48,127 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-28 21:01:48,127 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-28 21:01:48,127 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-28 21:01:48,140 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-28 21:01:48,141 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-28 21:01:48,293 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-28 21:01:48,294 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-28 21:01:48,294 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-28 21:01:48,299 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-28 21:01:48,325 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-28 21:01:48,336 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-28 21:01:48,419 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-28 21:01:48,421 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-28 21:01:48,430 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-28 21:01:48,431 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-28 21:01:48,439 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-28 21:01:48,439 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:24, output treesize:19 [2018-01-28 21:01:48,479 INFO L700 Elim1Store]: detected not equals via solver [2018-01-28 21:01:48,480 INFO L700 Elim1Store]: detected not equals via solver [2018-01-28 21:01:48,483 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-28 21:01:48,484 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-28 21:01:48,503 INFO L700 Elim1Store]: detected not equals via solver [2018-01-28 21:01:48,504 INFO L700 Elim1Store]: detected not equals via solver [2018-01-28 21:01:48,505 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-28 21:01:48,505 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-28 21:01:48,515 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-28 21:01:48,515 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:30, output treesize:18 [2018-01-28 21:01:48,707 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-28 21:01:48,727 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-28 21:01:48,727 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 24 [2018-01-28 21:01:48,728 INFO L409 AbstractCegarLoop]: Interpolant automaton has 25 states [2018-01-28 21:01:48,728 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2018-01-28 21:01:48,728 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=68, Invalid=532, Unknown=0, NotChecked=0, Total=600 [2018-01-28 21:01:48,728 INFO L87 Difference]: Start difference. First operand 118 states and 136 transitions. Second operand 25 states. [2018-01-28 21:01:49,491 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-28 21:01:49,491 INFO L93 Difference]: Finished difference Result 177 states and 197 transitions. [2018-01-28 21:01:49,491 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2018-01-28 21:01:49,491 INFO L78 Accepts]: Start accepts. Automaton has 25 states. Word has length 39 [2018-01-28 21:01:49,492 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-28 21:01:49,493 INFO L225 Difference]: With dead ends: 177 [2018-01-28 21:01:49,493 INFO L226 Difference]: Without dead ends: 173 [2018-01-28 21:01:49,494 INFO L533 BasicCegarLoop]: 0 DeclaredPredicates, 62 GetRequests, 28 SyntacticMatches, 0 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 270 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=192, Invalid=1068, Unknown=0, NotChecked=0, Total=1260 [2018-01-28 21:01:49,495 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 173 states. [2018-01-28 21:01:49,506 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 173 to 125. [2018-01-28 21:01:49,506 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 125 states. [2018-01-28 21:01:49,508 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 125 states to 125 states and 144 transitions. [2018-01-28 21:01:49,508 INFO L78 Accepts]: Start accepts. Automaton has 125 states and 144 transitions. Word has length 39 [2018-01-28 21:01:49,508 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-28 21:01:49,508 INFO L432 AbstractCegarLoop]: Abstraction has 125 states and 144 transitions. [2018-01-28 21:01:49,509 INFO L433 AbstractCegarLoop]: Interpolant automaton has 25 states. [2018-01-28 21:01:49,509 INFO L276 IsEmpty]: Start isEmpty. Operand 125 states and 144 transitions. [2018-01-28 21:01:49,510 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2018-01-28 21:01:49,510 INFO L322 BasicCegarLoop]: Found error trace [2018-01-28 21:01:49,510 INFO L330 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-28 21:01:49,511 INFO L371 AbstractCegarLoop]: === Iteration 10 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-28 21:01:49,511 INFO L82 PathProgramCache]: Analyzing trace with hash -1038587179, now seen corresponding path program 1 times [2018-01-28 21:01:49,511 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-28 21:01:49,511 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-28 21:01:49,512 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-28 21:01:49,512 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-28 21:01:49,513 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-28 21:01:49,525 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-28 21:01:49,526 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-28 21:01:49,579 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-28 21:01:49,580 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-28 21:01:49,580 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-01-28 21:01:49,580 INFO L409 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-01-28 21:01:49,581 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-01-28 21:01:49,581 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2018-01-28 21:01:49,581 INFO L87 Difference]: Start difference. First operand 125 states and 144 transitions. Second operand 6 states. [2018-01-28 21:01:49,684 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-28 21:01:49,685 INFO L93 Difference]: Finished difference Result 130 states and 151 transitions. [2018-01-28 21:01:49,686 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-01-28 21:01:49,686 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 40 [2018-01-28 21:01:49,686 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-28 21:01:49,687 INFO L225 Difference]: With dead ends: 130 [2018-01-28 21:01:49,687 INFO L226 Difference]: Without dead ends: 129 [2018-01-28 21:01:49,688 INFO L533 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-28 21:01:49,688 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 129 states. [2018-01-28 21:01:49,695 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 129 to 124. [2018-01-28 21:01:49,696 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 124 states. [2018-01-28 21:01:49,697 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 124 states to 124 states and 141 transitions. [2018-01-28 21:01:49,697 INFO L78 Accepts]: Start accepts. Automaton has 124 states and 141 transitions. Word has length 40 [2018-01-28 21:01:49,697 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-28 21:01:49,697 INFO L432 AbstractCegarLoop]: Abstraction has 124 states and 141 transitions. [2018-01-28 21:01:49,697 INFO L433 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-01-28 21:01:49,697 INFO L276 IsEmpty]: Start isEmpty. Operand 124 states and 141 transitions. [2018-01-28 21:01:49,698 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2018-01-28 21:01:49,699 INFO L322 BasicCegarLoop]: Found error trace [2018-01-28 21:01:49,699 INFO L330 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-28 21:01:49,699 INFO L371 AbstractCegarLoop]: === Iteration 11 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-28 21:01:49,699 INFO L82 PathProgramCache]: Analyzing trace with hash -1038587178, now seen corresponding path program 1 times [2018-01-28 21:01:49,699 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-28 21:01:49,699 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-28 21:01:49,700 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-28 21:01:49,700 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-28 21:01:49,700 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-28 21:01:49,711 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-28 21:01:49,712 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-28 21:01:49,856 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-28 21:01:49,857 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-28 21:01:49,857 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2018-01-28 21:01:49,857 INFO L409 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-01-28 21:01:49,857 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-01-28 21:01:49,858 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=54, Unknown=0, NotChecked=0, Total=72 [2018-01-28 21:01:49,858 INFO L87 Difference]: Start difference. First operand 124 states and 141 transitions. Second operand 9 states. [2018-01-28 21:01:50,001 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-28 21:01:50,001 INFO L93 Difference]: Finished difference Result 175 states and 200 transitions. [2018-01-28 21:01:50,001 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-01-28 21:01:50,001 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 40 [2018-01-28 21:01:50,001 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-28 21:01:50,002 INFO L225 Difference]: With dead ends: 175 [2018-01-28 21:01:50,002 INFO L226 Difference]: Without dead ends: 174 [2018-01-28 21:01:50,003 INFO L533 BasicCegarLoop]: 0 DeclaredPredicates, 12 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 22 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=39, Invalid=117, Unknown=0, NotChecked=0, Total=156 [2018-01-28 21:01:50,003 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 174 states. [2018-01-28 21:01:50,008 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 174 to 142. [2018-01-28 21:01:50,008 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 142 states. [2018-01-28 21:01:50,008 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 142 states to 142 states and 161 transitions. [2018-01-28 21:01:50,009 INFO L78 Accepts]: Start accepts. Automaton has 142 states and 161 transitions. Word has length 40 [2018-01-28 21:01:50,009 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-28 21:01:50,009 INFO L432 AbstractCegarLoop]: Abstraction has 142 states and 161 transitions. [2018-01-28 21:01:50,009 INFO L433 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-01-28 21:01:50,009 INFO L276 IsEmpty]: Start isEmpty. Operand 142 states and 161 transitions. [2018-01-28 21:01:50,010 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2018-01-28 21:01:50,010 INFO L322 BasicCegarLoop]: Found error trace [2018-01-28 21:01:50,010 INFO L330 BasicCegarLoop]: trace histogram [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, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-28 21:01:50,010 INFO L371 AbstractCegarLoop]: === Iteration 12 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-28 21:01:50,011 INFO L82 PathProgramCache]: Analyzing trace with hash 153428241, now seen corresponding path program 2 times [2018-01-28 21:01:50,011 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-28 21:01:50,011 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-28 21:01:50,012 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-28 21:01:50,012 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-28 21:01:50,012 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-28 21:01:50,027 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-28 21:01:50,028 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-28 21:01:50,419 INFO L134 CoverageAnalysis]: Checked inductivity of 11 backedges. 0 proven. 11 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-28 21:01:50,420 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-28 21:01:50,420 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-28 21:01:50,426 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-01-28 21:01:50,452 INFO L201 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-28 21:01:50,458 INFO L214 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-28 21:01:50,460 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-28 21:01:50,465 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-28 21:01:50,545 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-28 21:01:50,546 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-28 21:01:50,554 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-28 21:01:50,555 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-28 21:01:50,561 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-28 21:01:50,561 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:27, output treesize:25 [2018-01-28 21:01:50,620 INFO L700 Elim1Store]: detected not equals via solver [2018-01-28 21:01:50,634 INFO L700 Elim1Store]: detected not equals via solver [2018-01-28 21:01:50,635 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-28 21:01:50,635 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-28 21:01:50,646 INFO L700 Elim1Store]: detected not equals via solver [2018-01-28 21:01:50,646 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-28 21:01:50,647 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-28 21:01:50,657 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-28 21:01:50,657 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:39, output treesize:28 [2018-01-28 21:01:50,719 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-28 21:01:50,721 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-28 21:01:50,721 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-28 21:01:50,722 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-28 21:01:50,732 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-28 21:01:50,732 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:44, output treesize:40 [2018-01-28 21:01:50,767 INFO L700 Elim1Store]: detected not equals via solver [2018-01-28 21:01:50,771 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-28 21:01:50,773 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-28 21:01:50,774 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-28 21:01:50,778 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-28 21:01:50,786 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-28 21:01:50,787 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:51, output treesize:47 [2018-01-28 21:01:50,981 INFO L700 Elim1Store]: detected not equals via solver [2018-01-28 21:01:50,983 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 33 treesize of output 31 [2018-01-28 21:01:50,999 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 1 case distinctions, treesize of input 18 treesize of output 19 [2018-01-28 21:01:51,000 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-28 21:01:51,011 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-28 21:01:51,012 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-28 21:01:51,015 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-28 21:01:51,027 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: 3 dim-0 vars, and 2 xjuncts. [2018-01-28 21:01:51,027 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 3 variables, input treesize:53, output treesize:69 [2018-01-28 21:01:51,368 INFO L134 CoverageAnalysis]: Checked inductivity of 11 backedges. 0 proven. 11 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-28 21:01:51,388 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-28 21:01:51,388 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 19] total 34 [2018-01-28 21:01:51,389 INFO L409 AbstractCegarLoop]: Interpolant automaton has 35 states [2018-01-28 21:01:51,389 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 35 interpolants. [2018-01-28 21:01:51,389 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=109, Invalid=1081, Unknown=0, NotChecked=0, Total=1190 [2018-01-28 21:01:51,390 INFO L87 Difference]: Start difference. First operand 142 states and 161 transitions. Second operand 35 states. [2018-01-28 21:01:51,936 WARN L143 SmtUtils]: Spent 311ms on a formula simplification that was a NOOP. DAG size: 55 [2018-01-28 21:01:53,620 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-28 21:01:53,621 INFO L93 Difference]: Finished difference Result 344 states and 380 transitions. [2018-01-28 21:01:53,621 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2018-01-28 21:01:53,621 INFO L78 Accepts]: Start accepts. Automaton has 35 states. Word has length 46 [2018-01-28 21:01:53,621 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-28 21:01:53,623 INFO L225 Difference]: With dead ends: 344 [2018-01-28 21:01:53,623 INFO L226 Difference]: Without dead ends: 340 [2018-01-28 21:01:53,624 INFO L533 BasicCegarLoop]: 0 DeclaredPredicates, 87 GetRequests, 28 SyntacticMatches, 1 SemanticMatches, 58 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 785 ImplicationChecksByTransitivity, 2.3s TimeCoverageRelationStatistics Valid=452, Invalid=3088, Unknown=0, NotChecked=0, Total=3540 [2018-01-28 21:01:53,625 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 340 states. [2018-01-28 21:01:53,633 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 340 to 149. [2018-01-28 21:01:53,633 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 149 states. [2018-01-28 21:01:53,634 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 149 states to 149 states and 169 transitions. [2018-01-28 21:01:53,634 INFO L78 Accepts]: Start accepts. Automaton has 149 states and 169 transitions. Word has length 46 [2018-01-28 21:01:53,634 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-28 21:01:53,635 INFO L432 AbstractCegarLoop]: Abstraction has 149 states and 169 transitions. [2018-01-28 21:01:53,635 INFO L433 AbstractCegarLoop]: Interpolant automaton has 35 states. [2018-01-28 21:01:53,635 INFO L276 IsEmpty]: Start isEmpty. Operand 149 states and 169 transitions. [2018-01-28 21:01:53,636 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 54 [2018-01-28 21:01:53,636 INFO L322 BasicCegarLoop]: Found error trace [2018-01-28 21:01:53,636 INFO L330 BasicCegarLoop]: trace histogram [4, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 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-28 21:01:53,636 INFO L371 AbstractCegarLoop]: === Iteration 13 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-28 21:01:53,636 INFO L82 PathProgramCache]: Analyzing trace with hash -485619196, now seen corresponding path program 3 times [2018-01-28 21:01:53,636 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-28 21:01:53,637 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-28 21:01:53,637 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-28 21:01:53,638 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-01-28 21:01:53,638 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-28 21:01:53,655 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-28 21:01:53,656 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-28 21:01:54,307 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 0 proven. 27 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-28 21:01:54,307 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-28 21:01:54,307 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-28 21:01:54,314 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-01-28 21:01:54,328 INFO L254 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued a check-sat command [2018-01-28 21:01:54,332 INFO L254 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued a check-sat command [2018-01-28 21:01:54,335 INFO L254 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued a check-sat command [2018-01-28 21:01:54,338 INFO L254 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued a check-sat command [2018-01-28 21:01:54,339 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-28 21:01:54,344 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-28 21:01:54,406 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-28 21:01:54,407 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-28 21:01:54,414 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-28 21:01:54,414 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-28 21:01:54,420 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-28 21:01:54,420 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:27, output treesize:25 [2018-01-28 21:01:54,477 INFO L700 Elim1Store]: detected not equals via solver [2018-01-28 21:01:54,478 INFO L700 Elim1Store]: detected not equals via solver [2018-01-28 21:01:54,478 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-28 21:01:54,478 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-28 21:01:54,488 INFO L700 Elim1Store]: detected not equals via solver [2018-01-28 21:01:54,489 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-28 21:01:54,489 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-28 21:01:54,499 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-28 21:01:54,499 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:39, output treesize:28 [2018-01-28 21:01:54,561 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-28 21:01:54,563 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-28 21:01:54,563 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-28 21:01:54,564 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-28 21:01:54,573 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-28 21:01:54,573 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:44, output treesize:40 [2018-01-28 21:01:54,613 INFO L700 Elim1Store]: detected not equals via solver [2018-01-28 21:01:54,616 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-28 21:01:54,618 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 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-28 21:01:54,618 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-28 21:01:54,622 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-28 21:01:54,630 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-28 21:01:54,630 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:51, output treesize:47 [2018-01-28 21:01:55,011 INFO L700 Elim1Store]: detected not equals via solver [2018-01-28 21:01:55,012 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-28 21:01:55,024 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 2 disjoint index pairs (out of 3 index pairs), introduced 1 new quantified variables, introduced 2 case distinctions, treesize of input 24 treesize of output 39 [2018-01-28 21:01:55,025 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 3 xjuncts. [2018-01-28 21:01:55,042 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 9 treesize of output 1 [2018-01-28 21:01:55,043 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-28 21:01:55,052 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-28 21:01:55,071 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-2 vars, End of recursive call: 7 dim-0 vars, and 2 xjuncts. [2018-01-28 21:01:55,071 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 4 variables, input treesize:66, output treesize:227 [2018-01-28 21:01:55,464 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 0 proven. 27 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-28 21:01:55,484 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-28 21:01:55,484 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 24] total 44 [2018-01-28 21:01:55,484 INFO L409 AbstractCegarLoop]: Interpolant automaton has 45 states [2018-01-28 21:01:55,485 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 45 interpolants. [2018-01-28 21:01:55,485 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=157, Invalid=1823, Unknown=0, NotChecked=0, Total=1980 [2018-01-28 21:01:55,485 INFO L87 Difference]: Start difference. First operand 149 states and 169 transitions. Second operand 45 states. [2018-01-28 21:01:58,440 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-28 21:01:58,441 INFO L93 Difference]: Finished difference Result 349 states and 387 transitions. [2018-01-28 21:01:58,441 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 36 states. [2018-01-28 21:01:58,441 INFO L78 Accepts]: Start accepts. Automaton has 45 states. Word has length 53 [2018-01-28 21:01:58,441 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-28 21:01:58,443 INFO L225 Difference]: With dead ends: 349 [2018-01-28 21:01:58,443 INFO L226 Difference]: Without dead ends: 345 [2018-01-28 21:01:58,445 INFO L533 BasicCegarLoop]: 0 DeclaredPredicates, 101 GetRequests, 30 SyntacticMatches, 1 SemanticMatches, 70 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1165 ImplicationChecksByTransitivity, 3.3s TimeCoverageRelationStatistics Valid=641, Invalid=4471, Unknown=0, NotChecked=0, Total=5112 [2018-01-28 21:01:58,446 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 345 states. [2018-01-28 21:01:58,456 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 345 to 156. [2018-01-28 21:01:58,457 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 156 states. [2018-01-28 21:01:58,458 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 156 states to 156 states and 177 transitions. [2018-01-28 21:01:58,458 INFO L78 Accepts]: Start accepts. Automaton has 156 states and 177 transitions. Word has length 53 [2018-01-28 21:01:58,458 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-28 21:01:58,458 INFO L432 AbstractCegarLoop]: Abstraction has 156 states and 177 transitions. [2018-01-28 21:01:58,459 INFO L433 AbstractCegarLoop]: Interpolant automaton has 45 states. [2018-01-28 21:01:58,459 INFO L276 IsEmpty]: Start isEmpty. Operand 156 states and 177 transitions. [2018-01-28 21:01:58,459 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2018-01-28 21:01:58,460 INFO L322 BasicCegarLoop]: Found error trace [2018-01-28 21:01:58,460 INFO L330 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-28 21:01:58,460 INFO L371 AbstractCegarLoop]: === Iteration 14 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-28 21:01:58,460 INFO L82 PathProgramCache]: Analyzing trace with hash -1033741019, now seen corresponding path program 1 times [2018-01-28 21:01:58,460 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-28 21:01:58,460 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-28 21:01:58,461 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-28 21:01:58,461 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-01-28 21:01:58,461 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-28 21:01:58,471 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-28 21:01:58,472 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-28 21:01:58,488 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 3 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-28 21:01:58,488 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-28 21:01:58,489 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-01-28 21:01:58,489 INFO L409 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-01-28 21:01:58,489 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-01-28 21:01:58,489 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-28 21:01:58,489 INFO L87 Difference]: Start difference. First operand 156 states and 177 transitions. Second operand 3 states. [2018-01-28 21:01:58,511 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-28 21:01:58,511 INFO L93 Difference]: Finished difference Result 204 states and 229 transitions. [2018-01-28 21:01:58,512 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-01-28 21:01:58,512 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 54 [2018-01-28 21:01:58,512 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-28 21:01:58,513 INFO L225 Difference]: With dead ends: 204 [2018-01-28 21:01:58,513 INFO L226 Difference]: Without dead ends: 140 [2018-01-28 21:01:58,514 INFO L533 BasicCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-28 21:01:58,514 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 140 states. [2018-01-28 21:01:58,523 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 140 to 140. [2018-01-28 21:01:58,523 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 140 states. [2018-01-28 21:01:58,524 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 140 states to 140 states and 156 transitions. [2018-01-28 21:01:58,524 INFO L78 Accepts]: Start accepts. Automaton has 140 states and 156 transitions. Word has length 54 [2018-01-28 21:01:58,524 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-28 21:01:58,525 INFO L432 AbstractCegarLoop]: Abstraction has 140 states and 156 transitions. [2018-01-28 21:01:58,525 INFO L433 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-01-28 21:01:58,525 INFO L276 IsEmpty]: Start isEmpty. Operand 140 states and 156 transitions. [2018-01-28 21:01:58,525 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2018-01-28 21:01:58,525 INFO L322 BasicCegarLoop]: Found error trace [2018-01-28 21:01:58,526 INFO L330 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-28 21:01:58,526 INFO L371 AbstractCegarLoop]: === Iteration 15 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-28 21:01:58,526 INFO L82 PathProgramCache]: Analyzing trace with hash -211914578, now seen corresponding path program 1 times [2018-01-28 21:01:58,526 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-28 21:01:58,526 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-28 21:01:58,527 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-28 21:01:58,527 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-28 21:01:58,527 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-28 21:01:58,535 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-28 21:01:58,573 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-28 21:01:58,623 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-28 21:01:58,623 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-28 21:01:58,624 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2018-01-28 21:01:58,624 INFO L409 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-01-28 21:01:58,624 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-01-28 21:01:58,624 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2018-01-28 21:01:58,624 INFO L87 Difference]: Start difference. First operand 140 states and 156 transitions. Second operand 6 states. [2018-01-28 21:01:58,674 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-28 21:01:58,674 INFO L93 Difference]: Finished difference Result 189 states and 207 transitions. [2018-01-28 21:01:58,674 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-01-28 21:01:58,674 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 54 [2018-01-28 21:01:58,674 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-28 21:01:58,675 INFO L225 Difference]: With dead ends: 189 [2018-01-28 21:01:58,675 INFO L226 Difference]: Without dead ends: 169 [2018-01-28 21:01:58,676 INFO L533 BasicCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=20, Invalid=36, Unknown=0, NotChecked=0, Total=56 [2018-01-28 21:01:58,676 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 169 states. [2018-01-28 21:01:58,682 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 169 to 146. [2018-01-28 21:01:58,683 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 146 states. [2018-01-28 21:01:58,683 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 146 states to 146 states and 162 transitions. [2018-01-28 21:01:58,683 INFO L78 Accepts]: Start accepts. Automaton has 146 states and 162 transitions. Word has length 54 [2018-01-28 21:01:58,683 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-28 21:01:58,684 INFO L432 AbstractCegarLoop]: Abstraction has 146 states and 162 transitions. [2018-01-28 21:01:58,684 INFO L433 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-01-28 21:01:58,684 INFO L276 IsEmpty]: Start isEmpty. Operand 146 states and 162 transitions. [2018-01-28 21:01:58,684 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2018-01-28 21:01:58,684 INFO L322 BasicCegarLoop]: Found error trace [2018-01-28 21:01:58,684 INFO L330 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-28 21:01:58,684 INFO L371 AbstractCegarLoop]: === Iteration 16 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-28 21:01:58,684 INFO L82 PathProgramCache]: Analyzing trace with hash -899211454, now seen corresponding path program 1 times [2018-01-28 21:01:58,685 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-28 21:01:58,685 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-28 21:01:58,685 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-28 21:01:58,686 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-28 21:01:58,686 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-28 21:01:58,697 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-28 21:01:58,697 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-28 21:01:58,984 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-28 21:01:58,984 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-28 21:01:58,985 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-28 21:01:58,989 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-28 21:01:59,007 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-28 21:01:59,010 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-28 21:01:59,019 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-28 21:01:59,021 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-28 21:01:59,022 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-28 21:01:59,025 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-28 21:01:59,032 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-28 21:01:59,033 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:25, output treesize:21 [2018-01-28 21:01:59,229 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-28 21:01:59,237 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-28 21:01:59,238 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-28 21:01:59,242 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-28 21:01:59,254 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-28 21:01:59,255 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:38, output treesize:29 [2018-01-28 21:01:59,359 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-28 21:01:59,392 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-28 21:01:59,392 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 11] total 20 [2018-01-28 21:01:59,393 INFO L409 AbstractCegarLoop]: Interpolant automaton has 21 states [2018-01-28 21:01:59,393 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2018-01-28 21:01:59,393 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=48, Invalid=372, Unknown=0, NotChecked=0, Total=420 [2018-01-28 21:01:59,393 INFO L87 Difference]: Start difference. First operand 146 states and 162 transitions. Second operand 21 states. [2018-01-28 21:02:00,141 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-28 21:02:00,141 INFO L93 Difference]: Finished difference Result 192 states and 209 transitions. [2018-01-28 21:02:00,141 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2018-01-28 21:02:00,142 INFO L78 Accepts]: Start accepts. Automaton has 21 states. Word has length 58 [2018-01-28 21:02:00,142 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-28 21:02:00,143 INFO L225 Difference]: With dead ends: 192 [2018-01-28 21:02:00,143 INFO L226 Difference]: Without dead ends: 191 [2018-01-28 21:02:00,144 INFO L533 BasicCegarLoop]: 0 DeclaredPredicates, 82 GetRequests, 51 SyntacticMatches, 0 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 150 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=148, Invalid=908, Unknown=0, NotChecked=0, Total=1056 [2018-01-28 21:02:00,144 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 191 states. [2018-01-28 21:02:00,153 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 191 to 163. [2018-01-28 21:02:00,153 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 163 states. [2018-01-28 21:02:00,154 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 163 states to 163 states and 181 transitions. [2018-01-28 21:02:00,155 INFO L78 Accepts]: Start accepts. Automaton has 163 states and 181 transitions. Word has length 58 [2018-01-28 21:02:00,155 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-28 21:02:00,155 INFO L432 AbstractCegarLoop]: Abstraction has 163 states and 181 transitions. [2018-01-28 21:02:00,155 INFO L433 AbstractCegarLoop]: Interpolant automaton has 21 states. [2018-01-28 21:02:00,155 INFO L276 IsEmpty]: Start isEmpty. Operand 163 states and 181 transitions. [2018-01-28 21:02:00,156 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 60 [2018-01-28 21:02:00,156 INFO L322 BasicCegarLoop]: Found error trace [2018-01-28 21:02:00,156 INFO L330 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-28 21:02:00,156 INFO L371 AbstractCegarLoop]: === Iteration 17 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-28 21:02:00,157 INFO L82 PathProgramCache]: Analyzing trace with hash -2105751261, now seen corresponding path program 1 times [2018-01-28 21:02:00,157 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-28 21:02:00,157 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-28 21:02:00,157 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-28 21:02:00,158 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-28 21:02:00,158 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-28 21:02:00,168 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-28 21:02:00,169 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-28 21:02:00,212 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2018-01-28 21:02:00,213 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-28 21:02:00,213 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2018-01-28 21:02:00,213 INFO L409 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-01-28 21:02:00,213 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-01-28 21:02:00,213 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2018-01-28 21:02:00,213 INFO L87 Difference]: Start difference. First operand 163 states and 181 transitions. Second operand 7 states. [2018-01-28 21:02:00,300 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-28 21:02:00,300 INFO L93 Difference]: Finished difference Result 163 states and 181 transitions. [2018-01-28 21:02:00,300 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-01-28 21:02:00,300 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 59 [2018-01-28 21:02:00,301 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-28 21:02:00,301 INFO L225 Difference]: With dead ends: 163 [2018-01-28 21:02:00,301 INFO L226 Difference]: Without dead ends: 161 [2018-01-28 21:02:00,302 INFO L533 BasicCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 2 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-28 21:02:00,302 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 161 states. [2018-01-28 21:02:00,310 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 161 to 157. [2018-01-28 21:02:00,310 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 157 states. [2018-01-28 21:02:00,312 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 157 states to 157 states and 174 transitions. [2018-01-28 21:02:00,312 INFO L78 Accepts]: Start accepts. Automaton has 157 states and 174 transitions. Word has length 59 [2018-01-28 21:02:00,312 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-28 21:02:00,312 INFO L432 AbstractCegarLoop]: Abstraction has 157 states and 174 transitions. [2018-01-28 21:02:00,312 INFO L433 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-01-28 21:02:00,312 INFO L276 IsEmpty]: Start isEmpty. Operand 157 states and 174 transitions. [2018-01-28 21:02:00,313 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 60 [2018-01-28 21:02:00,313 INFO L322 BasicCegarLoop]: Found error trace [2018-01-28 21:02:00,313 INFO L330 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-28 21:02:00,313 INFO L371 AbstractCegarLoop]: === Iteration 18 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-28 21:02:00,314 INFO L82 PathProgramCache]: Analyzing trace with hash -2105751260, now seen corresponding path program 1 times [2018-01-28 21:02:00,314 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-28 21:02:00,314 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-28 21:02:00,315 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-28 21:02:00,315 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-28 21:02:00,315 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-28 21:02:00,326 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-28 21:02:00,327 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-28 21:02:00,610 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-28 21:02:00,610 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-28 21:02:00,610 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-28 21:02:00,615 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-28 21:02:00,632 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-28 21:02:00,635 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-28 21:02:00,671 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-28 21:02:00,671 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-28 21:02:00,675 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-28 21:02:00,676 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 2 variables, input treesize:15, output treesize:11 [2018-01-28 21:02:00,980 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-28 21:02:01,000 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-28 21:02:01,000 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 18] total 35 [2018-01-28 21:02:01,001 INFO L409 AbstractCegarLoop]: Interpolant automaton has 36 states [2018-01-28 21:02:01,001 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 36 interpolants. [2018-01-28 21:02:01,001 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=97, Invalid=1163, Unknown=0, NotChecked=0, Total=1260 [2018-01-28 21:02:01,001 INFO L87 Difference]: Start difference. First operand 157 states and 174 transitions. Second operand 36 states. [2018-01-28 21:02:01,935 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-28 21:02:01,936 INFO L93 Difference]: Finished difference Result 233 states and 255 transitions. [2018-01-28 21:02:01,936 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2018-01-28 21:02:01,936 INFO L78 Accepts]: Start accepts. Automaton has 36 states. Word has length 59 [2018-01-28 21:02:01,936 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-28 21:02:01,937 INFO L225 Difference]: With dead ends: 233 [2018-01-28 21:02:01,937 INFO L226 Difference]: Without dead ends: 230 [2018-01-28 21:02:01,938 INFO L533 BasicCegarLoop]: 0 DeclaredPredicates, 96 GetRequests, 43 SyntacticMatches, 0 SemanticMatches, 53 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 599 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=323, Invalid=2647, Unknown=0, NotChecked=0, Total=2970 [2018-01-28 21:02:01,938 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 230 states. [2018-01-28 21:02:01,948 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 230 to 190. [2018-01-28 21:02:01,948 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 190 states. [2018-01-28 21:02:01,949 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 190 states to 190 states and 211 transitions. [2018-01-28 21:02:01,949 INFO L78 Accepts]: Start accepts. Automaton has 190 states and 211 transitions. Word has length 59 [2018-01-28 21:02:01,950 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-28 21:02:01,950 INFO L432 AbstractCegarLoop]: Abstraction has 190 states and 211 transitions. [2018-01-28 21:02:01,950 INFO L433 AbstractCegarLoop]: Interpolant automaton has 36 states. [2018-01-28 21:02:01,950 INFO L276 IsEmpty]: Start isEmpty. Operand 190 states and 211 transitions. [2018-01-28 21:02:01,951 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 60 [2018-01-28 21:02:01,951 INFO L322 BasicCegarLoop]: Found error trace [2018-01-28 21:02:01,951 INFO L330 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-28 21:02:01,951 INFO L371 AbstractCegarLoop]: === Iteration 19 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-28 21:02:01,951 INFO L82 PathProgramCache]: Analyzing trace with hash -1283924820, now seen corresponding path program 1 times [2018-01-28 21:02:01,951 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-28 21:02:01,952 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-28 21:02:01,952 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-28 21:02:01,952 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-28 21:02:01,953 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-28 21:02:01,964 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-28 21:02:01,965 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-28 21:02:02,104 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-28 21:02:02,104 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-28 21:02:02,104 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-01-28 21:02:02,104 INFO L409 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-01-28 21:02:02,105 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-01-28 21:02:02,105 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2018-01-28 21:02:02,106 INFO L87 Difference]: Start difference. First operand 190 states and 211 transitions. Second operand 6 states. [2018-01-28 21:02:02,290 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-28 21:02:02,290 INFO L93 Difference]: Finished difference Result 190 states and 211 transitions. [2018-01-28 21:02:02,291 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-01-28 21:02:02,291 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 59 [2018-01-28 21:02:02,291 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-28 21:02:02,292 INFO L225 Difference]: With dead ends: 190 [2018-01-28 21:02:02,292 INFO L226 Difference]: Without dead ends: 171 [2018-01-28 21:02:02,292 INFO L533 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-28 21:02:02,292 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 171 states. [2018-01-28 21:02:02,298 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 171 to 163. [2018-01-28 21:02:02,298 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 163 states. [2018-01-28 21:02:02,299 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 163 states to 163 states and 177 transitions. [2018-01-28 21:02:02,299 INFO L78 Accepts]: Start accepts. Automaton has 163 states and 177 transitions. Word has length 59 [2018-01-28 21:02:02,299 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-28 21:02:02,299 INFO L432 AbstractCegarLoop]: Abstraction has 163 states and 177 transitions. [2018-01-28 21:02:02,299 INFO L433 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-01-28 21:02:02,299 INFO L276 IsEmpty]: Start isEmpty. Operand 163 states and 177 transitions. [2018-01-28 21:02:02,307 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 61 [2018-01-28 21:02:02,308 INFO L322 BasicCegarLoop]: Found error trace [2018-01-28 21:02:02,308 INFO L330 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-28 21:02:02,308 INFO L371 AbstractCegarLoop]: === Iteration 20 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-28 21:02:02,309 INFO L82 PathProgramCache]: Analyzing trace with hash -525498700, now seen corresponding path program 1 times [2018-01-28 21:02:02,309 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-28 21:02:02,309 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-28 21:02:02,310 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-28 21:02:02,310 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-28 21:02:02,310 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-28 21:02:02,319 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-28 21:02:02,320 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-28 21:02:02,473 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-28 21:02:02,474 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-28 21:02:02,474 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-28 21:02:02,481 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-28 21:02:02,503 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-28 21:02:02,507 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-28 21:02:02,556 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 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-28 21:02:02,557 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-28 21:02:02,564 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-28 21:02:02,565 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-28 21:02:02,571 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-28 21:02:02,571 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:24, output treesize:19 [2018-01-28 21:02:02,610 INFO L700 Elim1Store]: detected not equals via solver [2018-01-28 21:02:02,610 INFO L700 Elim1Store]: detected not equals via solver [2018-01-28 21:02:02,611 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-28 21:02:02,611 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-28 21:02:02,619 INFO L700 Elim1Store]: detected not equals via solver [2018-01-28 21:02:02,620 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-28 21:02:02,621 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-28 21:02:02,628 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-28 21:02:02,628 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:30, output treesize:18 [2018-01-28 21:02:02,781 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-28 21:02:02,802 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-28 21:02:02,802 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 24 [2018-01-28 21:02:02,802 INFO L409 AbstractCegarLoop]: Interpolant automaton has 25 states [2018-01-28 21:02:02,803 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2018-01-28 21:02:02,803 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=68, Invalid=532, Unknown=0, NotChecked=0, Total=600 [2018-01-28 21:02:02,803 INFO L87 Difference]: Start difference. First operand 163 states and 177 transitions. Second operand 25 states. [2018-01-28 21:02:03,402 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-28 21:02:03,402 INFO L93 Difference]: Finished difference Result 172 states and 185 transitions. [2018-01-28 21:02:03,403 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-01-28 21:02:03,403 INFO L78 Accepts]: Start accepts. Automaton has 25 states. Word has length 60 [2018-01-28 21:02:03,403 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-28 21:02:03,404 INFO L225 Difference]: With dead ends: 172 [2018-01-28 21:02:03,404 INFO L226 Difference]: Without dead ends: 166 [2018-01-28 21:02:03,405 INFO L533 BasicCegarLoop]: 0 DeclaredPredicates, 81 GetRequests, 49 SyntacticMatches, 0 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 243 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=166, Invalid=956, Unknown=0, NotChecked=0, Total=1122 [2018-01-28 21:02:03,405 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 166 states. [2018-01-28 21:02:03,414 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 166 to 158. [2018-01-28 21:02:03,414 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 158 states. [2018-01-28 21:02:03,415 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 158 states to 158 states and 171 transitions. [2018-01-28 21:02:03,415 INFO L78 Accepts]: Start accepts. Automaton has 158 states and 171 transitions. Word has length 60 [2018-01-28 21:02:03,415 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-28 21:02:03,415 INFO L432 AbstractCegarLoop]: Abstraction has 158 states and 171 transitions. [2018-01-28 21:02:03,415 INFO L433 AbstractCegarLoop]: Interpolant automaton has 25 states. [2018-01-28 21:02:03,416 INFO L276 IsEmpty]: Start isEmpty. Operand 158 states and 171 transitions. [2018-01-28 21:02:03,416 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 61 [2018-01-28 21:02:03,416 INFO L322 BasicCegarLoop]: Found error trace [2018-01-28 21:02:03,417 INFO L330 BasicCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 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-28 21:02:03,417 INFO L371 AbstractCegarLoop]: === Iteration 21 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-28 21:02:03,417 INFO L82 PathProgramCache]: Analyzing trace with hash 1066252721, now seen corresponding path program 4 times [2018-01-28 21:02:03,417 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-28 21:02:03,417 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-28 21:02:03,418 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-28 21:02:03,418 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-28 21:02:03,418 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-28 21:02:03,432 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-28 21:02:03,433 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-28 21:02:04,377 INFO L134 CoverageAnalysis]: Checked inductivity of 50 backedges. 0 proven. 50 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-28 21:02:04,377 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-28 21:02:04,377 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-28 21:02:04,382 INFO L101 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-01-28 21:02:04,402 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-28 21:02:04,406 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-28 21:02:04,477 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-28 21:02:04,477 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-28 21:02:04,485 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-28 21:02:04,486 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-28 21:02:04,492 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-28 21:02:04,492 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:27, output treesize:25 [2018-01-28 21:02:04,558 INFO L700 Elim1Store]: detected not equals via solver [2018-01-28 21:02:04,559 INFO L700 Elim1Store]: detected not equals via solver [2018-01-28 21:02:04,560 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-28 21:02:04,560 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-28 21:02:04,572 INFO L700 Elim1Store]: detected not equals via solver [2018-01-28 21:02:04,573 INFO L700 Elim1Store]: detected not equals via solver [2018-01-28 21:02:04,573 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-28 21:02:04,573 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-28 21:02:04,580 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-28 21:02:04,580 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:36, output treesize:25 [2018-01-28 21:02:04,647 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-28 21:02:04,649 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-28 21:02:04,649 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-28 21:02:04,650 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-28 21:02:04,657 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-28 21:02:04,658 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:41, output treesize:37 [2018-01-28 21:02:04,697 INFO L700 Elim1Store]: detected not equals via solver [2018-01-28 21:02:04,700 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-28 21:02:04,702 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-28 21:02:04,702 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-28 21:02:04,706 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-28 21:02:04,713 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-28 21:02:04,714 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:52, output treesize:48 [2018-01-28 21:02:05,438 INFO L700 Elim1Store]: detected not equals via solver [2018-01-28 21:02:05,440 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 55 treesize of output 49 [2018-01-28 21:02:05,443 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 1 [2018-01-28 21:02:05,443 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-28 21:02:05,455 INFO L700 Elim1Store]: detected not equals via solver [2018-01-28 21:02:05,456 INFO L700 Elim1Store]: detected not equals via solver [2018-01-28 21:02:05,456 INFO L700 Elim1Store]: detected not equals via solver [2018-01-28 21:02:05,465 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 35 treesize of output 73 [2018-01-28 21:02:05,466 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 2 xjuncts. [2018-01-28 21:02:05,486 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-28 21:02:05,506 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-28 21:02:05,507 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 5 variables, input treesize:83, output treesize:146 [2018-01-28 21:02:05,937 INFO L134 CoverageAnalysis]: Checked inductivity of 50 backedges. 0 proven. 50 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-28 21:02:05,957 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-28 21:02:05,957 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [24, 27] total 50 [2018-01-28 21:02:05,957 INFO L409 AbstractCegarLoop]: Interpolant automaton has 51 states [2018-01-28 21:02:05,957 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 51 interpolants. [2018-01-28 21:02:05,958 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=157, Invalid=2393, Unknown=0, NotChecked=0, Total=2550 [2018-01-28 21:02:05,958 INFO L87 Difference]: Start difference. First operand 158 states and 171 transitions. Second operand 51 states. [2018-01-28 21:02:06,775 WARN L146 SmtUtils]: Spent 360ms on a formula simplification. DAG size of input: 91 DAG size of output 52 [2018-01-28 21:02:32,680 WARN L146 SmtUtils]: Spent 112ms on a formula simplification. DAG size of input: 116 DAG size of output 84 [2018-01-28 21:02:38,196 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-28 21:02:38,196 INFO L93 Difference]: Finished difference Result 261 states and 275 transitions. [2018-01-28 21:02:38,196 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 37 states. [2018-01-28 21:02:38,196 INFO L78 Accepts]: Start accepts. Automaton has 51 states. Word has length 60 [2018-01-28 21:02:38,197 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-28 21:02:38,197 INFO L225 Difference]: With dead ends: 261 [2018-01-28 21:02:38,197 INFO L226 Difference]: Without dead ends: 242 [2018-01-28 21:02:38,199 INFO L533 BasicCegarLoop]: 0 DeclaredPredicates, 116 GetRequests, 34 SyntacticMatches, 1 SemanticMatches, 81 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1634 ImplicationChecksByTransitivity, 32.9s TimeCoverageRelationStatistics Valid=584, Invalid=6216, Unknown=6, NotChecked=0, Total=6806 [2018-01-28 21:02:38,199 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 242 states. [2018-01-28 21:02:38,206 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 242 to 165. [2018-01-28 21:02:38,206 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 165 states. [2018-01-28 21:02:38,207 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 165 states to 165 states and 179 transitions. [2018-01-28 21:02:38,207 INFO L78 Accepts]: Start accepts. Automaton has 165 states and 179 transitions. Word has length 60 [2018-01-28 21:02:38,207 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-28 21:02:38,207 INFO L432 AbstractCegarLoop]: Abstraction has 165 states and 179 transitions. [2018-01-28 21:02:38,207 INFO L433 AbstractCegarLoop]: Interpolant automaton has 51 states. [2018-01-28 21:02:38,207 INFO L276 IsEmpty]: Start isEmpty. Operand 165 states and 179 transitions. [2018-01-28 21:02:38,208 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 67 [2018-01-28 21:02:38,208 INFO L322 BasicCegarLoop]: Found error trace [2018-01-28 21:02:38,208 INFO L330 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-28 21:02:38,208 INFO L371 AbstractCegarLoop]: === Iteration 22 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-28 21:02:38,208 INFO L82 PathProgramCache]: Analyzing trace with hash 1708344081, now seen corresponding path program 1 times [2018-01-28 21:02:38,208 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-28 21:02:38,208 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-28 21:02:38,209 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-28 21:02:38,209 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-01-28 21:02:38,209 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-28 21:02:38,217 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-28 21:02:38,218 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-28 21:02:38,687 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-28 21:02:38,688 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-28 21:02:38,688 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-28 21:02:38,693 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-28 21:02:38,713 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-28 21:02:38,716 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-28 21:02:38,747 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-28 21:02:38,747 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-28 21:02:38,755 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-28 21:02:38,756 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-28 21:02:38,763 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-28 21:02:38,763 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:24, output treesize:19 [2018-01-28 21:02:38,818 INFO L700 Elim1Store]: detected not equals via solver [2018-01-28 21:02:38,819 INFO L700 Elim1Store]: detected not equals via solver [2018-01-28 21:02:38,820 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-28 21:02:38,820 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-28 21:02:38,831 INFO L700 Elim1Store]: detected not equals via solver [2018-01-28 21:02:38,832 INFO L700 Elim1Store]: detected not equals via solver [2018-01-28 21:02:38,832 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-28 21:02:38,833 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-28 21:02:38,838 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-28 21:02:38,838 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:30, output treesize:16 [2018-01-28 21:02:39,528 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-28 21:02:39,552 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-28 21:02:39,552 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 24] total 44 [2018-01-28 21:02:39,552 INFO L409 AbstractCegarLoop]: Interpolant automaton has 45 states [2018-01-28 21:02:39,553 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 45 interpolants. [2018-01-28 21:02:39,553 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=113, Invalid=1867, Unknown=0, NotChecked=0, Total=1980 [2018-01-28 21:02:39,553 INFO L87 Difference]: Start difference. First operand 165 states and 179 transitions. Second operand 45 states. [2018-01-28 21:02:42,513 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-28 21:02:42,513 INFO L93 Difference]: Finished difference Result 265 states and 283 transitions. [2018-01-28 21:02:42,513 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 39 states. [2018-01-28 21:02:42,513 INFO L78 Accepts]: Start accepts. Automaton has 45 states. Word has length 66 [2018-01-28 21:02:42,514 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-28 21:02:42,514 INFO L225 Difference]: With dead ends: 265 [2018-01-28 21:02:42,514 INFO L226 Difference]: Without dead ends: 242 [2018-01-28 21:02:42,516 INFO L533 BasicCegarLoop]: 0 DeclaredPredicates, 122 GetRequests, 44 SyntacticMatches, 0 SemanticMatches, 78 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1394 ImplicationChecksByTransitivity, 3.2s TimeCoverageRelationStatistics Valid=602, Invalid=5718, Unknown=0, NotChecked=0, Total=6320 [2018-01-28 21:02:42,516 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 242 states. [2018-01-28 21:02:42,523 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 242 to 213. [2018-01-28 21:02:42,523 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 213 states. [2018-01-28 21:02:42,524 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 213 states to 213 states and 230 transitions. [2018-01-28 21:02:42,524 INFO L78 Accepts]: Start accepts. Automaton has 213 states and 230 transitions. Word has length 66 [2018-01-28 21:02:42,524 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-28 21:02:42,524 INFO L432 AbstractCegarLoop]: Abstraction has 213 states and 230 transitions. [2018-01-28 21:02:42,524 INFO L433 AbstractCegarLoop]: Interpolant automaton has 45 states. [2018-01-28 21:02:42,525 INFO L276 IsEmpty]: Start isEmpty. Operand 213 states and 230 transitions. [2018-01-28 21:02:42,525 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 68 [2018-01-28 21:02:42,525 INFO L322 BasicCegarLoop]: Found error trace [2018-01-28 21:02:42,525 INFO L330 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-28 21:02:42,525 INFO L371 AbstractCegarLoop]: === Iteration 23 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-28 21:02:42,525 INFO L82 PathProgramCache]: Analyzing trace with hash 1747339879, now seen corresponding path program 1 times [2018-01-28 21:02:42,525 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-28 21:02:42,526 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-28 21:02:42,526 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-28 21:02:42,526 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-28 21:02:42,526 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-28 21:02:42,536 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-28 21:02:42,537 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-28 21:02:42,923 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-28 21:02:42,924 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-28 21:02:42,924 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-28 21:02:42,929 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-28 21:02:42,946 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-28 21:02:42,949 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-28 21:02:42,952 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-28 21:02:42,952 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-28 21:02:42,959 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-28 21:02:42,959 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-28 21:02:42,965 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-28 21:02:42,965 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:24, output treesize:19 [2018-01-28 21:02:43,014 INFO L700 Elim1Store]: detected not equals via solver [2018-01-28 21:02:43,015 INFO L700 Elim1Store]: detected not equals via solver [2018-01-28 21:02:43,015 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-28 21:02:43,015 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-28 21:02:43,024 INFO L700 Elim1Store]: detected not equals via solver [2018-01-28 21:02:43,024 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-28 21:02:43,025 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-28 21:02:43,032 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-28 21:02:43,032 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:30, output treesize:19 [2018-01-28 21:02:43,080 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-28 21:02:43,081 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 12 [2018-01-28 21:02:43,082 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-28 21:02:43,083 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-28 21:02:43,087 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-28 21:02:43,088 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:34, output treesize:30 [2018-01-28 21:02:43,347 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-28 21:02:43,353 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 1 case distinctions, treesize of input 16 treesize of output 13 [2018-01-28 21:02:43,353 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-28 21:02:43,356 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-28 21:02:43,363 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: 3 dim-0 vars, and 2 xjuncts. [2018-01-28 21:02:43,363 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:40, output treesize:55 [2018-01-28 21:02:43,582 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-28 21:02:43,603 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-28 21:02:43,603 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 22] total 40 [2018-01-28 21:02:43,603 INFO L409 AbstractCegarLoop]: Interpolant automaton has 41 states [2018-01-28 21:02:43,603 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 41 interpolants. [2018-01-28 21:02:43,604 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=116, Invalid=1524, Unknown=0, NotChecked=0, Total=1640 [2018-01-28 21:02:43,604 INFO L87 Difference]: Start difference. First operand 213 states and 230 transitions. Second operand 41 states. [2018-01-28 21:02:47,291 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-28 21:02:47,291 INFO L93 Difference]: Finished difference Result 241 states and 255 transitions. [2018-01-28 21:02:47,291 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 29 states. [2018-01-28 21:02:47,291 INFO L78 Accepts]: Start accepts. Automaton has 41 states. Word has length 67 [2018-01-28 21:02:47,292 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-28 21:02:47,292 INFO L225 Difference]: With dead ends: 241 [2018-01-28 21:02:47,292 INFO L226 Difference]: Without dead ends: 235 [2018-01-28 21:02:47,293 INFO L533 BasicCegarLoop]: 0 DeclaredPredicates, 112 GetRequests, 49 SyntacticMatches, 0 SemanticMatches, 63 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1007 ImplicationChecksByTransitivity, 1.8s TimeCoverageRelationStatistics Valid=400, Invalid=3760, Unknown=0, NotChecked=0, Total=4160 [2018-01-28 21:02:47,294 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 235 states. [2018-01-28 21:02:47,301 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 235 to 213. [2018-01-28 21:02:47,301 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 213 states. [2018-01-28 21:02:47,301 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 213 states to 213 states and 229 transitions. [2018-01-28 21:02:47,301 INFO L78 Accepts]: Start accepts. Automaton has 213 states and 229 transitions. Word has length 67 [2018-01-28 21:02:47,302 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-28 21:02:47,302 INFO L432 AbstractCegarLoop]: Abstraction has 213 states and 229 transitions. [2018-01-28 21:02:47,302 INFO L433 AbstractCegarLoop]: Interpolant automaton has 41 states. [2018-01-28 21:02:47,302 INFO L276 IsEmpty]: Start isEmpty. Operand 213 states and 229 transitions. [2018-01-28 21:02:47,302 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 68 [2018-01-28 21:02:47,302 INFO L322 BasicCegarLoop]: Found error trace [2018-01-28 21:02:47,302 INFO L330 BasicCegarLoop]: trace histogram [6, 5, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 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-28 21:02:47,302 INFO L371 AbstractCegarLoop]: === Iteration 24 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-28 21:02:47,303 INFO L82 PathProgramCache]: Analyzing trace with hash -955875996, now seen corresponding path program 5 times [2018-01-28 21:02:47,303 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-28 21:02:47,303 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-28 21:02:47,303 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-28 21:02:47,303 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-28 21:02:47,303 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-28 21:02:47,317 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-28 21:02:47,318 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-28 21:02:48,628 INFO L134 CoverageAnalysis]: Checked inductivity of 80 backedges. 0 proven. 80 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-28 21:02:48,629 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-28 21:02:48,629 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-28 21:02:48,634 INFO L101 rtionOrderModulation]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-01-28 21:02:48,641 INFO L278 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-28 21:02:48,642 INFO L278 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-28 21:02:48,644 INFO L278 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-28 21:02:48,646 INFO L278 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-28 21:02:48,647 INFO L278 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-28 21:02:48,654 INFO L278 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-28 21:02:48,657 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-28 21:02:48,660 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-28 21:02:48,725 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-28 21:02:48,726 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-28 21:02:48,733 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-28 21:02:48,734 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-28 21:02:48,740 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-28 21:02:48,740 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:27, output treesize:25 [2018-01-28 21:02:48,804 INFO L700 Elim1Store]: detected not equals via solver [2018-01-28 21:02:48,805 INFO L700 Elim1Store]: detected not equals via solver [2018-01-28 21:02:48,805 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-28 21:02:48,805 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-28 21:02:48,816 INFO L700 Elim1Store]: detected not equals via solver [2018-01-28 21:02:48,816 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-28 21:02:48,816 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-28 21:02:48,824 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-28 21:02:48,824 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:36, output treesize:25 [2018-01-28 21:02:48,891 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-28 21:02:48,893 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 15 [2018-01-28 21:02:48,893 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-28 21:02:48,895 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-28 21:02:48,902 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-28 21:02:48,903 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:41, output treesize:37 [2018-01-28 21:02:48,943 INFO L700 Elim1Store]: detected not equals via solver [2018-01-28 21:02:48,946 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-28 21:02:48,948 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-28 21:02:48,949 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-28 21:02:48,954 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-28 21:02:48,965 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-28 21:02:48,965 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:52, output treesize:48 [2018-01-28 21:02:49,998 INFO L700 Elim1Store]: detected not equals via solver [2018-01-28 21:02:49,999 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 65 treesize of output 57 [2018-01-28 21:02:50,003 INFO L700 Elim1Store]: detected not equals via solver [2018-01-28 21:02:50,004 INFO L700 Elim1Store]: detected not equals via solver [2018-01-28 21:02:50,004 INFO L700 Elim1Store]: detected not equals via solver [2018-01-28 21:02:50,006 INFO L700 Elim1Store]: detected not equals via solver [2018-01-28 21:02:50,007 INFO L700 Elim1Store]: detected not equals via solver [2018-01-28 21:02:50,007 INFO L700 Elim1Store]: detected not equals via solver [2018-01-28 21:02:50,016 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 5 select indices, 5 select index equivalence classes, 12 disjoint index pairs (out of 10 index pairs), introduced 3 new quantified variables, introduced 1 case distinctions, treesize of input 43 treesize of output 113 [2018-01-28 21:02:50,017 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-28 21:02:50,052 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-28 21:02:50,052 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-28 21:02:50,065 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-28 21:02:50,090 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-28 21:02:50,090 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 5 variables, input treesize:93, output treesize:166 [2018-01-28 21:02:50,504 INFO L134 CoverageAnalysis]: Checked inductivity of 80 backedges. 0 proven. 80 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-28 21:02:50,524 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-28 21:02:50,524 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [29, 31] total 59 [2018-01-28 21:02:50,524 INFO L409 AbstractCegarLoop]: Interpolant automaton has 60 states [2018-01-28 21:02:50,524 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 60 interpolants. [2018-01-28 21:02:50,525 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=288, Invalid=3252, Unknown=0, NotChecked=0, Total=3540 [2018-01-28 21:02:50,525 INFO L87 Difference]: Start difference. First operand 213 states and 229 transitions. Second operand 60 states. [2018-01-28 21:02:51,340 WARN L146 SmtUtils]: Spent 385ms on a formula simplification. DAG size of input: 105 DAG size of output 52 [2018-01-28 21:02:56,935 WARN L146 SmtUtils]: Spent 1140ms on a formula simplification. DAG size of input: 115 DAG size of output 76 [2018-01-28 21:03:02,808 WARN L146 SmtUtils]: Spent 147ms on a formula simplification. DAG size of input: 122 DAG size of output 83 [2018-01-28 21:03:05,394 WARN L146 SmtUtils]: Spent 115ms on a formula simplification. DAG size of input: 106 DAG size of output 67 [2018-01-28 21:03:14,886 WARN L146 SmtUtils]: Spent 105ms on a formula simplification. DAG size of input: 132 DAG size of output 93 [2018-01-28 21:03:15,349 WARN L146 SmtUtils]: Spent 118ms on a formula simplification. DAG size of input: 135 DAG size of output 97 [2018-01-28 21:03:16,010 WARN L146 SmtUtils]: Spent 157ms on a formula simplification. DAG size of input: 148 DAG size of output 88 [2018-01-28 21:03:17,006 WARN L146 SmtUtils]: Spent 108ms on a formula simplification. DAG size of input: 127 DAG size of output 82 [2018-01-28 21:03:21,267 WARN L146 SmtUtils]: Spent 149ms on a formula simplification. DAG size of input: 145 DAG size of output 104 [2018-01-28 21:03:21,917 WARN L146 SmtUtils]: Spent 103ms on a formula simplification. DAG size of input: 122 DAG size of output 85 [2018-01-28 21:03:38,442 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-28 21:03:38,442 INFO L93 Difference]: Finished difference Result 364 states and 388 transitions. [2018-01-28 21:03:38,442 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 51 states. [2018-01-28 21:03:38,443 INFO L78 Accepts]: Start accepts. Automaton has 60 states. Word has length 67 [2018-01-28 21:03:38,443 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-28 21:03:38,444 INFO L225 Difference]: With dead ends: 364 [2018-01-28 21:03:38,444 INFO L226 Difference]: Without dead ends: 330 [2018-01-28 21:03:38,447 INFO L533 BasicCegarLoop]: 0 DeclaredPredicates, 140 GetRequests, 37 SyntacticMatches, 1 SemanticMatches, 102 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3163 ImplicationChecksByTransitivity, 48.2s TimeCoverageRelationStatistics Valid=1138, Invalid=9567, Unknown=7, NotChecked=0, Total=10712 [2018-01-28 21:03:38,448 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 330 states. [2018-01-28 21:03:38,464 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 330 to 227. [2018-01-28 21:03:38,465 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 227 states. [2018-01-28 21:03:38,465 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 227 states to 227 states and 245 transitions. [2018-01-28 21:03:38,465 INFO L78 Accepts]: Start accepts. Automaton has 227 states and 245 transitions. Word has length 67 [2018-01-28 21:03:38,466 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-28 21:03:38,466 INFO L432 AbstractCegarLoop]: Abstraction has 227 states and 245 transitions. [2018-01-28 21:03:38,466 INFO L433 AbstractCegarLoop]: Interpolant automaton has 60 states. [2018-01-28 21:03:38,466 INFO L276 IsEmpty]: Start isEmpty. Operand 227 states and 245 transitions. [2018-01-28 21:03:38,467 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2018-01-28 21:03:38,467 INFO L322 BasicCegarLoop]: Found error trace [2018-01-28 21:03:38,467 INFO L330 BasicCegarLoop]: trace histogram [3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-28 21:03:38,467 INFO L371 AbstractCegarLoop]: === Iteration 25 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-28 21:03:38,468 INFO L82 PathProgramCache]: Analyzing trace with hash -815188860, now seen corresponding path program 2 times [2018-01-28 21:03:38,468 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-28 21:03:38,468 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-28 21:03:38,468 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-28 21:03:38,469 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-01-28 21:03:38,469 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-28 21:03:38,482 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-28 21:03:38,482 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-28 21:03:39,238 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 0 proven. 20 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-28 21:03:39,239 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-28 21:03:39,239 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-28 21:03:39,244 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-01-28 21:03:39,256 INFO L201 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-28 21:03:39,263 INFO L214 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-28 21:03:39,265 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-28 21:03:39,268 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-28 21:03:39,272 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-28 21:03:39,272 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-28 21:03:39,287 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-28 21:03:39,287 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-28 21:03:39,294 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-28 21:03:39,294 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:24, output treesize:19 [2018-01-28 21:03:39,354 INFO L700 Elim1Store]: detected not equals via solver [2018-01-28 21:03:39,354 INFO L700 Elim1Store]: detected not equals via solver [2018-01-28 21:03:39,355 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-28 21:03:39,355 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-28 21:03:39,362 INFO L700 Elim1Store]: detected not equals via solver [2018-01-28 21:03:39,363 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-28 21:03:39,363 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-28 21:03:39,369 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-28 21:03:39,369 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:30, output treesize:16 [2018-01-28 21:03:40,093 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 0 proven. 20 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-28 21:03:40,113 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-28 21:03:40,113 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [29, 27] total 53 [2018-01-28 21:03:40,113 INFO L409 AbstractCegarLoop]: Interpolant automaton has 54 states [2018-01-28 21:03:40,114 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 54 interpolants. [2018-01-28 21:03:40,114 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=150, Invalid=2712, Unknown=0, NotChecked=0, Total=2862 [2018-01-28 21:03:40,115 INFO L87 Difference]: Start difference. First operand 227 states and 245 transitions. Second operand 54 states. [2018-01-28 21:03:42,295 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-28 21:03:42,295 INFO L93 Difference]: Finished difference Result 292 states and 310 transitions. [2018-01-28 21:03:42,295 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 35 states. [2018-01-28 21:03:42,295 INFO L78 Accepts]: Start accepts. Automaton has 54 states. Word has length 73 [2018-01-28 21:03:42,296 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-28 21:03:42,297 INFO L225 Difference]: With dead ends: 292 [2018-01-28 21:03:42,297 INFO L226 Difference]: Without dead ends: 279 [2018-01-28 21:03:42,298 INFO L533 BasicCegarLoop]: 0 DeclaredPredicates, 130 GetRequests, 49 SyntacticMatches, 0 SemanticMatches, 81 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1662 ImplicationChecksByTransitivity, 2.5s TimeCoverageRelationStatistics Valid=539, Invalid=6267, Unknown=0, NotChecked=0, Total=6806 [2018-01-28 21:03:42,298 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 279 states. [2018-01-28 21:03:42,308 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 279 to 249. [2018-01-28 21:03:42,308 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 249 states. [2018-01-28 21:03:42,309 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 249 states to 249 states and 268 transitions. [2018-01-28 21:03:42,309 INFO L78 Accepts]: Start accepts. Automaton has 249 states and 268 transitions. Word has length 73 [2018-01-28 21:03:42,309 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-28 21:03:42,309 INFO L432 AbstractCegarLoop]: Abstraction has 249 states and 268 transitions. [2018-01-28 21:03:42,309 INFO L433 AbstractCegarLoop]: Interpolant automaton has 54 states. [2018-01-28 21:03:42,309 INFO L276 IsEmpty]: Start isEmpty. Operand 249 states and 268 transitions. [2018-01-28 21:03:42,310 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2018-01-28 21:03:42,310 INFO L322 BasicCegarLoop]: Found error trace [2018-01-28 21:03:42,310 INFO L330 BasicCegarLoop]: trace histogram [3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-28 21:03:42,310 INFO L371 AbstractCegarLoop]: === Iteration 26 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-28 21:03:42,310 INFO L82 PathProgramCache]: Analyzing trace with hash 827230036, now seen corresponding path program 2 times [2018-01-28 21:03:42,310 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-28 21:03:42,310 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-28 21:03:42,311 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-28 21:03:42,311 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-01-28 21:03:42,311 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-28 21:03:42,319 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-28 21:03:42,320 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-28 21:03:43,194 INFO L134 CoverageAnalysis]: Checked inductivity of 17 backedges. 0 proven. 17 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-28 21:03:43,195 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-28 21:03:43,195 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-28 21:03:43,200 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-01-28 21:03:43,212 INFO L201 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-28 21:03:43,219 INFO L214 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-28 21:03:43,221 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-28 21:03:43,224 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-28 21:03:43,256 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-28 21:03:43,256 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-28 21:03:43,261 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-28 21:03:43,262 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-28 21:03:43,266 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-28 21:03:43,266 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:19, output treesize:17 [2018-01-28 21:03:43,320 INFO L700 Elim1Store]: detected not equals via solver [2018-01-28 21:03:43,321 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-28 21:03:43,322 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-28 21:03:43,330 INFO L700 Elim1Store]: detected not equals via solver [2018-01-28 21:03:43,331 INFO L700 Elim1Store]: detected not equals via solver [2018-01-28 21:03:43,331 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-28 21:03:43,332 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-28 21:03:43,337 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-28 21:03:43,337 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:28, output treesize:21 [2018-01-28 21:03:43,399 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 16 [2018-01-28 21:03:43,401 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 15 [2018-01-28 21:03:43,401 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-28 21:03:43,403 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-28 21:03:43,409 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-28 21:03:43,409 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:35, output treesize:31 [2018-01-28 21:03:43,452 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-28 21:03:43,454 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-28 21:03:43,569 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-28 21:03:43,573 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-28 21:03:43,579 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-28 21:03:43,580 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:42, output treesize:38 [2018-01-28 21:03:43,943 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-28 21:03:43,948 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-28 21:03:43,949 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-28 21:03:43,955 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-28 21:03:43,956 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-28 21:03:43,958 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-28 21:03:43,966 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-2 vars, End of recursive call: and 2 xjuncts. [2018-01-28 21:03:43,966 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 4 variables, input treesize:47, output treesize:38 [2018-01-28 21:03:44,555 INFO L134 CoverageAnalysis]: Checked inductivity of 17 backedges. 2 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-28 21:03:44,575 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-28 21:03:44,575 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [27, 25] total 51 [2018-01-28 21:03:44,575 INFO L409 AbstractCegarLoop]: Interpolant automaton has 52 states [2018-01-28 21:03:44,575 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 52 interpolants. [2018-01-28 21:03:44,576 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=136, Invalid=2516, Unknown=0, NotChecked=0, Total=2652 [2018-01-28 21:03:44,576 INFO L87 Difference]: Start difference. First operand 249 states and 268 transitions. Second operand 52 states. [2018-01-28 21:03:49,319 WARN L146 SmtUtils]: Spent 4047ms on a formula simplification. DAG size of input: 62 DAG size of output 56 [2018-01-28 21:03:53,756 WARN L146 SmtUtils]: Spent 4133ms on a formula simplification. DAG size of input: 91 DAG size of output 80 [2018-01-28 21:03:57,999 WARN L146 SmtUtils]: Spent 4146ms on a formula simplification. DAG size of input: 110 DAG size of output 94 [2018-01-28 21:04:02,409 WARN L146 SmtUtils]: Spent 4261ms on a formula simplification. DAG size of input: 113 DAG size of output 98 [2018-01-28 21:04:02,597 WARN L146 SmtUtils]: Spent 127ms on a formula simplification. DAG size of input: 94 DAG size of output 84 [2018-01-28 21:04:03,148 WARN L146 SmtUtils]: Spent 160ms on a formula simplification. DAG size of input: 108 DAG size of output 93 [2018-01-28 21:04:03,417 WARN L146 SmtUtils]: Spent 157ms on a formula simplification. DAG size of input: 104 DAG size of output 85 [2018-01-28 21:04:03,869 WARN L146 SmtUtils]: Spent 309ms on a formula simplification. DAG size of input: 96 DAG size of output 86 [2018-01-28 21:04:04,205 WARN L146 SmtUtils]: Spent 259ms on a formula simplification. DAG size of input: 127 DAG size of output 103 [2018-01-28 21:04:04,630 WARN L146 SmtUtils]: Spent 322ms on a formula simplification. DAG size of input: 124 DAG size of output 105 [2018-01-28 21:04:05,616 WARN L146 SmtUtils]: Spent 921ms on a formula simplification. DAG size of input: 100 DAG size of output 86 Received shutdown request... [2018-01-28 21:04:09,797 WARN L146 SmtUtils]: Spent 4081ms on a formula simplification. DAG size of input: 82 DAG size of output 72 [2018-01-28 21:04:09,798 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2018-01-28 21:04:09,798 WARN L491 AbstractCegarLoop]: Verification canceled [2018-01-28 21:04:09,803 WARN L185 ceAbstractionStarter]: Timeout [2018-01-28 21:04:09,803 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 28.01 09:04:09 BoogieIcfgContainer [2018-01-28 21:04:09,803 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-01-28 21:04:09,804 INFO L168 Benchmark]: Toolchain (without parser) took 144646.70 ms. Allocated memory was 303.0 MB in the beginning and 649.1 MB in the end (delta: 346.0 MB). Free memory was 263.1 MB in the beginning and 399.9 MB in the end (delta: -136.8 MB). Peak memory consumption was 209.2 MB. Max. memory is 5.3 GB. [2018-01-28 21:04:09,805 INFO L168 Benchmark]: CDTParser took 0.18 ms. Allocated memory is still 303.0 MB. Free memory is still 269.0 MB. There was no memory consumed. Max. memory is 5.3 GB. [2018-01-28 21:04:09,805 INFO L168 Benchmark]: CACSL2BoogieTranslator took 217.53 ms. Allocated memory is still 303.0 MB. Free memory was 262.1 MB in the beginning and 252.0 MB in the end (delta: 10.0 MB). Peak memory consumption was 10.0 MB. Max. memory is 5.3 GB. [2018-01-28 21:04:09,805 INFO L168 Benchmark]: Boogie Preprocessor took 39.74 ms. Allocated memory is still 303.0 MB. Free memory was 252.0 MB in the beginning and 250.0 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 5.3 GB. [2018-01-28 21:04:09,806 INFO L168 Benchmark]: RCFGBuilder took 333.28 ms. Allocated memory is still 303.0 MB. Free memory was 250.0 MB in the beginning and 226.5 MB in the end (delta: 23.6 MB). Peak memory consumption was 23.6 MB. Max. memory is 5.3 GB. [2018-01-28 21:04:09,806 INFO L168 Benchmark]: TraceAbstraction took 144049.21 ms. Allocated memory was 303.0 MB in the beginning and 649.1 MB in the end (delta: 346.0 MB). Free memory was 226.5 MB in the beginning and 399.9 MB in the end (delta: -173.4 MB). Peak memory consumption was 172.6 MB. Max. memory is 5.3 GB. [2018-01-28 21:04:09,807 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.18 ms. Allocated memory is still 303.0 MB. Free memory is still 269.0 MB. There was no memory consumed. Max. memory is 5.3 GB. * CACSL2BoogieTranslator took 217.53 ms. Allocated memory is still 303.0 MB. Free memory was 262.1 MB in the beginning and 252.0 MB in the end (delta: 10.0 MB). Peak memory consumption was 10.0 MB. Max. memory is 5.3 GB. * Boogie Preprocessor took 39.74 ms. Allocated memory is still 303.0 MB. Free memory was 252.0 MB in the beginning and 250.0 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 5.3 GB. * RCFGBuilder took 333.28 ms. Allocated memory is still 303.0 MB. Free memory was 250.0 MB in the beginning and 226.5 MB in the end (delta: 23.6 MB). Peak memory consumption was 23.6 MB. Max. memory is 5.3 GB. * TraceAbstraction took 144049.21 ms. Allocated memory was 303.0 MB in the beginning and 649.1 MB in the end (delta: 346.0 MB). Free memory was 226.5 MB in the beginning and 399.9 MB in the end (delta: -173.4 MB). Peak memory consumption was 172.6 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 570). Cancelled while BasicCegarLoop was constructing difference of abstraction (249states) and interpolant automaton (currently 27 states, 52 states before enhancement), while ReachableStatesComputation was computing reachable states (69 states constructedinput type IntersectNwa). - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 569). Cancelled while BasicCegarLoop was constructing difference of abstraction (249states) and interpolant automaton (currently 27 states, 52 states before enhancement), while ReachableStatesComputation was computing reachable states (69 states constructedinput type IntersectNwa). - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 570). Cancelled while BasicCegarLoop was constructing difference of abstraction (249states) and interpolant automaton (currently 27 states, 52 states before enhancement), while ReachableStatesComputation was computing reachable states (69 states constructedinput type IntersectNwa). - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 569). Cancelled while BasicCegarLoop was constructing difference of abstraction (249states) and interpolant automaton (currently 27 states, 52 states before enhancement), while ReachableStatesComputation was computing reachable states (69 states constructedinput type IntersectNwa). - TimeoutResultAtElement [Line: 553]: Timeout (TraceAbstraction) Unable to prove that all allocated memory was freed (line 553). Cancelled while BasicCegarLoop was constructing difference of abstraction (249states) and interpolant automaton (currently 27 states, 52 states before enhancement), while ReachableStatesComputation was computing reachable states (69 states constructedinput type IntersectNwa). - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 549). Cancelled while BasicCegarLoop was constructing difference of abstraction (249states) and interpolant automaton (currently 27 states, 52 states before enhancement), while ReachableStatesComputation was computing reachable states (69 states constructedinput type IntersectNwa). - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 545). Cancelled while BasicCegarLoop was constructing difference of abstraction (249states) and interpolant automaton (currently 27 states, 52 states before enhancement), while ReachableStatesComputation was computing reachable states (69 states constructedinput type IntersectNwa). - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 543). Cancelled while BasicCegarLoop was constructing difference of abstraction (249states) and interpolant automaton (currently 27 states, 52 states before enhancement), while ReachableStatesComputation was computing reachable states (69 states constructedinput type IntersectNwa). - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 545). Cancelled while BasicCegarLoop was constructing difference of abstraction (249states) and interpolant automaton (currently 27 states, 52 states before enhancement), while ReachableStatesComputation was computing reachable states (69 states constructedinput type IntersectNwa). - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 550). Cancelled while BasicCegarLoop was constructing difference of abstraction (249states) and interpolant automaton (currently 27 states, 52 states before enhancement), while ReachableStatesComputation was computing reachable states (69 states constructedinput type IntersectNwa). - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 543). Cancelled while BasicCegarLoop was constructing difference of abstraction (249states) and interpolant automaton (currently 27 states, 52 states before enhancement), while ReachableStatesComputation was computing reachable states (69 states constructedinput type IntersectNwa). - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 545). Cancelled while BasicCegarLoop was constructing difference of abstraction (249states) and interpolant automaton (currently 27 states, 52 states before enhancement), while ReachableStatesComputation was computing reachable states (69 states constructedinput type IntersectNwa). - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 550). Cancelled while BasicCegarLoop was constructing difference of abstraction (249states) and interpolant automaton (currently 27 states, 52 states before enhancement), while ReachableStatesComputation was computing reachable states (69 states constructedinput type IntersectNwa). - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 549). Cancelled while BasicCegarLoop was constructing difference of abstraction (249states) and interpolant automaton (currently 27 states, 52 states before enhancement), while ReachableStatesComputation was computing reachable states (69 states constructedinput type IntersectNwa). - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 545). Cancelled while BasicCegarLoop was constructing difference of abstraction (249states) and interpolant automaton (currently 27 states, 52 states before enhancement), while ReachableStatesComputation was computing reachable states (69 states constructedinput type IntersectNwa). - StatisticsResult: Ultimate Automizer benchmark data CFG has 4 procedures, 96 locations, 15 error locations. TIMEOUT Result, 143.9s OverallTime, 26 OverallIterations, 6 TraceHistogramMax, 124.2s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 2309 SDtfs, 9017 SDslu, 24895 SDs, 0 SdLazy, 13441 SolverSat, 789 SolverUnsat, 1 SolverUnknown, 0 SolverNotchecked, 11.8s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 1358 GetRequests, 512 SyntacticMatches, 4 SemanticMatches, 842 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13060 ImplicationChecksByTransitivity, 125.0s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=249occurred in iteration=25, 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, 0.0s DumpTime, AutomataMinimizationStatistics: 0.2s AutomataMinimizationTime, 25 MinimizatonAttempts, 879 StatesRemovedByMinimization, 19 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.1s SsaConstructionTime, 0.5s SatisfiabilityAnalysisTime, 18.1s InterpolantComputationTime, 1972 NumberOfCodeBlocks, 1969 NumberOfCodeBlocksAsserted, 49 NumberOfCheckSat, 1934 ConstructedInterpolants, 235 QuantifiedInterpolants, 1580625 SizeOfPredicates, 310 NumberOfNonLiveVariables, 2089 ConjunctsInSsa, 670 ConjunctsInUnsatCore, 38 InterpolantComputations, 14 PerfectInterpolantSequences, 14/494 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, ReuseStatistics: No data available RESULT: Ultimate could not prove your program: Timeout Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/cstrncat-alloca_true-valid-memsafety_true-termination.i_svcomp-DerefFreeMemtrack-32bit-Automizer_Camel+AI_EQ_SS.epf_AutomizerC.xml/Csv-Benchmark-0-2018-01-28_21-04-09-813.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/cstrncat-alloca_true-valid-memsafety_true-termination.i_svcomp-DerefFreeMemtrack-32bit-Automizer_Camel+AI_EQ_SS.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-0-2018-01-28_21-04-09-813.csv Completed graceful shutdown