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/cav18-smtinterpol/svcomp-DerefFreeMemtrack-32bit-Automizer_Camel.epf -i ../../../trunk/examples/svcomp/array-memsafety/openbsd_cstrncat-alloca_true-valid-memsafety_true-termination.i -------------------------------------------------------------------------------- This is Ultimate 0.1.23-26d9e06-m [2018-02-02 08:45:31,766 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-02-02 08:45:31,767 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-02-02 08:45:31,778 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-02-02 08:45:31,778 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-02-02 08:45:31,779 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-02-02 08:45:31,780 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-02-02 08:45:31,781 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-02-02 08:45:31,783 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-02-02 08:45:31,784 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-02-02 08:45:31,784 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-02-02 08:45:31,785 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-02-02 08:45:31,785 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-02-02 08:45:31,786 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-02-02 08:45:31,787 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-02-02 08:45:31,789 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-02-02 08:45:31,791 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-02-02 08:45:31,792 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-02-02 08:45:31,793 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-02-02 08:45:31,794 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-02-02 08:45:31,796 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-02-02 08:45:31,796 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-02-02 08:45:31,796 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-02-02 08:45:31,797 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-02-02 08:45:31,798 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-02-02 08:45:31,799 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-02-02 08:45:31,799 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-02-02 08:45:31,799 INFO L177 SettingsManager]: PEA to Boogie provides no preferences, ignoring... [2018-02-02 08:45:31,800 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-02-02 08:45:31,800 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-02-02 08:45:31,800 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-02-02 08:45:31,800 INFO L98 SettingsManager]: Beginning loading settings from /home/ultimate/work/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/cav18-smtinterpol/svcomp-DerefFreeMemtrack-32bit-Automizer_Camel.epf [2018-02-02 08:45:31,810 INFO L110 SettingsManager]: Loading preferences was successful [2018-02-02 08:45:31,810 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-02-02 08:45:31,811 INFO L131 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2018-02-02 08:45:31,811 INFO L133 SettingsManager]: * Create parallel compositions if possible=false [2018-02-02 08:45:31,811 INFO L133 SettingsManager]: * Use SBE=true [2018-02-02 08:45:31,811 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-02-02 08:45:31,812 INFO L133 SettingsManager]: * sizeof long=4 [2018-02-02 08:45:31,812 INFO L133 SettingsManager]: * Check unreachability of error function in SV-COMP mode=false [2018-02-02 08:45:31,812 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-02-02 08:45:31,812 INFO L133 SettingsManager]: * sizeof POINTER=4 [2018-02-02 08:45:31,812 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-02-02 08:45:31,812 INFO L133 SettingsManager]: * Check for the main procedure if all allocated memory was freed=true [2018-02-02 08:45:31,812 INFO L133 SettingsManager]: * Bitprecise bitfields=true [2018-02-02 08:45:31,813 INFO L133 SettingsManager]: * SV-COMP memtrack compatibility mode=true [2018-02-02 08:45:31,813 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-02-02 08:45:31,813 INFO L133 SettingsManager]: * sizeof long double=12 [2018-02-02 08:45:31,813 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-02-02 08:45:31,813 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-02-02 08:45:31,813 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-02-02 08:45:31,813 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-02-02 08:45:31,814 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-02-02 08:45:31,814 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-02-02 08:45:31,814 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-02-02 08:45:31,814 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-02-02 08:45:31,814 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-02-02 08:45:31,841 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-02-02 08:45:31,855 INFO L266 ainManager$Toolchain]: [Toolchain 1]: Parser(s) successfully initialized [2018-02-02 08:45:31,858 INFO L222 ainManager$Toolchain]: [Toolchain 1]: Toolchain data selected. [2018-02-02 08:45:31,860 INFO L271 PluginConnector]: Initializing CDTParser... [2018-02-02 08:45:31,861 INFO L276 PluginConnector]: CDTParser initialized [2018-02-02 08:45:31,861 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /home/ultimate/work/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/array-memsafety/openbsd_cstrncat-alloca_true-valid-memsafety_true-termination.i [2018-02-02 08:45:32,007 INFO L304 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-02-02 08:45:32,008 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2018-02-02 08:45:32,009 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2018-02-02 08:45:32,009 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2018-02-02 08:45:32,013 INFO L276 PluginConnector]: CACSL2BoogieTranslator initialized [2018-02-02 08:45:32,014 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 02.02 08:45:32" (1/1) ... [2018-02-02 08:45:32,016 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@21938c2a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.02 08:45:32, skipping insertion in model container [2018-02-02 08:45:32,017 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 02.02 08:45:32" (1/1) ... [2018-02-02 08:45:32,027 INFO L153 Dispatcher]: Using SV-COMP mode [2018-02-02 08:45:32,055 INFO L153 Dispatcher]: Using SV-COMP mode [2018-02-02 08:45:32,148 INFO L450 PostProcessor]: Settings: Checked method=main [2018-02-02 08:45:32,165 INFO L450 PostProcessor]: Settings: Checked method=main [2018-02-02 08:45:32,171 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.02 08:45:32 WrapperNode [2018-02-02 08:45:32,171 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2018-02-02 08:45:32,171 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-02-02 08:45:32,172 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-02-02 08:45:32,172 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-02-02 08:45:32,183 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.02 08:45:32" (1/1) ... [2018-02-02 08:45:32,183 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.02 08:45:32" (1/1) ... [2018-02-02 08:45:32,190 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.02 08:45:32" (1/1) ... [2018-02-02 08:45:32,191 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.02 08:45:32" (1/1) ... [2018-02-02 08:45:32,194 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.02 08:45:32" (1/1) ... [2018-02-02 08:45:32,196 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.02 08:45:32" (1/1) ... [2018-02-02 08:45:32,198 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.02 08:45:32" (1/1) ... [2018-02-02 08:45:32,199 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-02-02 08:45:32,200 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-02-02 08:45:32,200 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-02-02 08:45:32,200 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-02-02 08:45:32,201 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.02 08:45:32" (1/1) ... No working directory specified, using /home/ultimate/work/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-02-02 08:45:32,237 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2018-02-02 08:45:32,237 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-02-02 08:45:32,237 INFO L136 BoogieDeclarations]: Found implementation of procedure cstrncat [2018-02-02 08:45:32,237 INFO L136 BoogieDeclarations]: Found implementation of procedure main [2018-02-02 08:45:32,237 INFO L128 BoogieDeclarations]: Found specification of procedure write~int [2018-02-02 08:45:32,238 INFO L128 BoogieDeclarations]: Found specification of procedure read~int [2018-02-02 08:45:32,238 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.free [2018-02-02 08:45:32,238 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2018-02-02 08:45:32,238 INFO L128 BoogieDeclarations]: Found specification of procedure #Ultimate.alloc [2018-02-02 08:45:32,238 INFO L128 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2018-02-02 08:45:32,238 INFO L128 BoogieDeclarations]: Found specification of procedure cstrncat [2018-02-02 08:45:32,238 INFO L128 BoogieDeclarations]: Found specification of procedure main [2018-02-02 08:45:32,238 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2018-02-02 08:45:32,238 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-02-02 08:45:32,434 INFO L257 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-02-02 08:45:32,434 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 02.02 08:45:32 BoogieIcfgContainer [2018-02-02 08:45:32,434 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-02-02 08:45:32,435 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-02-02 08:45:32,435 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-02-02 08:45:32,438 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-02-02 08:45:32,438 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 02.02 08:45:32" (1/3) ... [2018-02-02 08:45:32,439 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@46ac36c2 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 02.02 08:45:32, skipping insertion in model container [2018-02-02 08:45:32,439 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.02 08:45:32" (2/3) ... [2018-02-02 08:45:32,439 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@46ac36c2 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 02.02 08:45:32, skipping insertion in model container [2018-02-02 08:45:32,439 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 02.02 08:45:32" (3/3) ... [2018-02-02 08:45:32,441 INFO L107 eAbstractionObserver]: Analyzing ICFG openbsd_cstrncat-alloca_true-valid-memsafety_true-termination.i [2018-02-02 08:45:32,449 INFO L128 ceAbstractionStarter]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-02-02 08:45:32,454 INFO L140 ceAbstractionStarter]: Appying trace abstraction to program that has 13 error locations. [2018-02-02 08:45:32,483 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-02-02 08:45:32,483 INFO L323 AbstractCegarLoop]: Hoare is false [2018-02-02 08:45:32,483 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-02-02 08:45:32,483 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-02-02 08:45:32,484 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-02-02 08:45:32,484 INFO L327 AbstractCegarLoop]: Difference is false [2018-02-02 08:45:32,484 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-02-02 08:45:32,484 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-02-02 08:45:32,485 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-02-02 08:45:32,494 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states. [2018-02-02 08:45:32,502 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2018-02-02 08:45:32,502 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 08:45:32,503 INFO L351 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-02-02 08:45:32,503 INFO L371 AbstractCegarLoop]: === Iteration 1 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 08:45:32,506 INFO L82 PathProgramCache]: Analyzing trace with hash 2055638365, now seen corresponding path program 1 times [2018-02-02 08:45:32,507 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 08:45:32,507 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 08:45:32,538 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 08:45:32,538 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 08:45:32,538 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 08:45:32,572 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 08:45:32,577 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 08:45:32,616 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 08:45:32,619 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-02-02 08:45:32,619 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-02-02 08:45:32,620 INFO L409 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-02-02 08:45:32,630 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-02-02 08:45:32,631 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-02-02 08:45:32,632 INFO L87 Difference]: Start difference. First operand 54 states. Second operand 3 states. [2018-02-02 08:45:32,773 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 08:45:32,773 INFO L93 Difference]: Finished difference Result 55 states and 62 transitions. [2018-02-02 08:45:32,773 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-02-02 08:45:32,775 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 11 [2018-02-02 08:45:32,775 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 08:45:32,784 INFO L225 Difference]: With dead ends: 55 [2018-02-02 08:45:32,784 INFO L226 Difference]: Without dead ends: 51 [2018-02-02 08:45:32,785 INFO L554 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-02-02 08:45:32,800 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2018-02-02 08:45:32,809 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 51. [2018-02-02 08:45:32,810 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 51 states. [2018-02-02 08:45:32,811 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 57 transitions. [2018-02-02 08:45:32,811 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 57 transitions. Word has length 11 [2018-02-02 08:45:32,812 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 08:45:32,812 INFO L432 AbstractCegarLoop]: Abstraction has 51 states and 57 transitions. [2018-02-02 08:45:32,812 INFO L433 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-02-02 08:45:32,812 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 57 transitions. [2018-02-02 08:45:32,812 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2018-02-02 08:45:32,812 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 08:45:32,812 INFO L351 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-02-02 08:45:32,813 INFO L371 AbstractCegarLoop]: === Iteration 2 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 08:45:32,813 INFO L82 PathProgramCache]: Analyzing trace with hash -1872133330, now seen corresponding path program 1 times [2018-02-02 08:45:32,813 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 08:45:32,813 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 08:45:32,814 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 08:45:32,814 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 08:45:32,814 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 08:45:32,824 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 08:45:32,825 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 08:45:32,852 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 08:45:32,852 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-02-02 08:45:32,852 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-02-02 08:45:32,854 INFO L409 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-02-02 08:45:32,854 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-02-02 08:45:32,854 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-02-02 08:45:32,854 INFO L87 Difference]: Start difference. First operand 51 states and 57 transitions. Second operand 5 states. [2018-02-02 08:45:32,913 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 08:45:32,913 INFO L93 Difference]: Finished difference Result 54 states and 61 transitions. [2018-02-02 08:45:32,913 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-02-02 08:45:32,914 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 15 [2018-02-02 08:45:32,914 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 08:45:32,914 INFO L225 Difference]: With dead ends: 54 [2018-02-02 08:45:32,914 INFO L226 Difference]: Without dead ends: 51 [2018-02-02 08:45:32,915 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=25, Unknown=0, NotChecked=0, Total=42 [2018-02-02 08:45:32,915 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2018-02-02 08:45:32,917 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 51. [2018-02-02 08:45:32,917 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 51 states. [2018-02-02 08:45:32,918 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 56 transitions. [2018-02-02 08:45:32,918 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 56 transitions. Word has length 15 [2018-02-02 08:45:32,918 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 08:45:32,918 INFO L432 AbstractCegarLoop]: Abstraction has 51 states and 56 transitions. [2018-02-02 08:45:32,918 INFO L433 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-02-02 08:45:32,918 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 56 transitions. [2018-02-02 08:45:32,919 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2018-02-02 08:45:32,919 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 08:45:32,919 INFO L351 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-02-02 08:45:32,919 INFO L371 AbstractCegarLoop]: === Iteration 3 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 08:45:32,919 INFO L82 PathProgramCache]: Analyzing trace with hash -1192074960, now seen corresponding path program 1 times [2018-02-02 08:45:32,919 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 08:45:32,919 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 08:45:32,920 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 08:45:32,920 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 08:45:32,920 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 08:45:32,933 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 08:45:32,934 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 08:45:32,982 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 08:45:32,982 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-02-02 08:45:32,983 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-02-02 08:45:32,983 INFO L409 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-02-02 08:45:32,983 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-02-02 08:45:32,983 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-02-02 08:45:32,984 INFO L87 Difference]: Start difference. First operand 51 states and 56 transitions. Second operand 4 states. [2018-02-02 08:45:33,023 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 08:45:33,024 INFO L93 Difference]: Finished difference Result 50 states and 55 transitions. [2018-02-02 08:45:33,024 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-02-02 08:45:33,024 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 15 [2018-02-02 08:45:33,025 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 08:45:33,025 INFO L225 Difference]: With dead ends: 50 [2018-02-02 08:45:33,025 INFO L226 Difference]: Without dead ends: 50 [2018-02-02 08:45:33,026 INFO L554 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-02-02 08:45:33,026 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 50 states. [2018-02-02 08:45:33,029 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 50 to 50. [2018-02-02 08:45:33,029 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 50 states. [2018-02-02 08:45:33,030 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 50 states to 50 states and 55 transitions. [2018-02-02 08:45:33,030 INFO L78 Accepts]: Start accepts. Automaton has 50 states and 55 transitions. Word has length 15 [2018-02-02 08:45:33,030 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 08:45:33,030 INFO L432 AbstractCegarLoop]: Abstraction has 50 states and 55 transitions. [2018-02-02 08:45:33,030 INFO L433 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-02-02 08:45:33,031 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 55 transitions. [2018-02-02 08:45:33,031 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2018-02-02 08:45:33,031 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 08:45:33,031 INFO L351 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-02-02 08:45:33,031 INFO L371 AbstractCegarLoop]: === Iteration 4 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 08:45:33,032 INFO L82 PathProgramCache]: Analyzing trace with hash -1192074959, now seen corresponding path program 1 times [2018-02-02 08:45:33,032 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 08:45:33,032 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 08:45:33,032 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 08:45:33,033 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 08:45:33,033 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 08:45:33,044 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 08:45:33,045 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 08:45:33,126 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 08:45:33,126 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-02-02 08:45:33,126 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2018-02-02 08:45:33,126 INFO L409 AbstractCegarLoop]: Interpolant automaton has 8 states [2018-02-02 08:45:33,126 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2018-02-02 08:45:33,127 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=38, Unknown=0, NotChecked=0, Total=56 [2018-02-02 08:45:33,127 INFO L87 Difference]: Start difference. First operand 50 states and 55 transitions. Second operand 8 states. [2018-02-02 08:45:33,229 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 08:45:33,229 INFO L93 Difference]: Finished difference Result 49 states and 54 transitions. [2018-02-02 08:45:33,229 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-02-02 08:45:33,230 INFO L78 Accepts]: Start accepts. Automaton has 8 states. Word has length 15 [2018-02-02 08:45:33,230 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 08:45:33,230 INFO L225 Difference]: With dead ends: 49 [2018-02-02 08:45:33,230 INFO L226 Difference]: Without dead ends: 49 [2018-02-02 08:45:33,231 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=48, Invalid=84, Unknown=0, NotChecked=0, Total=132 [2018-02-02 08:45:33,231 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 49 states. [2018-02-02 08:45:33,233 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 49 to 49. [2018-02-02 08:45:33,234 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 49 states. [2018-02-02 08:45:33,234 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 49 states to 49 states and 54 transitions. [2018-02-02 08:45:33,235 INFO L78 Accepts]: Start accepts. Automaton has 49 states and 54 transitions. Word has length 15 [2018-02-02 08:45:33,235 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 08:45:33,235 INFO L432 AbstractCegarLoop]: Abstraction has 49 states and 54 transitions. [2018-02-02 08:45:33,235 INFO L433 AbstractCegarLoop]: Interpolant automaton has 8 states. [2018-02-02 08:45:33,235 INFO L276 IsEmpty]: Start isEmpty. Operand 49 states and 54 transitions. [2018-02-02 08:45:33,236 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2018-02-02 08:45:33,236 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 08:45:33,236 INFO L351 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-02-02 08:45:33,236 INFO L371 AbstractCegarLoop]: === Iteration 5 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 08:45:33,236 INFO L82 PathProgramCache]: Analyzing trace with hash 1700381909, now seen corresponding path program 1 times [2018-02-02 08:45:33,236 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 08:45:33,236 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 08:45:33,237 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 08:45:33,237 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 08:45:33,237 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 08:45:33,247 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 08:45:33,248 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 08:45:33,269 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 08:45:33,269 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-02-02 08:45:33,269 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-02-02 08:45:33,270 INFO L409 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-02-02 08:45:33,270 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-02-02 08:45:33,270 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-02-02 08:45:33,270 INFO L87 Difference]: Start difference. First operand 49 states and 54 transitions. Second operand 4 states. [2018-02-02 08:45:33,312 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 08:45:33,312 INFO L93 Difference]: Finished difference Result 48 states and 53 transitions. [2018-02-02 08:45:33,313 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-02-02 08:45:33,313 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 16 [2018-02-02 08:45:33,313 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 08:45:33,314 INFO L225 Difference]: With dead ends: 48 [2018-02-02 08:45:33,314 INFO L226 Difference]: Without dead ends: 48 [2018-02-02 08:45:33,315 INFO L554 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-02-02 08:45:33,315 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states. [2018-02-02 08:45:33,317 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 48. [2018-02-02 08:45:33,317 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 48 states. [2018-02-02 08:45:33,318 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 53 transitions. [2018-02-02 08:45:33,318 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 53 transitions. Word has length 16 [2018-02-02 08:45:33,318 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 08:45:33,318 INFO L432 AbstractCegarLoop]: Abstraction has 48 states and 53 transitions. [2018-02-02 08:45:33,318 INFO L433 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-02-02 08:45:33,319 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 53 transitions. [2018-02-02 08:45:33,319 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2018-02-02 08:45:33,319 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 08:45:33,319 INFO L351 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-02-02 08:45:33,319 INFO L371 AbstractCegarLoop]: === Iteration 6 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 08:45:33,320 INFO L82 PathProgramCache]: Analyzing trace with hash 1700381910, now seen corresponding path program 1 times [2018-02-02 08:45:33,320 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 08:45:33,320 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 08:45:33,320 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 08:45:33,320 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 08:45:33,320 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 08:45:33,329 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 08:45:33,330 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 08:45:33,375 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 08:45:33,376 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-02-02 08:45:33,376 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-02-02 08:45:33,376 INFO L409 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-02-02 08:45:33,376 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-02-02 08:45:33,377 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-02-02 08:45:33,377 INFO L87 Difference]: Start difference. First operand 48 states and 53 transitions. Second operand 5 states. [2018-02-02 08:45:33,407 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 08:45:33,407 INFO L93 Difference]: Finished difference Result 47 states and 52 transitions. [2018-02-02 08:45:33,407 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-02-02 08:45:33,407 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 16 [2018-02-02 08:45:33,407 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 08:45:33,408 INFO L225 Difference]: With dead ends: 47 [2018-02-02 08:45:33,408 INFO L226 Difference]: Without dead ends: 47 [2018-02-02 08:45:33,408 INFO L554 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-02-02 08:45:33,409 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2018-02-02 08:45:33,411 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 47. [2018-02-02 08:45:33,411 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 47 states. [2018-02-02 08:45:33,412 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 47 states to 47 states and 52 transitions. [2018-02-02 08:45:33,412 INFO L78 Accepts]: Start accepts. Automaton has 47 states and 52 transitions. Word has length 16 [2018-02-02 08:45:33,412 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 08:45:33,412 INFO L432 AbstractCegarLoop]: Abstraction has 47 states and 52 transitions. [2018-02-02 08:45:33,413 INFO L433 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-02-02 08:45:33,413 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 52 transitions. [2018-02-02 08:45:33,413 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2018-02-02 08:45:33,413 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 08:45:33,413 INFO L351 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-02-02 08:45:33,413 INFO L371 AbstractCegarLoop]: === Iteration 7 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 08:45:33,414 INFO L82 PathProgramCache]: Analyzing trace with hash -275307336, now seen corresponding path program 1 times [2018-02-02 08:45:33,414 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 08:45:33,414 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 08:45:33,415 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 08:45:33,415 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 08:45:33,415 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 08:45:33,426 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 08:45:33,427 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 08:45:33,460 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 08:45:33,460 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-02-02 08:45:33,460 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-02-02 08:45:33,461 INFO L409 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-02-02 08:45:33,461 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-02-02 08:45:33,461 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2018-02-02 08:45:33,461 INFO L87 Difference]: Start difference. First operand 47 states and 52 transitions. Second operand 6 states. [2018-02-02 08:45:33,559 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 08:45:33,559 INFO L93 Difference]: Finished difference Result 47 states and 52 transitions. [2018-02-02 08:45:33,560 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-02-02 08:45:33,560 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 21 [2018-02-02 08:45:33,560 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 08:45:33,562 INFO L225 Difference]: With dead ends: 47 [2018-02-02 08:45:33,562 INFO L226 Difference]: Without dead ends: 47 [2018-02-02 08:45:33,563 INFO L554 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-02-02 08:45:33,563 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2018-02-02 08:45:33,565 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 44. [2018-02-02 08:45:33,565 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 44 states. [2018-02-02 08:45:33,565 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 44 states to 44 states and 49 transitions. [2018-02-02 08:45:33,566 INFO L78 Accepts]: Start accepts. Automaton has 44 states and 49 transitions. Word has length 21 [2018-02-02 08:45:33,566 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 08:45:33,566 INFO L432 AbstractCegarLoop]: Abstraction has 44 states and 49 transitions. [2018-02-02 08:45:33,566 INFO L433 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-02-02 08:45:33,566 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 49 transitions. [2018-02-02 08:45:33,566 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2018-02-02 08:45:33,567 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 08:45:33,567 INFO L351 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-02-02 08:45:33,567 INFO L371 AbstractCegarLoop]: === Iteration 8 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 08:45:33,567 INFO L82 PathProgramCache]: Analyzing trace with hash -275307335, now seen corresponding path program 1 times [2018-02-02 08:45:33,567 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 08:45:33,567 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 08:45:33,568 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 08:45:33,568 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 08:45:33,568 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 08:45:33,577 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 08:45:33,578 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 08:45:33,699 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 08:45:33,700 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-02-02 08:45:33,700 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2018-02-02 08:45:33,700 INFO L409 AbstractCegarLoop]: Interpolant automaton has 10 states [2018-02-02 08:45:33,700 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2018-02-02 08:45:33,700 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=71, Unknown=0, NotChecked=0, Total=90 [2018-02-02 08:45:33,701 INFO L87 Difference]: Start difference. First operand 44 states and 49 transitions. Second operand 10 states. [2018-02-02 08:45:33,851 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 08:45:33,851 INFO L93 Difference]: Finished difference Result 57 states and 64 transitions. [2018-02-02 08:45:33,851 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-02-02 08:45:33,852 INFO L78 Accepts]: Start accepts. Automaton has 10 states. Word has length 21 [2018-02-02 08:45:33,852 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 08:45:33,852 INFO L225 Difference]: With dead ends: 57 [2018-02-02 08:45:33,852 INFO L226 Difference]: Without dead ends: 57 [2018-02-02 08:45:33,852 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 16 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 25 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=65, Invalid=207, Unknown=0, NotChecked=0, Total=272 [2018-02-02 08:45:33,853 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 57 states. [2018-02-02 08:45:33,854 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 57 to 52. [2018-02-02 08:45:33,854 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 52 states. [2018-02-02 08:45:33,855 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 52 states to 52 states and 61 transitions. [2018-02-02 08:45:33,855 INFO L78 Accepts]: Start accepts. Automaton has 52 states and 61 transitions. Word has length 21 [2018-02-02 08:45:33,855 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 08:45:33,855 INFO L432 AbstractCegarLoop]: Abstraction has 52 states and 61 transitions. [2018-02-02 08:45:33,855 INFO L433 AbstractCegarLoop]: Interpolant automaton has 10 states. [2018-02-02 08:45:33,855 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 61 transitions. [2018-02-02 08:45:33,855 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2018-02-02 08:45:33,855 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 08:45:33,855 INFO L351 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-02-02 08:45:33,856 INFO L371 AbstractCegarLoop]: === Iteration 9 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 08:45:33,856 INFO L82 PathProgramCache]: Analyzing trace with hash 1706718631, now seen corresponding path program 1 times [2018-02-02 08:45:33,856 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 08:45:33,856 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 08:45:33,856 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 08:45:33,856 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 08:45:33,856 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 08:45:33,864 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 08:45:33,865 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 08:45:33,899 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 08:45:33,899 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-02-02 08:45:33,899 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2018-02-02 08:45:33,899 INFO L409 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-02-02 08:45:33,899 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-02-02 08:45:33,899 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2018-02-02 08:45:33,899 INFO L87 Difference]: Start difference. First operand 52 states and 61 transitions. Second operand 7 states. [2018-02-02 08:45:33,956 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 08:45:33,956 INFO L93 Difference]: Finished difference Result 54 states and 62 transitions. [2018-02-02 08:45:33,957 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-02-02 08:45:33,957 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 24 [2018-02-02 08:45:33,957 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 08:45:33,957 INFO L225 Difference]: With dead ends: 54 [2018-02-02 08:45:33,957 INFO L226 Difference]: Without dead ends: 54 [2018-02-02 08:45:33,957 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 9 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=29, Invalid=61, Unknown=0, NotChecked=0, Total=90 [2018-02-02 08:45:33,958 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2018-02-02 08:45:33,959 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 51. [2018-02-02 08:45:33,959 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 51 states. [2018-02-02 08:45:33,960 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 59 transitions. [2018-02-02 08:45:33,960 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 59 transitions. Word has length 24 [2018-02-02 08:45:33,960 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 08:45:33,961 INFO L432 AbstractCegarLoop]: Abstraction has 51 states and 59 transitions. [2018-02-02 08:45:33,961 INFO L433 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-02-02 08:45:33,961 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 59 transitions. [2018-02-02 08:45:33,961 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2018-02-02 08:45:33,961 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 08:45:33,961 INFO L351 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-02-02 08:45:33,962 INFO L371 AbstractCegarLoop]: === Iteration 10 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 08:45:33,962 INFO L82 PathProgramCache]: Analyzing trace with hash 1706718632, now seen corresponding path program 1 times [2018-02-02 08:45:33,962 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 08:45:33,962 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 08:45:33,963 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 08:45:33,963 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 08:45:33,963 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 08:45:33,972 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 08:45:33,973 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 08:45:34,058 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 08:45:34,058 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-02-02 08:45:34,058 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2018-02-02 08:45:34,059 INFO L409 AbstractCegarLoop]: Interpolant automaton has 10 states [2018-02-02 08:45:34,059 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2018-02-02 08:45:34,059 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=70, Unknown=0, NotChecked=0, Total=90 [2018-02-02 08:45:34,059 INFO L87 Difference]: Start difference. First operand 51 states and 59 transitions. Second operand 10 states. [2018-02-02 08:45:34,153 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 08:45:34,154 INFO L93 Difference]: Finished difference Result 56 states and 64 transitions. [2018-02-02 08:45:34,154 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-02-02 08:45:34,154 INFO L78 Accepts]: Start accepts. Automaton has 10 states. Word has length 24 [2018-02-02 08:45:34,154 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 08:45:34,154 INFO L225 Difference]: With dead ends: 56 [2018-02-02 08:45:34,155 INFO L226 Difference]: Without dead ends: 56 [2018-02-02 08:45:34,155 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 24 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=42, Invalid=140, Unknown=0, NotChecked=0, Total=182 [2018-02-02 08:45:34,155 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 56 states. [2018-02-02 08:45:34,156 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 56 to 53. [2018-02-02 08:45:34,156 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 53 states. [2018-02-02 08:45:34,157 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 53 states to 53 states and 60 transitions. [2018-02-02 08:45:34,157 INFO L78 Accepts]: Start accepts. Automaton has 53 states and 60 transitions. Word has length 24 [2018-02-02 08:45:34,157 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 08:45:34,157 INFO L432 AbstractCegarLoop]: Abstraction has 53 states and 60 transitions. [2018-02-02 08:45:34,157 INFO L433 AbstractCegarLoop]: Interpolant automaton has 10 states. [2018-02-02 08:45:34,157 INFO L276 IsEmpty]: Start isEmpty. Operand 53 states and 60 transitions. [2018-02-02 08:45:34,158 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2018-02-02 08:45:34,158 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 08:45:34,158 INFO L351 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-02-02 08:45:34,158 INFO L371 AbstractCegarLoop]: === Iteration 11 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 08:45:34,158 INFO L82 PathProgramCache]: Analyzing trace with hash 1706720075, now seen corresponding path program 1 times [2018-02-02 08:45:34,158 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 08:45:34,158 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 08:45:34,159 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 08:45:34,159 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 08:45:34,159 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 08:45:34,168 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 08:45:34,169 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 08:45:34,295 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 08:45:34,296 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-02-02 08:45:34,296 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /home/ultimate/work/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-02-02 08:45:34,303 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 08:45:34,324 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 08:45:34,332 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-02-02 08:45:34,402 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-02-02 08:45:34,404 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-02-02 08:45:34,413 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-02-02 08:45:34,413 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 08:45:34,420 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 08:45:34,421 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:24, output treesize:19 [2018-02-02 08:45:34,452 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 08:45:34,453 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 08:45:34,455 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-02-02 08:45:34,456 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-02-02 08:45:34,465 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 08:45:34,465 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 08:45:34,466 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-02-02 08:45:34,466 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 08:45:34,471 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 08:45:34,471 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:30, output treesize:18 [2018-02-02 08:45:34,646 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 08:45:34,664 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-02-02 08:45:34,664 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 13] total 23 [2018-02-02 08:45:34,664 INFO L409 AbstractCegarLoop]: Interpolant automaton has 24 states [2018-02-02 08:45:34,665 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2018-02-02 08:45:34,665 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=61, Invalid=491, Unknown=0, NotChecked=0, Total=552 [2018-02-02 08:45:34,665 INFO L87 Difference]: Start difference. First operand 53 states and 60 transitions. Second operand 24 states. [2018-02-02 08:45:35,180 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 08:45:35,180 INFO L93 Difference]: Finished difference Result 72 states and 82 transitions. [2018-02-02 08:45:35,180 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-02-02 08:45:35,181 INFO L78 Accepts]: Start accepts. Automaton has 24 states. Word has length 24 [2018-02-02 08:45:35,181 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 08:45:35,181 INFO L225 Difference]: With dead ends: 72 [2018-02-02 08:45:35,181 INFO L226 Difference]: Without dead ends: 72 [2018-02-02 08:45:35,182 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 45 GetRequests, 13 SyntacticMatches, 0 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 192 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=169, Invalid=953, Unknown=0, NotChecked=0, Total=1122 [2018-02-02 08:45:35,182 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 72 states. [2018-02-02 08:45:35,184 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 72 to 64. [2018-02-02 08:45:35,184 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 64 states. [2018-02-02 08:45:35,184 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 64 states to 64 states and 75 transitions. [2018-02-02 08:45:35,185 INFO L78 Accepts]: Start accepts. Automaton has 64 states and 75 transitions. Word has length 24 [2018-02-02 08:45:35,185 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 08:45:35,185 INFO L432 AbstractCegarLoop]: Abstraction has 64 states and 75 transitions. [2018-02-02 08:45:35,185 INFO L433 AbstractCegarLoop]: Interpolant automaton has 24 states. [2018-02-02 08:45:35,185 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 75 transitions. [2018-02-02 08:45:35,185 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2018-02-02 08:45:35,185 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 08:45:35,186 INFO L351 BasicCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-02-02 08:45:35,186 INFO L371 AbstractCegarLoop]: === Iteration 12 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 08:45:35,186 INFO L82 PathProgramCache]: Analyzing trace with hash 1074905977, now seen corresponding path program 2 times [2018-02-02 08:45:35,186 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 08:45:35,186 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 08:45:35,187 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 08:45:35,187 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 08:45:35,187 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 08:45:35,200 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 08:45:35,201 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 08:45:35,477 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 08:45:35,477 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-02-02 08:45:35,477 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /home/ultimate/work/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-02-02 08:45:35,483 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-02-02 08:45:35,493 INFO L201 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-02-02 08:45:35,497 INFO L214 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-02-02 08:45:35,498 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-02-02 08:45:35,501 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-02-02 08:45:35,522 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-02-02 08:45:35,522 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-02-02 08:45:35,525 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 08:45:35,525 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:18, output treesize:17 [2018-02-02 08:45:35,568 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 08:45:35,569 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 08:45:35,569 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-02-02 08:45:35,570 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-02-02 08:45:35,573 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 08:45:35,574 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:22, output treesize:16 [2018-02-02 08:45:35,607 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 14 [2018-02-02 08:45:35,609 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 13 [2018-02-02 08:45:35,609 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 08:45:35,610 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 08:45:35,616 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-02-02 08:45:35,616 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:42, output treesize:38 [2018-02-02 08:45:35,646 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 28 treesize of output 29 [2018-02-02 08:45:35,648 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-02-02 08:45:35,648 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 08:45:35,651 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 08:45:35,659 INFO L267 ElimStorePlain]: Start of recursive call 1: 5 dim-0 vars, 1 dim-2 vars, End of recursive call: 5 dim-0 vars, and 1 xjuncts. [2018-02-02 08:45:35,659 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 6 variables, input treesize:52, output treesize:48 [2018-02-02 08:45:35,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 41 treesize of output 37 [2018-02-02 08:45:35,999 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 08:45:36,004 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 3 disjoint index pairs (out of 3 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 25 treesize of output 37 [2018-02-02 08:45:36,005 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-02-02 08:45:36,039 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2018-02-02 08:45:36,039 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-02-02 08:45:36,045 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-02-02 08:45:36,057 INFO L267 ElimStorePlain]: Start of recursive call 1: 5 dim-0 vars, 1 dim-2 vars, End of recursive call: and 2 xjuncts. [2018-02-02 08:45:36,058 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 6 variables, input treesize:66, output treesize:43 [2018-02-02 08:45:36,103 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 2 proven. 5 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 08:45:36,121 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-02-02 08:45:36,121 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 16] total 27 [2018-02-02 08:45:36,122 INFO L409 AbstractCegarLoop]: Interpolant automaton has 28 states [2018-02-02 08:45:36,122 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2018-02-02 08:45:36,122 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=68, Invalid=688, Unknown=0, NotChecked=0, Total=756 [2018-02-02 08:45:36,122 INFO L87 Difference]: Start difference. First operand 64 states and 75 transitions. Second operand 28 states. [2018-02-02 08:45:36,814 WARN L146 SmtUtils]: Spent 120ms on a formula simplification. DAG size of input: 80 DAG size of output 77 [2018-02-02 08:45:41,155 WARN L146 SmtUtils]: Spent 286ms on a formula simplification. DAG size of input: 83 DAG size of output 79 [2018-02-02 08:45:48,341 WARN L146 SmtUtils]: Spent 2100ms on a formula simplification. DAG size of input: 83 DAG size of output 74 [2018-02-02 08:45:59,829 WARN L146 SmtUtils]: Spent 6140ms on a formula simplification. DAG size of input: 90 DAG size of output 72 [2018-02-02 08:46:03,836 WARN L146 SmtUtils]: Spent 118ms on a formula simplification. DAG size of input: 57 DAG size of output 46 [2018-02-02 08:46:04,072 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 08:46:04,072 INFO L93 Difference]: Finished difference Result 110 states and 123 transitions. [2018-02-02 08:46:04,072 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 32 states. [2018-02-02 08:46:04,072 INFO L78 Accepts]: Start accepts. Automaton has 28 states. Word has length 27 [2018-02-02 08:46:04,072 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 08:46:04,073 INFO L225 Difference]: With dead ends: 110 [2018-02-02 08:46:04,073 INFO L226 Difference]: Without dead ends: 110 [2018-02-02 08:46:04,074 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 70 GetRequests, 14 SyntacticMatches, 1 SemanticMatches, 55 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 613 ImplicationChecksByTransitivity, 16.4s TimeCoverageRelationStatistics Valid=442, Invalid=2748, Unknown=2, NotChecked=0, Total=3192 [2018-02-02 08:46:04,074 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 110 states. [2018-02-02 08:46:04,077 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 110 to 61. [2018-02-02 08:46:04,077 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 61 states. [2018-02-02 08:46:04,078 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 61 states to 61 states and 72 transitions. [2018-02-02 08:46:04,078 INFO L78 Accepts]: Start accepts. Automaton has 61 states and 72 transitions. Word has length 27 [2018-02-02 08:46:04,078 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 08:46:04,078 INFO L432 AbstractCegarLoop]: Abstraction has 61 states and 72 transitions. [2018-02-02 08:46:04,078 INFO L433 AbstractCegarLoop]: Interpolant automaton has 28 states. [2018-02-02 08:46:04,078 INFO L276 IsEmpty]: Start isEmpty. Operand 61 states and 72 transitions. [2018-02-02 08:46:04,079 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2018-02-02 08:46:04,079 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 08:46:04,079 INFO L351 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-02-02 08:46:04,079 INFO L371 AbstractCegarLoop]: === Iteration 13 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 08:46:04,079 INFO L82 PathProgramCache]: Analyzing trace with hash 94248296, now seen corresponding path program 1 times [2018-02-02 08:46:04,079 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 08:46:04,080 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 08:46:04,080 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 08:46:04,080 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-02-02 08:46:04,080 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 08:46:04,088 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 08:46:04,088 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 08:46:04,125 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 08:46:04,125 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-02-02 08:46:04,125 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-02-02 08:46:04,126 INFO L409 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-02-02 08:46:04,126 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-02-02 08:46:04,126 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-02-02 08:46:04,126 INFO L87 Difference]: Start difference. First operand 61 states and 72 transitions. Second operand 5 states. [2018-02-02 08:46:04,154 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 08:46:04,154 INFO L93 Difference]: Finished difference Result 86 states and 99 transitions. [2018-02-02 08:46:04,154 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-02-02 08:46:04,154 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 28 [2018-02-02 08:46:04,154 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 08:46:04,155 INFO L225 Difference]: With dead ends: 86 [2018-02-02 08:46:04,155 INFO L226 Difference]: Without dead ends: 86 [2018-02-02 08:46:04,155 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2018-02-02 08:46:04,156 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 86 states. [2018-02-02 08:46:04,160 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 86 to 72. [2018-02-02 08:46:04,161 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 72 states. [2018-02-02 08:46:04,161 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 72 states to 72 states and 84 transitions. [2018-02-02 08:46:04,161 INFO L78 Accepts]: Start accepts. Automaton has 72 states and 84 transitions. Word has length 28 [2018-02-02 08:46:04,162 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 08:46:04,162 INFO L432 AbstractCegarLoop]: Abstraction has 72 states and 84 transitions. [2018-02-02 08:46:04,162 INFO L433 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-02-02 08:46:04,162 INFO L276 IsEmpty]: Start isEmpty. Operand 72 states and 84 transitions. [2018-02-02 08:46:04,163 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2018-02-02 08:46:04,163 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 08:46:04,163 INFO L351 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-02-02 08:46:04,163 INFO L371 AbstractCegarLoop]: === Iteration 14 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 08:46:04,163 INFO L82 PathProgramCache]: Analyzing trace with hash -723400154, now seen corresponding path program 1 times [2018-02-02 08:46:04,163 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 08:46:04,163 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 08:46:04,164 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 08:46:04,164 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 08:46:04,164 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 08:46:04,174 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 08:46:04,175 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 08:46:04,220 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 08:46:04,220 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-02-02 08:46:04,220 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-02-02 08:46:04,220 INFO L409 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-02-02 08:46:04,220 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-02-02 08:46:04,221 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2018-02-02 08:46:04,221 INFO L87 Difference]: Start difference. First operand 72 states and 84 transitions. Second operand 6 states. [2018-02-02 08:46:04,299 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 08:46:04,299 INFO L93 Difference]: Finished difference Result 71 states and 83 transitions. [2018-02-02 08:46:04,299 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-02-02 08:46:04,299 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 28 [2018-02-02 08:46:04,299 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 08:46:04,300 INFO L225 Difference]: With dead ends: 71 [2018-02-02 08:46:04,300 INFO L226 Difference]: Without dead ends: 58 [2018-02-02 08:46:04,300 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2018-02-02 08:46:04,300 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 58 states. [2018-02-02 08:46:04,301 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 58 to 50. [2018-02-02 08:46:04,302 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 50 states. [2018-02-02 08:46:04,302 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 50 states to 50 states and 57 transitions. [2018-02-02 08:46:04,302 INFO L78 Accepts]: Start accepts. Automaton has 50 states and 57 transitions. Word has length 28 [2018-02-02 08:46:04,302 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 08:46:04,302 INFO L432 AbstractCegarLoop]: Abstraction has 50 states and 57 transitions. [2018-02-02 08:46:04,303 INFO L433 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-02-02 08:46:04,303 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 57 transitions. [2018-02-02 08:46:04,303 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2018-02-02 08:46:04,303 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 08:46:04,303 INFO L351 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-02-02 08:46:04,303 INFO L371 AbstractCegarLoop]: === Iteration 15 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 08:46:04,304 INFO L82 PathProgramCache]: Analyzing trace with hash -1208652779, now seen corresponding path program 1 times [2018-02-02 08:46:04,304 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 08:46:04,304 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 08:46:04,304 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 08:46:04,304 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 08:46:04,305 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 08:46:04,315 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 08:46:04,316 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 08:46:04,414 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 08:46:04,414 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-02-02 08:46:04,414 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2018-02-02 08:46:04,414 INFO L409 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-02-02 08:46:04,415 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-02-02 08:46:04,415 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2018-02-02 08:46:04,415 INFO L87 Difference]: Start difference. First operand 50 states and 57 transitions. Second operand 7 states. [2018-02-02 08:46:04,473 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 08:46:04,473 INFO L93 Difference]: Finished difference Result 83 states and 91 transitions. [2018-02-02 08:46:04,474 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-02-02 08:46:04,474 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 30 [2018-02-02 08:46:04,474 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 08:46:04,474 INFO L225 Difference]: With dead ends: 83 [2018-02-02 08:46:04,474 INFO L226 Difference]: Without dead ends: 77 [2018-02-02 08:46:04,475 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2018-02-02 08:46:04,475 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 77 states. [2018-02-02 08:46:04,476 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 77 to 75. [2018-02-02 08:46:04,477 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 75 states. [2018-02-02 08:46:04,477 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 75 states to 75 states and 83 transitions. [2018-02-02 08:46:04,477 INFO L78 Accepts]: Start accepts. Automaton has 75 states and 83 transitions. Word has length 30 [2018-02-02 08:46:04,477 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 08:46:04,477 INFO L432 AbstractCegarLoop]: Abstraction has 75 states and 83 transitions. [2018-02-02 08:46:04,478 INFO L433 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-02-02 08:46:04,478 INFO L276 IsEmpty]: Start isEmpty. Operand 75 states and 83 transitions. [2018-02-02 08:46:04,478 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2018-02-02 08:46:04,478 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 08:46:04,479 INFO L351 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-02-02 08:46:04,479 INFO L371 AbstractCegarLoop]: === Iteration 16 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 08:46:04,479 INFO L82 PathProgramCache]: Analyzing trace with hash -989798061, now seen corresponding path program 1 times [2018-02-02 08:46:04,479 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 08:46:04,479 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 08:46:04,480 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 08:46:04,480 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 08:46:04,480 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 08:46:04,492 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 08:46:04,493 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 08:46:04,635 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 08:46:04,636 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-02-02 08:46:04,636 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /home/ultimate/work/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-02-02 08:46:04,641 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 08:46:04,657 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 08:46:04,659 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-02-02 08:46:04,665 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-02-02 08:46:04,667 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-02-02 08:46:04,667 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 08:46:04,668 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 08:46:04,672 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-02-02 08:46:04,672 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:25, output treesize:21 [2018-02-02 08:46:04,784 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-02-02 08:46:04,790 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-02-02 08:46:04,790 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-02-02 08:46:04,793 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-02-02 08:46:04,799 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: and 2 xjuncts. [2018-02-02 08:46:04,799 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:38, output treesize:29 [2018-02-02 08:46:04,843 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 08:46:04,861 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-02-02 08:46:04,861 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 10] total 18 [2018-02-02 08:46:04,861 INFO L409 AbstractCegarLoop]: Interpolant automaton has 19 states [2018-02-02 08:46:04,861 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2018-02-02 08:46:04,861 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=40, Invalid=302, Unknown=0, NotChecked=0, Total=342 [2018-02-02 08:46:04,861 INFO L87 Difference]: Start difference. First operand 75 states and 83 transitions. Second operand 19 states. [2018-02-02 08:46:05,273 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 08:46:05,273 INFO L93 Difference]: Finished difference Result 86 states and 94 transitions. [2018-02-02 08:46:05,274 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-02-02 08:46:05,274 INFO L78 Accepts]: Start accepts. Automaton has 19 states. Word has length 30 [2018-02-02 08:46:05,274 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 08:46:05,274 INFO L225 Difference]: With dead ends: 86 [2018-02-02 08:46:05,274 INFO L226 Difference]: Without dead ends: 86 [2018-02-02 08:46:05,275 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 49 GetRequests, 24 SyntacticMatches, 0 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 77 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=103, Invalid=599, Unknown=0, NotChecked=0, Total=702 [2018-02-02 08:46:05,275 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 86 states. [2018-02-02 08:46:05,276 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 86 to 81. [2018-02-02 08:46:05,276 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 81 states. [2018-02-02 08:46:05,276 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 81 states to 81 states and 89 transitions. [2018-02-02 08:46:05,276 INFO L78 Accepts]: Start accepts. Automaton has 81 states and 89 transitions. Word has length 30 [2018-02-02 08:46:05,276 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 08:46:05,276 INFO L432 AbstractCegarLoop]: Abstraction has 81 states and 89 transitions. [2018-02-02 08:46:05,276 INFO L433 AbstractCegarLoop]: Interpolant automaton has 19 states. [2018-02-02 08:46:05,277 INFO L276 IsEmpty]: Start isEmpty. Operand 81 states and 89 transitions. [2018-02-02 08:46:05,277 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2018-02-02 08:46:05,277 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 08:46:05,277 INFO L351 BasicCegarLoop]: trace histogram [3, 3, 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] [2018-02-02 08:46:05,277 INFO L371 AbstractCegarLoop]: === Iteration 17 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 08:46:05,277 INFO L82 PathProgramCache]: Analyzing trace with hash -1959345908, now seen corresponding path program 1 times [2018-02-02 08:46:05,277 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 08:46:05,277 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 08:46:05,278 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 08:46:05,278 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 08:46:05,278 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 08:46:05,287 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 08:46:05,287 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 08:46:05,820 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 0 proven. 9 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 08:46:05,820 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-02-02 08:46:05,820 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /home/ultimate/work/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-02-02 08:46:05,825 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 08:46:05,837 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 08:46:05,840 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-02-02 08:46:05,844 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-02-02 08:46:05,844 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-02-02 08:46:05,852 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-02-02 08:46:05,853 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 08:46:05,860 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 08:46:05,860 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:22, output treesize:20 [2018-02-02 08:46:05,885 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 08:46:05,886 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-02-02 08:46:05,887 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-02-02 08:46:05,899 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 08:46:05,900 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 08:46:05,900 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-02-02 08:46:05,900 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 08:46:05,906 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 08:46:05,906 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:31, output treesize:24 [2018-02-02 08:46:05,948 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 15 [2018-02-02 08:46:05,949 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 14 [2018-02-02 08:46:05,949 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 08:46:05,951 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 08:46:05,955 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-02-02 08:46:05,956 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:34, output treesize:30 [2018-02-02 08:46:05,980 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-02-02 08:46:05,982 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-02-02 08:46:05,982 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 08:46:05,985 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 08:46:05,991 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-02-02 08:46:05,991 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:41, output treesize:37 [2018-02-02 08:46:06,244 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-02-02 08:46:06,246 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-02-02 08:46:06,246 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 08:46:06,254 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-02-02 08:46:06,254 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 2 xjuncts. [2018-02-02 08:46:06,258 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-02-02 08:46:06,264 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-2 vars, End of recursive call: and 2 xjuncts. [2018-02-02 08:46:06,264 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 4 variables, input treesize:47, output treesize:27 [2018-02-02 08:46:06,399 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 2 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 08:46:06,417 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-02-02 08:46:06,417 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 17] total 29 [2018-02-02 08:46:06,418 INFO L409 AbstractCegarLoop]: Interpolant automaton has 30 states [2018-02-02 08:46:06,418 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2018-02-02 08:46:06,418 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=76, Invalid=794, Unknown=0, NotChecked=0, Total=870 [2018-02-02 08:46:06,418 INFO L87 Difference]: Start difference. First operand 81 states and 89 transitions. Second operand 30 states. [2018-02-02 08:46:07,443 WARN L146 SmtUtils]: Spent 321ms on a formula simplification. DAG size of input: 84 DAG size of output 61 [2018-02-02 08:46:08,213 WARN L146 SmtUtils]: Spent 410ms on a formula simplification. DAG size of input: 74 DAG size of output 54 [2018-02-02 08:46:08,514 WARN L146 SmtUtils]: Spent 117ms on a formula simplification. DAG size of input: 87 DAG size of output 60 [2018-02-02 08:46:08,704 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 08:46:08,704 INFO L93 Difference]: Finished difference Result 89 states and 97 transitions. [2018-02-02 08:46:08,704 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2018-02-02 08:46:08,704 INFO L78 Accepts]: Start accepts. Automaton has 30 states. Word has length 35 [2018-02-02 08:46:08,704 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 08:46:08,705 INFO L225 Difference]: With dead ends: 89 [2018-02-02 08:46:08,705 INFO L226 Difference]: Without dead ends: 56 [2018-02-02 08:46:08,705 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 68 GetRequests, 19 SyntacticMatches, 3 SemanticMatches, 46 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 359 ImplicationChecksByTransitivity, 2.6s TimeCoverageRelationStatistics Valid=310, Invalid=1946, Unknown=0, NotChecked=0, Total=2256 [2018-02-02 08:46:08,705 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 56 states. [2018-02-02 08:46:08,706 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 56 to 56. [2018-02-02 08:46:08,706 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 56 states. [2018-02-02 08:46:08,707 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 56 states to 56 states and 62 transitions. [2018-02-02 08:46:08,707 INFO L78 Accepts]: Start accepts. Automaton has 56 states and 62 transitions. Word has length 35 [2018-02-02 08:46:08,707 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 08:46:08,707 INFO L432 AbstractCegarLoop]: Abstraction has 56 states and 62 transitions. [2018-02-02 08:46:08,707 INFO L433 AbstractCegarLoop]: Interpolant automaton has 30 states. [2018-02-02 08:46:08,707 INFO L276 IsEmpty]: Start isEmpty. Operand 56 states and 62 transitions. [2018-02-02 08:46:08,707 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2018-02-02 08:46:08,707 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 08:46:08,708 INFO L351 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-02-02 08:46:08,708 INFO L371 AbstractCegarLoop]: === Iteration 18 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 08:46:08,708 INFO L82 PathProgramCache]: Analyzing trace with hash -608695935, now seen corresponding path program 1 times [2018-02-02 08:46:08,708 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 08:46:08,708 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 08:46:08,709 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 08:46:08,709 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 08:46:08,709 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 08:46:08,715 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 08:46:08,715 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 08:46:08,918 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 08:46:08,918 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-02-02 08:46:08,918 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /home/ultimate/work/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-02-02 08:46:08,923 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 08:46:08,938 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 08:46:08,940 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-02-02 08:46:08,955 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-02-02 08:46:08,955 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-02-02 08:46:08,960 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-02-02 08:46:08,960 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 08:46:08,964 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 08:46:08,964 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:21, output treesize:16 [2018-02-02 08:46:08,993 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 08:46:08,994 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 08:46:08,994 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 4 [2018-02-02 08:46:08,994 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-02-02 08:46:08,999 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 08:46:09,000 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-02-02 08:46:09,000 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 08:46:09,005 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 08:46:09,005 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:27, output treesize:13 [2018-02-02 08:46:09,261 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 08:46:09,279 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-02-02 08:46:09,279 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 17] total 32 [2018-02-02 08:46:09,279 INFO L409 AbstractCegarLoop]: Interpolant automaton has 33 states [2018-02-02 08:46:09,279 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2018-02-02 08:46:09,280 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=91, Invalid=965, Unknown=0, NotChecked=0, Total=1056 [2018-02-02 08:46:09,280 INFO L87 Difference]: Start difference. First operand 56 states and 62 transitions. Second operand 33 states. [2018-02-02 08:46:09,752 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 08:46:09,752 INFO L93 Difference]: Finished difference Result 74 states and 81 transitions. [2018-02-02 08:46:09,753 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2018-02-02 08:46:09,753 INFO L78 Accepts]: Start accepts. Automaton has 33 states. Word has length 35 [2018-02-02 08:46:09,753 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 08:46:09,753 INFO L225 Difference]: With dead ends: 74 [2018-02-02 08:46:09,753 INFO L226 Difference]: Without dead ends: 73 [2018-02-02 08:46:09,754 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 64 GetRequests, 21 SyntacticMatches, 0 SemanticMatches, 43 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 402 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=217, Invalid=1763, Unknown=0, NotChecked=0, Total=1980 [2018-02-02 08:46:09,754 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 73 states. [2018-02-02 08:46:09,755 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 73 to 70. [2018-02-02 08:46:09,755 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 70 states. [2018-02-02 08:46:09,756 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 70 states to 70 states and 77 transitions. [2018-02-02 08:46:09,756 INFO L78 Accepts]: Start accepts. Automaton has 70 states and 77 transitions. Word has length 35 [2018-02-02 08:46:09,756 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 08:46:09,756 INFO L432 AbstractCegarLoop]: Abstraction has 70 states and 77 transitions. [2018-02-02 08:46:09,756 INFO L433 AbstractCegarLoop]: Interpolant automaton has 33 states. [2018-02-02 08:46:09,756 INFO L276 IsEmpty]: Start isEmpty. Operand 70 states and 77 transitions. [2018-02-02 08:46:09,757 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2018-02-02 08:46:09,757 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 08:46:09,757 INFO L351 BasicCegarLoop]: trace histogram [3, 3, 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] [2018-02-02 08:46:09,757 INFO L371 AbstractCegarLoop]: === Iteration 19 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 08:46:09,757 INFO L82 PathProgramCache]: Analyzing trace with hash -36117874, now seen corresponding path program 1 times [2018-02-02 08:46:09,758 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 08:46:09,758 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 08:46:09,758 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 08:46:09,763 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 08:46:09,763 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 08:46:09,773 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 08:46:09,774 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 08:46:10,314 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 0 proven. 9 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 08:46:10,315 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-02-02 08:46:10,315 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /home/ultimate/work/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-02-02 08:46:10,319 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 08:46:10,335 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 08:46:10,337 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-02-02 08:46:10,339 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-02-02 08:46:10,339 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-02-02 08:46:10,346 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-02-02 08:46:10,346 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 08:46:10,351 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 08:46:10,351 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:27, output treesize:25 [2018-02-02 08:46:10,395 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 08:46:10,395 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 08:46:10,396 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-02-02 08:46:10,396 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-02-02 08:46:10,402 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 08:46:10,402 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-02-02 08:46:10,402 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 08:46:10,408 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 08:46:10,408 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:36, output treesize:25 [2018-02-02 08:46:10,450 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-02-02 08:46:10,451 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-02-02 08:46:10,451 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 08:46:10,452 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 08:46:10,457 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-02-02 08:46:10,457 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:41, output treesize:37 [2018-02-02 08:46:10,481 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 08:46:10,484 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-02-02 08:46:10,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 13 treesize of output 12 [2018-02-02 08:46:10,485 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 08:46:10,495 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 08:46:10,503 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-02-02 08:46:10,503 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:52, output treesize:48 [2018-02-02 08:46:10,864 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 08:46:10,865 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 45 treesize of output 41 [2018-02-02 08:46:10,872 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 1 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 19 [2018-02-02 08:46:10,873 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 08:46:10,881 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-02-02 08:46:10,881 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 2 xjuncts. [2018-02-02 08:46:10,885 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-02-02 08:46:10,899 INFO L267 ElimStorePlain]: Start of recursive call 1: 4 dim-0 vars, 1 dim-2 vars, End of recursive call: 6 dim-0 vars, and 2 xjuncts. [2018-02-02 08:46:10,899 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 5 variables, input treesize:73, output treesize:128 [2018-02-02 08:46:11,016 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 0 proven. 9 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 08:46:11,035 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-02-02 08:46:11,035 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 20] total 36 [2018-02-02 08:46:11,036 INFO L409 AbstractCegarLoop]: Interpolant automaton has 37 states [2018-02-02 08:46:11,036 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 37 interpolants. [2018-02-02 08:46:11,036 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=119, Invalid=1213, Unknown=0, NotChecked=0, Total=1332 [2018-02-02 08:46:11,036 INFO L87 Difference]: Start difference. First operand 70 states and 77 transitions. Second operand 37 states. [2018-02-02 08:46:11,423 WARN L146 SmtUtils]: Spent 101ms on a formula simplification. DAG size of input: 100 DAG size of output 47 [2018-02-02 08:46:11,590 WARN L146 SmtUtils]: Spent 118ms on a formula simplification. DAG size of input: 118 DAG size of output 51 [2018-02-02 08:46:13,323 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 08:46:13,323 INFO L93 Difference]: Finished difference Result 87 states and 95 transitions. [2018-02-02 08:46:13,323 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 29 states. [2018-02-02 08:46:13,323 INFO L78 Accepts]: Start accepts. Automaton has 37 states. Word has length 35 [2018-02-02 08:46:13,323 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 08:46:13,324 INFO L225 Difference]: With dead ends: 87 [2018-02-02 08:46:13,324 INFO L226 Difference]: Without dead ends: 85 [2018-02-02 08:46:13,325 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 75 GetRequests, 19 SyntacticMatches, 0 SemanticMatches, 56 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 815 ImplicationChecksByTransitivity, 2.5s TimeCoverageRelationStatistics Valid=368, Invalid=2938, Unknown=0, NotChecked=0, Total=3306 [2018-02-02 08:46:13,325 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 85 states. [2018-02-02 08:46:13,326 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 85 to 73. [2018-02-02 08:46:13,326 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 73 states. [2018-02-02 08:46:13,327 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 73 states to 73 states and 81 transitions. [2018-02-02 08:46:13,327 INFO L78 Accepts]: Start accepts. Automaton has 73 states and 81 transitions. Word has length 35 [2018-02-02 08:46:13,327 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 08:46:13,327 INFO L432 AbstractCegarLoop]: Abstraction has 73 states and 81 transitions. [2018-02-02 08:46:13,327 INFO L433 AbstractCegarLoop]: Interpolant automaton has 37 states. [2018-02-02 08:46:13,327 INFO L276 IsEmpty]: Start isEmpty. Operand 73 states and 81 transitions. [2018-02-02 08:46:13,327 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2018-02-02 08:46:13,327 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 08:46:13,327 INFO L351 BasicCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-02-02 08:46:13,328 INFO L371 AbstractCegarLoop]: === Iteration 20 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 08:46:13,328 INFO L82 PathProgramCache]: Analyzing trace with hash -1689703552, now seen corresponding path program 2 times [2018-02-02 08:46:13,328 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 08:46:13,328 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 08:46:13,328 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 08:46:13,328 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 08:46:13,329 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 08:46:13,348 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 08:46:13,348 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 08:46:13,701 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 08:46:13,701 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-02-02 08:46:13,701 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /home/ultimate/work/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-02-02 08:46:13,707 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-02-02 08:46:13,717 INFO L201 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-02-02 08:46:13,724 INFO L214 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-02-02 08:46:13,726 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-02-02 08:46:13,728 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-02-02 08:46:13,731 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-02-02 08:46:13,732 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-02-02 08:46:13,733 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 08:46:13,733 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:6, output treesize:5 [2018-02-02 08:46:13,737 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-02-02 08:46:13,737 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-02-02 08:46:13,743 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 08:46:13,744 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 08:46:13,744 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-02-02 08:46:13,744 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 08:46:13,755 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 08:46:13,755 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:20, output treesize:13 [2018-02-02 08:46:13,785 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 13 [2018-02-02 08:46:13,786 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 12 [2018-02-02 08:46:13,786 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 08:46:13,787 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 08:46:13,791 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-02-02 08:46:13,791 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:27, output treesize:23 [2018-02-02 08:46:13,950 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 24 treesize of output 25 [2018-02-02 08:46:13,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 8 treesize of output 7 [2018-02-02 08:46:13,952 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 08:46:13,955 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 08:46:13,960 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-02-02 08:46:13,961 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:37, output treesize:26 [2018-02-02 08:46:14,019 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 18 [2018-02-02 08:46:14,023 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-02-02 08:46:14,024 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-02-02 08:46:14,026 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-02-02 08:46:14,032 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 2 xjuncts. [2018-02-02 08:46:14,032 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:36, output treesize:37 [2018-02-02 08:46:14,079 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 08:46:14,109 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-02-02 08:46:14,109 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 27 [2018-02-02 08:46:14,110 INFO L409 AbstractCegarLoop]: Interpolant automaton has 28 states [2018-02-02 08:46:14,110 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2018-02-02 08:46:14,110 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=64, Invalid=692, Unknown=0, NotChecked=0, Total=756 [2018-02-02 08:46:14,110 INFO L87 Difference]: Start difference. First operand 73 states and 81 transitions. Second operand 28 states. [2018-02-02 08:46:14,997 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 08:46:14,997 INFO L93 Difference]: Finished difference Result 81 states and 87 transitions. [2018-02-02 08:46:14,997 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2018-02-02 08:46:14,997 INFO L78 Accepts]: Start accepts. Automaton has 28 states. Word has length 36 [2018-02-02 08:46:14,997 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 08:46:14,998 INFO L225 Difference]: With dead ends: 81 [2018-02-02 08:46:14,998 INFO L226 Difference]: Without dead ends: 81 [2018-02-02 08:46:14,998 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 66 GetRequests, 24 SyntacticMatches, 1 SemanticMatches, 41 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 197 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=200, Invalid=1606, Unknown=0, NotChecked=0, Total=1806 [2018-02-02 08:46:14,999 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 81 states. [2018-02-02 08:46:15,000 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 81 to 56. [2018-02-02 08:46:15,000 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 56 states. [2018-02-02 08:46:15,000 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 56 states to 56 states and 62 transitions. [2018-02-02 08:46:15,000 INFO L78 Accepts]: Start accepts. Automaton has 56 states and 62 transitions. Word has length 36 [2018-02-02 08:46:15,001 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 08:46:15,001 INFO L432 AbstractCegarLoop]: Abstraction has 56 states and 62 transitions. [2018-02-02 08:46:15,001 INFO L433 AbstractCegarLoop]: Interpolant automaton has 28 states. [2018-02-02 08:46:15,001 INFO L276 IsEmpty]: Start isEmpty. Operand 56 states and 62 transitions. [2018-02-02 08:46:15,001 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2018-02-02 08:46:15,001 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 08:46:15,001 INFO L351 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-02-02 08:46:15,002 INFO L371 AbstractCegarLoop]: === Iteration 21 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 08:46:15,002 INFO L82 PathProgramCache]: Analyzing trace with hash -601444785, now seen corresponding path program 1 times [2018-02-02 08:46:15,002 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 08:46:15,002 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 08:46:15,002 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 08:46:15,003 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-02-02 08:46:15,003 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 08:46:15,013 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 08:46:15,013 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 08:46:15,295 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 0 proven. 9 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 08:46:15,296 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-02-02 08:46:15,296 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /home/ultimate/work/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-02-02 08:46:15,301 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 08:46:15,315 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 08:46:15,317 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-02-02 08:46:15,329 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-02-02 08:46:15,330 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-02-02 08:46:15,334 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-02-02 08:46:15,334 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 08:46:15,338 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 08:46:15,338 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:21, output treesize:16 [2018-02-02 08:46:15,367 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 08:46:15,368 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 08:46:15,368 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-02-02 08:46:15,369 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-02-02 08:46:15,376 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 08:46:15,377 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 08:46:15,377 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-02-02 08:46:15,377 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 08:46:15,381 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 08:46:15,381 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:30, output treesize:19 [2018-02-02 08:46:15,416 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 12 [2018-02-02 08:46:15,417 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-02-02 08:46:15,418 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 08:46:15,419 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 08:46:15,422 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-02-02 08:46:15,422 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:28, output treesize:24 [2018-02-02 08:46:15,613 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 08:46:15,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 23 treesize of output 24 [2018-02-02 08:46:15,617 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-02-02 08:46:15,617 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 08:46:15,620 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 08:46:15,625 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-02-02 08:46:15,625 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:41, output treesize:30 [2018-02-02 08:46:15,681 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 15 [2018-02-02 08:46:15,685 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 1 case distinctions, treesize of input 15 treesize of output 12 [2018-02-02 08:46:15,685 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-02-02 08:46:15,687 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-02-02 08:46:15,694 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: 2 dim-0 vars, and 2 xjuncts. [2018-02-02 08:46:15,694 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:44, output treesize:51 [2018-02-02 08:46:15,783 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 0 proven. 9 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 08:46:15,800 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-02-02 08:46:15,801 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 19] total 39 [2018-02-02 08:46:15,801 INFO L409 AbstractCegarLoop]: Interpolant automaton has 40 states [2018-02-02 08:46:15,801 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 40 interpolants. [2018-02-02 08:46:15,801 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=118, Invalid=1442, Unknown=0, NotChecked=0, Total=1560 [2018-02-02 08:46:15,801 INFO L87 Difference]: Start difference. First operand 56 states and 62 transitions. Second operand 40 states. [2018-02-02 08:46:17,904 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 08:46:17,904 INFO L93 Difference]: Finished difference Result 94 states and 101 transitions. [2018-02-02 08:46:17,905 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 35 states. [2018-02-02 08:46:17,905 INFO L78 Accepts]: Start accepts. Automaton has 40 states. Word has length 38 [2018-02-02 08:46:17,905 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 08:46:17,906 INFO L225 Difference]: With dead ends: 94 [2018-02-02 08:46:17,906 INFO L226 Difference]: Without dead ends: 92 [2018-02-02 08:46:17,906 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 88 GetRequests, 21 SyntacticMatches, 0 SemanticMatches, 67 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1141 ImplicationChecksByTransitivity, 2.1s TimeCoverageRelationStatistics Valid=446, Invalid=4246, Unknown=0, NotChecked=0, Total=4692 [2018-02-02 08:46:17,907 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 92 states. [2018-02-02 08:46:17,908 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 92 to 62. [2018-02-02 08:46:17,908 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 62 states. [2018-02-02 08:46:17,908 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 62 states to 62 states and 68 transitions. [2018-02-02 08:46:17,908 INFO L78 Accepts]: Start accepts. Automaton has 62 states and 68 transitions. Word has length 38 [2018-02-02 08:46:17,909 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 08:46:17,909 INFO L432 AbstractCegarLoop]: Abstraction has 62 states and 68 transitions. [2018-02-02 08:46:17,909 INFO L433 AbstractCegarLoop]: Interpolant automaton has 40 states. [2018-02-02 08:46:17,909 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states and 68 transitions. [2018-02-02 08:46:17,909 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2018-02-02 08:46:17,909 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 08:46:17,909 INFO L351 BasicCegarLoop]: trace histogram [4, 4, 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] [2018-02-02 08:46:17,910 INFO L371 AbstractCegarLoop]: === Iteration 22 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 08:46:17,910 INFO L82 PathProgramCache]: Analyzing trace with hash -28866724, now seen corresponding path program 2 times [2018-02-02 08:46:17,910 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 08:46:17,910 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 08:46:17,910 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 08:46:17,911 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 08:46:17,911 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 08:46:17,920 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 08:46:17,920 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 08:46:18,317 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 0 proven. 18 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 08:46:18,318 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-02-02 08:46:18,318 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /home/ultimate/work/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-02-02 08:46:18,323 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-02-02 08:46:18,335 INFO L201 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-02-02 08:46:18,341 INFO L214 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-02-02 08:46:18,343 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-02-02 08:46:18,346 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-02-02 08:46:18,405 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-02-02 08:46:18,405 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-02-02 08:46:18,413 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-02-02 08:46:18,413 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 08:46:18,418 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 08:46:18,418 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:27, output treesize:25 [2018-02-02 08:46:18,467 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 08:46:18,468 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 08:46:18,469 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-02-02 08:46:18,469 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-02-02 08:46:18,491 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 08:46:18,492 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 08:46:18,492 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-02-02 08:46:18,492 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 08:46:18,499 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 08:46:18,499 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:36, output treesize:25 [2018-02-02 08:46:18,560 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-02-02 08:46:18,562 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 15 [2018-02-02 08:46:18,562 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 08:46:18,563 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 08:46:18,579 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-02-02 08:46:18,579 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:41, output treesize:37 [2018-02-02 08:46:18,660 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 08:46:18,664 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-02-02 08:46:18,668 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-02-02 08:46:18,668 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 08:46:18,673 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 08:46:18,683 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-02-02 08:46:18,684 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:52, output treesize:48 [2018-02-02 08:46:19,332 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 08:46:19,333 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 51 treesize of output 45 [2018-02-02 08:46:19,340 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 4 disjoint index pairs (out of 3 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 26 treesize of output 41 [2018-02-02 08:46:19,340 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-02-02 08:46:19,377 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-02-02 08:46:19,377 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 2 xjuncts. [2018-02-02 08:46:19,383 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-02-02 08:46:19,406 INFO L267 ElimStorePlain]: Start of recursive call 1: 6 dim-0 vars, 1 dim-2 vars, End of recursive call: 9 dim-0 vars, and 2 xjuncts. [2018-02-02 08:46:19,406 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 7 variables, input treesize:89, output treesize:227 [2018-02-02 08:46:19,567 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 0 proven. 18 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 08:46:19,590 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-02-02 08:46:19,590 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 22] total 40 [2018-02-02 08:46:19,591 INFO L409 AbstractCegarLoop]: Interpolant automaton has 41 states [2018-02-02 08:46:19,591 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 41 interpolants. [2018-02-02 08:46:19,592 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=114, Invalid=1526, Unknown=0, NotChecked=0, Total=1640 [2018-02-02 08:46:19,592 INFO L87 Difference]: Start difference. First operand 62 states and 68 transitions. Second operand 41 states. [2018-02-02 08:46:20,500 WARN L146 SmtUtils]: Spent 105ms on a formula simplification. DAG size of input: 108 DAG size of output 104 [2018-02-02 08:46:22,362 WARN L146 SmtUtils]: Spent 1653ms on a formula simplification. DAG size of input: 121 DAG size of output 111 [2018-02-02 08:46:22,700 WARN L146 SmtUtils]: Spent 119ms on a formula simplification. DAG size of input: 124 DAG size of output 120 [2018-02-02 08:46:22,967 WARN L146 SmtUtils]: Spent 146ms on a formula simplification. DAG size of input: 133 DAG size of output 122 [2018-02-02 08:46:23,171 WARN L146 SmtUtils]: Spent 131ms on a formula simplification. DAG size of input: 130 DAG size of output 115 [2018-02-02 08:46:23,364 WARN L146 SmtUtils]: Spent 128ms on a formula simplification. DAG size of input: 127 DAG size of output 121 [2018-02-02 08:46:23,586 WARN L146 SmtUtils]: Spent 157ms on a formula simplification. DAG size of input: 153 DAG size of output 136 [2018-02-02 08:46:23,759 WARN L146 SmtUtils]: Spent 111ms on a formula simplification. DAG size of input: 133 DAG size of output 117 [2018-02-02 08:46:26,761 WARN L146 SmtUtils]: Spent 114ms on a formula simplification. DAG size of input: 134 DAG size of output 120 [2018-02-02 08:46:27,013 WARN L146 SmtUtils]: Spent 150ms on a formula simplification. DAG size of input: 139 DAG size of output 130 [2018-02-02 08:46:28,978 WARN L146 SmtUtils]: Spent 111ms on a formula simplification. DAG size of input: 136 DAG size of output 122 [2018-02-02 08:46:29,296 WARN L146 SmtUtils]: Spent 121ms on a formula simplification. DAG size of input: 136 DAG size of output 122 [2018-02-02 08:46:29,522 WARN L146 SmtUtils]: Spent 151ms on a formula simplification. DAG size of input: 160 DAG size of output 137 [2018-02-02 08:46:30,162 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 08:46:30,162 INFO L93 Difference]: Finished difference Result 104 states and 111 transitions. [2018-02-02 08:46:30,163 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 43 states. [2018-02-02 08:46:30,163 INFO L78 Accepts]: Start accepts. Automaton has 41 states. Word has length 38 [2018-02-02 08:46:30,163 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 08:46:30,164 INFO L225 Difference]: With dead ends: 104 [2018-02-02 08:46:30,164 INFO L226 Difference]: Without dead ends: 101 [2018-02-02 08:46:30,165 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 92 GetRequests, 17 SyntacticMatches, 1 SemanticMatches, 74 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1355 ImplicationChecksByTransitivity, 6.4s TimeCoverageRelationStatistics Valid=550, Invalid=5150, Unknown=0, NotChecked=0, Total=5700 [2018-02-02 08:46:30,165 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 101 states. [2018-02-02 08:46:30,166 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 101 to 71. [2018-02-02 08:46:30,166 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 71 states. [2018-02-02 08:46:30,167 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 78 transitions. [2018-02-02 08:46:30,167 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 78 transitions. Word has length 38 [2018-02-02 08:46:30,167 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 08:46:30,167 INFO L432 AbstractCegarLoop]: Abstraction has 71 states and 78 transitions. [2018-02-02 08:46:30,167 INFO L433 AbstractCegarLoop]: Interpolant automaton has 41 states. [2018-02-02 08:46:30,167 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 78 transitions. [2018-02-02 08:46:30,168 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2018-02-02 08:46:30,168 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 08:46:30,168 INFO L351 BasicCegarLoop]: trace histogram [3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-02-02 08:46:30,168 INFO L371 AbstractCegarLoop]: === Iteration 23 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 08:46:30,168 INFO L82 PathProgramCache]: Analyzing trace with hash 669200065, now seen corresponding path program 2 times [2018-02-02 08:46:30,168 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 08:46:30,168 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 08:46:30,168 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 08:46:30,169 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-02-02 08:46:30,169 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 08:46:30,176 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 08:46:30,177 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 08:46:30,748 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 08:46:30,748 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-02-02 08:46:30,748 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /home/ultimate/work/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-02-02 08:46:30,753 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-02-02 08:46:30,761 INFO L201 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-02-02 08:46:30,766 INFO L214 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-02-02 08:46:30,769 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-02-02 08:46:30,771 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-02-02 08:46:30,774 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-02-02 08:46:30,774 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-02-02 08:46:30,780 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-02-02 08:46:30,780 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 08:46:30,784 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 08:46:30,784 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:24, output treesize:19 [2018-02-02 08:46:30,828 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 08:46:30,828 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 08:46:30,829 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-02-02 08:46:30,829 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-02-02 08:46:30,837 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 08:46:30,838 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 08:46:30,838 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-02-02 08:46:30,838 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 08:46:30,843 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 08:46:30,843 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:33, output treesize:22 [2018-02-02 08:46:30,946 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-02-02 08:46:30,947 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-02-02 08:46:30,947 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 08:46:30,949 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 08:46:30,954 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-02-02 08:46:30,954 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:35, output treesize:31 [2018-02-02 08:46:31,184 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 08:46:31,187 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 24 treesize of output 25 [2018-02-02 08:46:31,188 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-02-02 08:46:31,188 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 08:46:31,191 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 08:46:31,197 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-02-02 08:46:31,198 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:47, output treesize:36 [2018-02-02 08:46:31,362 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-02-02 08:46:31,367 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-02-02 08:46:31,367 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-02-02 08:46:31,369 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-02-02 08:46:31,380 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-02-02 08:46:31,380 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 5 variables, input treesize:57, output treesize:65 [2018-02-02 08:46:31,584 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 08:46:31,600 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-02-02 08:46:31,601 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [23, 21] total 41 [2018-02-02 08:46:31,601 INFO L409 AbstractCegarLoop]: Interpolant automaton has 42 states [2018-02-02 08:46:31,601 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 42 interpolants. [2018-02-02 08:46:31,601 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=101, Invalid=1621, Unknown=0, NotChecked=0, Total=1722 [2018-02-02 08:46:31,601 INFO L87 Difference]: Start difference. First operand 71 states and 78 transitions. Second operand 42 states. [2018-02-02 08:46:35,398 WARN L146 SmtUtils]: Spent 119ms on a formula simplification. DAG size of input: 93 DAG size of output 92 [2018-02-02 08:46:35,672 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 08:46:35,672 INFO L93 Difference]: Finished difference Result 116 states and 124 transitions. [2018-02-02 08:46:35,672 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 41 states. [2018-02-02 08:46:35,672 INFO L78 Accepts]: Start accepts. Automaton has 42 states. Word has length 41 [2018-02-02 08:46:35,673 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 08:46:35,673 INFO L225 Difference]: With dead ends: 116 [2018-02-02 08:46:35,673 INFO L226 Difference]: Without dead ends: 115 [2018-02-02 08:46:35,674 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 94 GetRequests, 23 SyntacticMatches, 0 SemanticMatches, 71 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 995 ImplicationChecksByTransitivity, 4.2s TimeCoverageRelationStatistics Valid=402, Invalid=4853, Unknown=1, NotChecked=0, Total=5256 [2018-02-02 08:46:35,675 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 115 states. [2018-02-02 08:46:35,676 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 115 to 71. [2018-02-02 08:46:35,676 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 71 states. [2018-02-02 08:46:35,677 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 78 transitions. [2018-02-02 08:46:35,677 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 78 transitions. Word has length 41 [2018-02-02 08:46:35,677 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 08:46:35,677 INFO L432 AbstractCegarLoop]: Abstraction has 71 states and 78 transitions. [2018-02-02 08:46:35,677 INFO L433 AbstractCegarLoop]: Interpolant automaton has 42 states. [2018-02-02 08:46:35,677 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 78 transitions. [2018-02-02 08:46:35,677 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2018-02-02 08:46:35,678 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 08:46:35,678 INFO L351 BasicCegarLoop]: trace histogram [5, 5, 4, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-02-02 08:46:35,678 INFO L371 AbstractCegarLoop]: === Iteration 24 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 08:46:35,678 INFO L82 PathProgramCache]: Analyzing trace with hash -652090471, now seen corresponding path program 1 times [2018-02-02 08:46:35,678 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 08:46:35,678 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 08:46:35,679 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 08:46:35,679 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-02-02 08:46:35,679 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 08:46:35,693 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 08:46:35,693 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 08:46:36,545 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 0 proven. 33 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 08:46:36,546 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-02-02 08:46:36,546 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /home/ultimate/work/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-02-02 08:46:36,550 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 08:46:36,567 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 08:46:36,569 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-02-02 08:46:36,572 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-02-02 08:46:36,572 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-02-02 08:46:36,577 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-02-02 08:46:36,578 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 08:46:36,582 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 08:46:36,582 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:24, output treesize:22 [2018-02-02 08:46:36,637 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 08:46:36,637 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 08:46:36,638 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-02-02 08:46:36,638 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-02-02 08:46:36,645 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 08:46:36,645 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-02-02 08:46:36,646 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 08:46:36,660 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 08:46:36,660 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:33, output treesize:22 [2018-02-02 08:46:36,725 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-02-02 08:46:36,727 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 15 [2018-02-02 08:46:36,727 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 08:46:36,728 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 08:46:36,733 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-02-02 08:46:36,734 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:38, output treesize:34 [2018-02-02 08:46:36,767 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 08:46:36,770 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-02-02 08:46:36,771 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-02-02 08:46:36,771 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 08:46:36,775 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 08:46:36,780 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-02-02 08:46:36,780 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:47, output treesize:43 Received shutdown request... [2018-02-02 08:46:36,957 INFO L175 TraceCheckSpWp]: Timeout while computing interpolants [2018-02-02 08:46:36,957 WARN L491 AbstractCegarLoop]: Verification canceled [2018-02-02 08:46:36,960 WARN L185 ceAbstractionStarter]: Timeout [2018-02-02 08:46:36,961 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 02.02 08:46:36 BoogieIcfgContainer [2018-02-02 08:46:36,961 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-02-02 08:46:36,961 INFO L168 Benchmark]: Toolchain (without parser) took 64953.67 ms. Allocated memory was 400.6 MB in the beginning and 842.0 MB in the end (delta: 441.5 MB). Free memory was 357.2 MB in the beginning and 540.6 MB in the end (delta: -183.3 MB). Peak memory consumption was 258.1 MB. Max. memory is 5.3 GB. [2018-02-02 08:46:36,962 INFO L168 Benchmark]: CDTParser took 0.09 ms. Allocated memory is still 400.6 MB. Free memory is still 362.5 MB. There was no memory consumed. Max. memory is 5.3 GB. [2018-02-02 08:46:36,962 INFO L168 Benchmark]: CACSL2BoogieTranslator took 162.15 ms. Allocated memory is still 400.6 MB. Free memory was 357.2 MB in the beginning and 346.7 MB in the end (delta: 10.6 MB). Peak memory consumption was 10.6 MB. Max. memory is 5.3 GB. [2018-02-02 08:46:36,963 INFO L168 Benchmark]: Boogie Preprocessor took 27.83 ms. Allocated memory is still 400.6 MB. Free memory was 346.7 MB in the beginning and 344.0 MB in the end (delta: 2.6 MB). Peak memory consumption was 2.6 MB. Max. memory is 5.3 GB. [2018-02-02 08:46:36,963 INFO L168 Benchmark]: RCFGBuilder took 234.95 ms. Allocated memory is still 400.6 MB. Free memory was 344.0 MB in the beginning and 324.2 MB in the end (delta: 19.9 MB). Peak memory consumption was 19.9 MB. Max. memory is 5.3 GB. [2018-02-02 08:46:36,963 INFO L168 Benchmark]: TraceAbstraction took 64525.73 ms. Allocated memory was 400.6 MB in the beginning and 842.0 MB in the end (delta: 441.5 MB). Free memory was 321.5 MB in the beginning and 540.6 MB in the end (delta: -219.0 MB). Peak memory consumption was 222.4 MB. Max. memory is 5.3 GB. [2018-02-02 08:46:36,964 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.09 ms. Allocated memory is still 400.6 MB. Free memory is still 362.5 MB. There was no memory consumed. Max. memory is 5.3 GB. * CACSL2BoogieTranslator took 162.15 ms. Allocated memory is still 400.6 MB. Free memory was 357.2 MB in the beginning and 346.7 MB in the end (delta: 10.6 MB). Peak memory consumption was 10.6 MB. Max. memory is 5.3 GB. * Boogie Preprocessor took 27.83 ms. Allocated memory is still 400.6 MB. Free memory was 346.7 MB in the beginning and 344.0 MB in the end (delta: 2.6 MB). Peak memory consumption was 2.6 MB. Max. memory is 5.3 GB. * RCFGBuilder took 234.95 ms. Allocated memory is still 400.6 MB. Free memory was 344.0 MB in the beginning and 324.2 MB in the end (delta: 19.9 MB). Peak memory consumption was 19.9 MB. Max. memory is 5.3 GB. * TraceAbstraction took 64525.73 ms. Allocated memory was 400.6 MB in the beginning and 842.0 MB in the end (delta: 441.5 MB). Free memory was 321.5 MB in the beginning and 540.6 MB in the end (delta: -219.0 MB). Peak memory consumption was 222.4 MB. Max. memory is 5.3 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 574). Cancelled while BasicCegarLoop was analyzing trace of length 44 with TraceHistMax 5, while TraceCheckSpWp was constructing forward predicates, while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 31. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 573). Cancelled while BasicCegarLoop was analyzing trace of length 44 with TraceHistMax 5, while TraceCheckSpWp was constructing forward predicates, while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 31. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 574). Cancelled while BasicCegarLoop was analyzing trace of length 44 with TraceHistMax 5, while TraceCheckSpWp was constructing forward predicates, while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 31. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 573). Cancelled while BasicCegarLoop was analyzing trace of length 44 with TraceHistMax 5, while TraceCheckSpWp was constructing forward predicates, while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 31. - TimeoutResultAtElement [Line: 557]: Timeout (TraceAbstraction) Unable to prove that all allocated memory was freed (line 557). Cancelled while BasicCegarLoop was analyzing trace of length 44 with TraceHistMax 5, while TraceCheckSpWp was constructing forward predicates, while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 31. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 553). Cancelled while BasicCegarLoop was analyzing trace of length 44 with TraceHistMax 5, while TraceCheckSpWp was constructing forward predicates, while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 31. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 549). Cancelled while BasicCegarLoop was analyzing trace of length 44 with TraceHistMax 5, while TraceCheckSpWp was constructing forward predicates, while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 31. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 546). Cancelled while BasicCegarLoop was analyzing trace of length 44 with TraceHistMax 5, while TraceCheckSpWp was constructing forward predicates, while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 31. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 549). Cancelled while BasicCegarLoop was analyzing trace of length 44 with TraceHistMax 5, while TraceCheckSpWp was constructing forward predicates, while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 31. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 546). Cancelled while BasicCegarLoop was analyzing trace of length 44 with TraceHistMax 5, while TraceCheckSpWp was constructing forward predicates, while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 31. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 549). Cancelled while BasicCegarLoop was analyzing trace of length 44 with TraceHistMax 5, while TraceCheckSpWp was constructing forward predicates, while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 31. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 553). Cancelled while BasicCegarLoop was analyzing trace of length 44 with TraceHistMax 5, while TraceCheckSpWp was constructing forward predicates, while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 31. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 549). Cancelled while BasicCegarLoop was analyzing trace of length 44 with TraceHistMax 5, while TraceCheckSpWp was constructing forward predicates, while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 31. - StatisticsResult: Ultimate Automizer benchmark data CFG has 4 procedures, 54 locations, 13 error locations. TIMEOUT Result, 64.4s OverallTime, 24 OverallIterations, 5 TraceHistogramMax, 52.5s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 809 SDtfs, 1972 SDslu, 5159 SDs, 0 SdLazy, 7675 SolverSat, 773 SolverUnsat, 7 SolverUnknown, 0 SolverNotchecked, 21.1s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 814 GetRequests, 213 SyntacticMatches, 6 SemanticMatches, 595 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6206 ImplicationChecksByTransitivity, 38.0s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=81occurred in iteration=16, 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.0s AutomataMinimizationTime, 23 MinimizatonAttempts, 244 StatesRemovedByMinimization, 16 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.3s SatisfiabilityAnalysisTime, 9.6s InterpolantComputationTime, 942 NumberOfCodeBlocks, 942 NumberOfCodeBlocksAsserted, 37 NumberOfCheckSat, 909 ConstructedInterpolants, 127 QuantifiedInterpolants, 463514 SizeOfPredicates, 160 NumberOfNonLiveVariables, 1686 ConjunctsInSsa, 510 ConjunctsInUnsatCore, 33 InterpolantComputations, 13 PerfectInterpolantSequences, 6/176 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, ReuseStatistics: No data available RESULT: Ultimate could not prove your program: Timeout Written .csv to /home/ultimate/work/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/openbsd_cstrncat-alloca_true-valid-memsafety_true-termination.i_svcomp-DerefFreeMemtrack-32bit-Automizer_Camel.epf_AutomizerC.xml/Csv-Benchmark-0-2018-02-02_08-46-36-970.csv Written .csv to /home/ultimate/work/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/openbsd_cstrncat-alloca_true-valid-memsafety_true-termination.i_svcomp-DerefFreeMemtrack-32bit-Automizer_Camel.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-0-2018-02-02_08-46-36-970.csv Completed graceful shutdown