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/cade18-smtinterpol/svcomp-DerefFreeMemtrack-32bit-Automizer_Camel.epf -i ../../../trunk/examples/svcomp/array-memsafety/cstrncat-alloca_true-valid-memsafety_true-termination.i -------------------------------------------------------------------------------- This is Ultimate 0.1.23-a74eeac-m [2018-02-02 18:22:46,286 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-02-02 18:22:46,287 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-02-02 18:22:46,299 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-02-02 18:22:46,299 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-02-02 18:22:46,300 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-02-02 18:22:46,300 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-02-02 18:22:46,302 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-02-02 18:22:46,304 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-02-02 18:22:46,305 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-02-02 18:22:46,305 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-02-02 18:22:46,306 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-02-02 18:22:46,307 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-02-02 18:22:46,308 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-02-02 18:22:46,308 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-02-02 18:22:46,310 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-02-02 18:22:46,312 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-02-02 18:22:46,313 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-02-02 18:22:46,314 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-02-02 18:22:46,315 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-02-02 18:22:46,317 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-02-02 18:22:46,317 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-02-02 18:22:46,317 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-02-02 18:22:46,318 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-02-02 18:22:46,319 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-02-02 18:22:46,320 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-02-02 18:22:46,320 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-02-02 18:22:46,321 INFO L177 SettingsManager]: PEA to Boogie provides no preferences, ignoring... [2018-02-02 18:22:46,321 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-02-02 18:22:46,321 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-02-02 18:22:46,322 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-02-02 18:22:46,322 INFO L98 SettingsManager]: Beginning loading settings from /home/ultimate/work/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/cade18-smtinterpol/svcomp-DerefFreeMemtrack-32bit-Automizer_Camel.epf [2018-02-02 18:22:46,332 INFO L110 SettingsManager]: Loading preferences was successful [2018-02-02 18:22:46,332 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-02-02 18:22:46,334 INFO L131 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2018-02-02 18:22:46,334 INFO L133 SettingsManager]: * Create parallel compositions if possible=false [2018-02-02 18:22:46,334 INFO L133 SettingsManager]: * Use SBE=true [2018-02-02 18:22:46,334 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-02-02 18:22:46,334 INFO L133 SettingsManager]: * sizeof long=4 [2018-02-02 18:22:46,335 INFO L133 SettingsManager]: * Check unreachability of error function in SV-COMP mode=false [2018-02-02 18:22:46,335 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-02-02 18:22:46,335 INFO L133 SettingsManager]: * sizeof POINTER=4 [2018-02-02 18:22:46,335 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-02-02 18:22:46,335 INFO L133 SettingsManager]: * Check for the main procedure if all allocated memory was freed=true [2018-02-02 18:22:46,335 INFO L133 SettingsManager]: * Bitprecise bitfields=true [2018-02-02 18:22:46,336 INFO L133 SettingsManager]: * SV-COMP memtrack compatibility mode=true [2018-02-02 18:22:46,336 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-02-02 18:22:46,336 INFO L133 SettingsManager]: * sizeof long double=12 [2018-02-02 18:22:46,336 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-02-02 18:22:46,336 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-02-02 18:22:46,336 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-02-02 18:22:46,336 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-02-02 18:22:46,337 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-02-02 18:22:46,337 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-02-02 18:22:46,337 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-02-02 18:22:46,337 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-02-02 18:22:46,337 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-02-02 18:22:46,368 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-02-02 18:22:46,378 INFO L266 ainManager$Toolchain]: [Toolchain 1]: Parser(s) successfully initialized [2018-02-02 18:22:46,380 INFO L222 ainManager$Toolchain]: [Toolchain 1]: Toolchain data selected. [2018-02-02 18:22:46,381 INFO L271 PluginConnector]: Initializing CDTParser... [2018-02-02 18:22:46,382 INFO L276 PluginConnector]: CDTParser initialized [2018-02-02 18:22:46,382 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /home/ultimate/work/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/array-memsafety/cstrncat-alloca_true-valid-memsafety_true-termination.i [2018-02-02 18:22:46,514 INFO L304 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-02-02 18:22:46,516 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2018-02-02 18:22:46,516 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2018-02-02 18:22:46,516 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2018-02-02 18:22:46,521 INFO L276 PluginConnector]: CACSL2BoogieTranslator initialized [2018-02-02 18:22:46,521 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 02.02 06:22:46" (1/1) ... [2018-02-02 18:22:46,524 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@3dc5225c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.02 06:22:46, skipping insertion in model container [2018-02-02 18:22:46,524 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 02.02 06:22:46" (1/1) ... [2018-02-02 18:22:46,536 INFO L153 Dispatcher]: Using SV-COMP mode [2018-02-02 18:22:46,565 INFO L153 Dispatcher]: Using SV-COMP mode [2018-02-02 18:22:46,657 INFO L450 PostProcessor]: Settings: Checked method=main [2018-02-02 18:22:46,670 INFO L450 PostProcessor]: Settings: Checked method=main [2018-02-02 18:22:46,675 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.02 06:22:46 WrapperNode [2018-02-02 18:22:46,676 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2018-02-02 18:22:46,676 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-02-02 18:22:46,676 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-02-02 18:22:46,677 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-02-02 18:22:46,690 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.02 06:22:46" (1/1) ... [2018-02-02 18:22:46,690 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.02 06:22:46" (1/1) ... [2018-02-02 18:22:46,698 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.02 06:22:46" (1/1) ... [2018-02-02 18:22:46,698 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.02 06:22:46" (1/1) ... [2018-02-02 18:22:46,700 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.02 06:22:46" (1/1) ... [2018-02-02 18:22:46,703 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.02 06:22:46" (1/1) ... [2018-02-02 18:22:46,704 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.02 06:22:46" (1/1) ... [2018-02-02 18:22:46,706 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-02-02 18:22:46,706 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-02-02 18:22:46,706 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-02-02 18:22:46,706 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-02-02 18:22:46,707 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.02 06:22:46" (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 18:22:46,744 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2018-02-02 18:22:46,744 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-02-02 18:22:46,745 INFO L136 BoogieDeclarations]: Found implementation of procedure cstrncat [2018-02-02 18:22:46,745 INFO L136 BoogieDeclarations]: Found implementation of procedure main [2018-02-02 18:22:46,745 INFO L128 BoogieDeclarations]: Found specification of procedure write~int [2018-02-02 18:22:46,745 INFO L128 BoogieDeclarations]: Found specification of procedure read~int [2018-02-02 18:22:46,745 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.free [2018-02-02 18:22:46,745 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2018-02-02 18:22:46,745 INFO L128 BoogieDeclarations]: Found specification of procedure #Ultimate.alloc [2018-02-02 18:22:46,745 INFO L128 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2018-02-02 18:22:46,745 INFO L128 BoogieDeclarations]: Found specification of procedure cstrncat [2018-02-02 18:22:46,745 INFO L128 BoogieDeclarations]: Found specification of procedure main [2018-02-02 18:22:46,745 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2018-02-02 18:22:46,745 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-02-02 18:22:46,922 INFO L257 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-02-02 18:22:46,922 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 02.02 06:22:46 BoogieIcfgContainer [2018-02-02 18:22:46,922 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-02-02 18:22:46,922 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-02-02 18:22:46,923 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-02-02 18:22:46,924 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-02-02 18:22:46,924 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 02.02 06:22:46" (1/3) ... [2018-02-02 18:22:46,925 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@ea58ba6 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 02.02 06:22:46, skipping insertion in model container [2018-02-02 18:22:46,925 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.02 06:22:46" (2/3) ... [2018-02-02 18:22:46,925 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@ea58ba6 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 02.02 06:22:46, skipping insertion in model container [2018-02-02 18:22:46,925 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 02.02 06:22:46" (3/3) ... [2018-02-02 18:22:46,926 INFO L107 eAbstractionObserver]: Analyzing ICFG cstrncat-alloca_true-valid-memsafety_true-termination.i [2018-02-02 18:22:46,931 INFO L128 ceAbstractionStarter]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-02-02 18:22:46,935 INFO L140 ceAbstractionStarter]: Appying trace abstraction to program that has 15 error locations. [2018-02-02 18:22:46,957 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-02-02 18:22:46,957 INFO L323 AbstractCegarLoop]: Hoare is false [2018-02-02 18:22:46,957 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-02-02 18:22:46,957 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-02-02 18:22:46,957 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-02-02 18:22:46,957 INFO L327 AbstractCegarLoop]: Difference is false [2018-02-02 18:22:46,957 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-02-02 18:22:46,957 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-02-02 18:22:46,958 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-02-02 18:22:46,966 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states. [2018-02-02 18:22:46,973 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2018-02-02 18:22:46,973 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 18:22:46,973 INFO L351 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-02-02 18:22:46,973 INFO L371 AbstractCegarLoop]: === Iteration 1 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 18:22:46,977 INFO L82 PathProgramCache]: Analyzing trace with hash 1927484354, now seen corresponding path program 1 times [2018-02-02 18:22:46,978 INFO L213 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 18:22:46,978 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 18:22:47,008 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:22:47,008 INFO L109 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 18:22:47,009 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:22:47,044 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:22:47,051 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 18:22:47,105 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 18:22:47,107 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-02-02 18:22:47,107 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-02-02 18:22:47,109 INFO L409 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-02-02 18:22:47,117 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-02-02 18:22:47,117 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-02-02 18:22:47,119 INFO L87 Difference]: Start difference. First operand 58 states. Second operand 3 states. [2018-02-02 18:22:47,197 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 18:22:47,197 INFO L93 Difference]: Finished difference Result 59 states and 66 transitions. [2018-02-02 18:22:47,197 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-02-02 18:22:47,198 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 11 [2018-02-02 18:22:47,199 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 18:22:47,283 INFO L225 Difference]: With dead ends: 59 [2018-02-02 18:22:47,283 INFO L226 Difference]: Without dead ends: 55 [2018-02-02 18:22:47,284 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 18:22:47,297 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2018-02-02 18:22:47,308 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 55. [2018-02-02 18:22:47,309 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 55 states. [2018-02-02 18:22:47,310 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 61 transitions. [2018-02-02 18:22:47,310 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 61 transitions. Word has length 11 [2018-02-02 18:22:47,311 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 18:22:47,311 INFO L432 AbstractCegarLoop]: Abstraction has 55 states and 61 transitions. [2018-02-02 18:22:47,311 INFO L433 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-02-02 18:22:47,311 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 61 transitions. [2018-02-02 18:22:47,311 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2018-02-02 18:22:47,311 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 18:22:47,312 INFO L351 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-02-02 18:22:47,312 INFO L371 AbstractCegarLoop]: === Iteration 2 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 18:22:47,312 INFO L82 PathProgramCache]: Analyzing trace with hash 1621249811, now seen corresponding path program 1 times [2018-02-02 18:22:47,312 INFO L213 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 18:22:47,312 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 18:22:47,313 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:22:47,313 INFO L109 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 18:22:47,313 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:22:47,324 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:22:47,325 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 18:22:47,357 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 18:22:47,357 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-02-02 18:22:47,357 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-02-02 18:22:47,359 INFO L409 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-02-02 18:22:47,359 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-02-02 18:22:47,359 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-02-02 18:22:47,359 INFO L87 Difference]: Start difference. First operand 55 states and 61 transitions. Second operand 5 states. [2018-02-02 18:22:47,405 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 18:22:47,405 INFO L93 Difference]: Finished difference Result 58 states and 65 transitions. [2018-02-02 18:22:47,406 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-02-02 18:22:47,406 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 15 [2018-02-02 18:22:47,406 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 18:22:47,407 INFO L225 Difference]: With dead ends: 58 [2018-02-02 18:22:47,407 INFO L226 Difference]: Without dead ends: 55 [2018-02-02 18:22:47,408 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 18:22:47,408 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2018-02-02 18:22:47,411 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 55. [2018-02-02 18:22:47,412 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 55 states. [2018-02-02 18:22:47,413 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 60 transitions. [2018-02-02 18:22:47,413 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 60 transitions. Word has length 15 [2018-02-02 18:22:47,413 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 18:22:47,413 INFO L432 AbstractCegarLoop]: Abstraction has 55 states and 60 transitions. [2018-02-02 18:22:47,413 INFO L433 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-02-02 18:22:47,414 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 60 transitions. [2018-02-02 18:22:47,414 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2018-02-02 18:22:47,414 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 18:22:47,414 INFO L351 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-02-02 18:22:47,414 INFO L371 AbstractCegarLoop]: === Iteration 3 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 18:22:47,414 INFO L82 PathProgramCache]: Analyzing trace with hash -1993659115, now seen corresponding path program 1 times [2018-02-02 18:22:47,414 INFO L213 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 18:22:47,415 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 18:22:47,415 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:22:47,416 INFO L109 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 18:22:47,416 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:22:47,432 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:22:47,432 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 18:22:47,479 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 18:22:47,480 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-02-02 18:22:47,480 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-02-02 18:22:47,480 INFO L409 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-02-02 18:22:47,480 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-02-02 18:22:47,480 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-02-02 18:22:47,480 INFO L87 Difference]: Start difference. First operand 55 states and 60 transitions. Second operand 4 states. [2018-02-02 18:22:47,525 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 18:22:47,525 INFO L93 Difference]: Finished difference Result 54 states and 59 transitions. [2018-02-02 18:22:47,526 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-02-02 18:22:47,526 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 15 [2018-02-02 18:22:47,526 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 18:22:47,526 INFO L225 Difference]: With dead ends: 54 [2018-02-02 18:22:47,526 INFO L226 Difference]: Without dead ends: 54 [2018-02-02 18:22:47,527 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 18:22:47,527 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2018-02-02 18:22:47,529 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 54. [2018-02-02 18:22:47,529 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 54 states. [2018-02-02 18:22:47,529 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 59 transitions. [2018-02-02 18:22:47,529 INFO L78 Accepts]: Start accepts. Automaton has 54 states and 59 transitions. Word has length 15 [2018-02-02 18:22:47,530 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 18:22:47,530 INFO L432 AbstractCegarLoop]: Abstraction has 54 states and 59 transitions. [2018-02-02 18:22:47,530 INFO L433 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-02-02 18:22:47,530 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states and 59 transitions. [2018-02-02 18:22:47,530 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2018-02-02 18:22:47,530 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 18:22:47,530 INFO L351 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-02-02 18:22:47,530 INFO L371 AbstractCegarLoop]: === Iteration 4 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 18:22:47,530 INFO L82 PathProgramCache]: Analyzing trace with hash -1993659114, now seen corresponding path program 1 times [2018-02-02 18:22:47,530 INFO L213 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 18:22:47,531 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 18:22:47,531 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:22:47,531 INFO L109 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 18:22:47,531 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:22:47,540 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:22:47,541 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 18:22:47,632 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 18:22:47,632 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-02-02 18:22:47,633 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2018-02-02 18:22:47,633 INFO L409 AbstractCegarLoop]: Interpolant automaton has 8 states [2018-02-02 18:22:47,633 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2018-02-02 18:22:47,633 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=38, Unknown=0, NotChecked=0, Total=56 [2018-02-02 18:22:47,633 INFO L87 Difference]: Start difference. First operand 54 states and 59 transitions. Second operand 8 states. [2018-02-02 18:22:47,720 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 18:22:47,720 INFO L93 Difference]: Finished difference Result 53 states and 58 transitions. [2018-02-02 18:22:47,721 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-02-02 18:22:47,721 INFO L78 Accepts]: Start accepts. Automaton has 8 states. Word has length 15 [2018-02-02 18:22:47,721 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 18:22:47,721 INFO L225 Difference]: With dead ends: 53 [2018-02-02 18:22:47,722 INFO L226 Difference]: Without dead ends: 53 [2018-02-02 18:22:47,722 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 18:22:47,722 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 53 states. [2018-02-02 18:22:47,724 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 53 to 53. [2018-02-02 18:22:47,725 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 53 states. [2018-02-02 18:22:47,726 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 53 states to 53 states and 58 transitions. [2018-02-02 18:22:47,726 INFO L78 Accepts]: Start accepts. Automaton has 53 states and 58 transitions. Word has length 15 [2018-02-02 18:22:47,726 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 18:22:47,726 INFO L432 AbstractCegarLoop]: Abstraction has 53 states and 58 transitions. [2018-02-02 18:22:47,726 INFO L433 AbstractCegarLoop]: Interpolant automaton has 8 states. [2018-02-02 18:22:47,726 INFO L276 IsEmpty]: Start isEmpty. Operand 53 states and 58 transitions. [2018-02-02 18:22:47,727 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2018-02-02 18:22:47,727 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 18:22:47,727 INFO L351 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-02-02 18:22:47,727 INFO L371 AbstractCegarLoop]: === Iteration 5 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 18:22:47,727 INFO L82 PathProgramCache]: Analyzing trace with hash -1673890416, now seen corresponding path program 1 times [2018-02-02 18:22:47,727 INFO L213 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 18:22:47,727 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 18:22:47,728 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:22:47,728 INFO L109 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 18:22:47,728 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:22:47,738 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:22:47,738 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 18:22:47,758 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 18:22:47,758 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-02-02 18:22:47,759 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-02-02 18:22:47,759 INFO L409 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-02-02 18:22:47,759 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-02-02 18:22:47,759 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-02-02 18:22:47,759 INFO L87 Difference]: Start difference. First operand 53 states and 58 transitions. Second operand 4 states. [2018-02-02 18:22:47,802 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 18:22:47,802 INFO L93 Difference]: Finished difference Result 52 states and 57 transitions. [2018-02-02 18:22:47,803 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-02-02 18:22:47,803 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 16 [2018-02-02 18:22:47,803 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 18:22:47,803 INFO L225 Difference]: With dead ends: 52 [2018-02-02 18:22:47,803 INFO L226 Difference]: Without dead ends: 52 [2018-02-02 18:22:47,804 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 18:22:47,804 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 52 states. [2018-02-02 18:22:47,806 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 52 to 52. [2018-02-02 18:22:47,806 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 52 states. [2018-02-02 18:22:47,807 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 52 states to 52 states and 57 transitions. [2018-02-02 18:22:47,807 INFO L78 Accepts]: Start accepts. Automaton has 52 states and 57 transitions. Word has length 16 [2018-02-02 18:22:47,807 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 18:22:47,808 INFO L432 AbstractCegarLoop]: Abstraction has 52 states and 57 transitions. [2018-02-02 18:22:47,808 INFO L433 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-02-02 18:22:47,808 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 57 transitions. [2018-02-02 18:22:47,808 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2018-02-02 18:22:47,808 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 18:22:47,808 INFO L351 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-02-02 18:22:47,808 INFO L371 AbstractCegarLoop]: === Iteration 6 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 18:22:47,809 INFO L82 PathProgramCache]: Analyzing trace with hash -1673890415, now seen corresponding path program 1 times [2018-02-02 18:22:47,809 INFO L213 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 18:22:47,809 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 18:22:47,809 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:22:47,809 INFO L109 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 18:22:47,810 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:22:47,817 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:22:47,818 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 18:22:47,866 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 18:22:47,867 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-02-02 18:22:47,867 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-02-02 18:22:47,867 INFO L409 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-02-02 18:22:47,867 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-02-02 18:22:47,867 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-02-02 18:22:47,867 INFO L87 Difference]: Start difference. First operand 52 states and 57 transitions. Second operand 5 states. [2018-02-02 18:22:47,892 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 18:22:47,892 INFO L93 Difference]: Finished difference Result 51 states and 56 transitions. [2018-02-02 18:22:47,892 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-02-02 18:22:47,892 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 16 [2018-02-02 18:22:47,893 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 18:22:47,893 INFO L225 Difference]: With dead ends: 51 [2018-02-02 18:22:47,893 INFO L226 Difference]: Without dead ends: 51 [2018-02-02 18:22:47,894 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 18:22:47,894 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2018-02-02 18:22:47,895 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 51. [2018-02-02 18:22:47,896 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 51 states. [2018-02-02 18:22:47,896 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 56 transitions. [2018-02-02 18:22:47,897 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 56 transitions. Word has length 16 [2018-02-02 18:22:47,897 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 18:22:47,897 INFO L432 AbstractCegarLoop]: Abstraction has 51 states and 56 transitions. [2018-02-02 18:22:47,897 INFO L433 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-02-02 18:22:47,897 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 56 transitions. [2018-02-02 18:22:47,898 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2018-02-02 18:22:47,898 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 18:22:47,898 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] [2018-02-02 18:22:47,898 INFO L371 AbstractCegarLoop]: === Iteration 7 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 18:22:47,898 INFO L82 PathProgramCache]: Analyzing trace with hash 1745382581, now seen corresponding path program 1 times [2018-02-02 18:22:47,899 INFO L213 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 18:22:47,899 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 18:22:47,899 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:22:47,900 INFO L109 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 18:22:47,900 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:22:47,915 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:22:47,916 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 18:22:47,940 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 18:22:47,941 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-02-02 18:22:47,941 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-02-02 18:22:47,941 INFO L409 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-02-02 18:22:47,941 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-02-02 18:22:47,942 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-02-02 18:22:47,942 INFO L87 Difference]: Start difference. First operand 51 states and 56 transitions. Second operand 5 states. [2018-02-02 18:22:47,998 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 18:22:47,998 INFO L93 Difference]: Finished difference Result 47 states and 52 transitions. [2018-02-02 18:22:47,998 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-02-02 18:22:47,999 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 20 [2018-02-02 18:22:47,999 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 18:22:47,999 INFO L225 Difference]: With dead ends: 47 [2018-02-02 18:22:47,999 INFO L226 Difference]: Without dead ends: 47 [2018-02-02 18:22:48,000 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2018-02-02 18:22:48,000 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2018-02-02 18:22:48,002 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 47. [2018-02-02 18:22:48,002 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 47 states. [2018-02-02 18:22:48,002 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 47 states to 47 states and 52 transitions. [2018-02-02 18:22:48,002 INFO L78 Accepts]: Start accepts. Automaton has 47 states and 52 transitions. Word has length 20 [2018-02-02 18:22:48,003 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 18:22:48,003 INFO L432 AbstractCegarLoop]: Abstraction has 47 states and 52 transitions. [2018-02-02 18:22:48,003 INFO L433 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-02-02 18:22:48,003 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 52 transitions. [2018-02-02 18:22:48,003 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2018-02-02 18:22:48,003 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 18:22:48,004 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] [2018-02-02 18:22:48,004 INFO L371 AbstractCegarLoop]: === Iteration 8 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 18:22:48,004 INFO L82 PathProgramCache]: Analyzing trace with hash 1745382582, now seen corresponding path program 1 times [2018-02-02 18:22:48,004 INFO L213 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 18:22:48,004 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 18:22:48,005 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:22:48,005 INFO L109 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 18:22:48,005 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:22:48,014 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:22:48,015 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 18:22:48,092 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 18:22:48,093 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-02-02 18:22:48,093 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2018-02-02 18:22:48,093 INFO L409 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-02-02 18:22:48,093 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-02-02 18:22:48,093 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2018-02-02 18:22:48,094 INFO L87 Difference]: Start difference. First operand 47 states and 52 transitions. Second operand 9 states. [2018-02-02 18:22:48,217 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 18:22:48,217 INFO L93 Difference]: Finished difference Result 65 states and 74 transitions. [2018-02-02 18:22:48,217 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-02-02 18:22:48,218 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 20 [2018-02-02 18:22:48,218 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 18:22:48,220 INFO L225 Difference]: With dead ends: 65 [2018-02-02 18:22:48,220 INFO L226 Difference]: Without dead ends: 65 [2018-02-02 18:22:48,221 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 14 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 16 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=57, Invalid=153, Unknown=0, NotChecked=0, Total=210 [2018-02-02 18:22:48,221 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 65 states. [2018-02-02 18:22:48,223 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 65 to 60. [2018-02-02 18:22:48,224 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 60 states. [2018-02-02 18:22:48,224 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 60 states to 60 states and 71 transitions. [2018-02-02 18:22:48,224 INFO L78 Accepts]: Start accepts. Automaton has 60 states and 71 transitions. Word has length 20 [2018-02-02 18:22:48,225 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 18:22:48,225 INFO L432 AbstractCegarLoop]: Abstraction has 60 states and 71 transitions. [2018-02-02 18:22:48,225 INFO L433 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-02-02 18:22:48,225 INFO L276 IsEmpty]: Start isEmpty. Operand 60 states and 71 transitions. [2018-02-02 18:22:48,225 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2018-02-02 18:22:48,225 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 18:22:48,226 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] [2018-02-02 18:22:48,226 INFO L371 AbstractCegarLoop]: === Iteration 9 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 18:22:48,226 INFO L82 PathProgramCache]: Analyzing trace with hash 1818413707, now seen corresponding path program 1 times [2018-02-02 18:22:48,226 INFO L213 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 18:22:48,226 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 18:22:48,227 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:22:48,227 INFO L109 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 18:22:48,227 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:22:48,237 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:22:48,238 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 18:22:48,335 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 18:22:48,336 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-02-02 18:22:48,336 INFO L213 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 18:22:48,344 INFO L109 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 18:22:48,364 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:22:48,372 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-02-02 18:22:48,441 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 18:22:48,442 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-02-02 18:22:48,449 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 18:22:48,449 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 18:22:48,456 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 18:22:48,456 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:24, output treesize:19 [2018-02-02 18:22:48,485 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:22:48,486 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:22:48,489 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 23 [2018-02-02 18:22:48,489 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-02-02 18:22:48,499 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:22:48,500 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:22:48,500 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 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 18:22:48,500 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 18:22:48,508 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 18:22:48,508 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:30, output treesize:18 [2018-02-02 18:22:48,638 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 18:22:48,654 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-02-02 18:22:48,654 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 12] total 21 [2018-02-02 18:22:48,654 INFO L409 AbstractCegarLoop]: Interpolant automaton has 22 states [2018-02-02 18:22:48,655 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2018-02-02 18:22:48,655 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=57, Invalid=405, Unknown=0, NotChecked=0, Total=462 [2018-02-02 18:22:48,655 INFO L87 Difference]: Start difference. First operand 60 states and 71 transitions. Second operand 22 states. [2018-02-02 18:22:49,046 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 18:22:49,046 INFO L93 Difference]: Finished difference Result 83 states and 96 transitions. [2018-02-02 18:22:49,047 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-02-02 18:22:49,047 INFO L78 Accepts]: Start accepts. Automaton has 22 states. Word has length 23 [2018-02-02 18:22:49,047 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 18:22:49,047 INFO L225 Difference]: With dead ends: 83 [2018-02-02 18:22:49,047 INFO L226 Difference]: Without dead ends: 83 [2018-02-02 18:22:49,048 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 42 GetRequests, 13 SyntacticMatches, 0 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 162 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=152, Invalid=778, Unknown=0, NotChecked=0, Total=930 [2018-02-02 18:22:49,048 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 83 states. [2018-02-02 18:22:49,050 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 83 to 70. [2018-02-02 18:22:49,050 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 70 states. [2018-02-02 18:22:49,050 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 70 states to 70 states and 86 transitions. [2018-02-02 18:22:49,050 INFO L78 Accepts]: Start accepts. Automaton has 70 states and 86 transitions. Word has length 23 [2018-02-02 18:22:49,051 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 18:22:49,051 INFO L432 AbstractCegarLoop]: Abstraction has 70 states and 86 transitions. [2018-02-02 18:22:49,051 INFO L433 AbstractCegarLoop]: Interpolant automaton has 22 states. [2018-02-02 18:22:49,051 INFO L276 IsEmpty]: Start isEmpty. Operand 70 states and 86 transitions. [2018-02-02 18:22:49,051 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2018-02-02 18:22:49,051 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 18:22:49,051 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] [2018-02-02 18:22:49,051 INFO L371 AbstractCegarLoop]: === Iteration 10 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 18:22:49,051 INFO L82 PathProgramCache]: Analyzing trace with hash -557502487, now seen corresponding path program 1 times [2018-02-02 18:22:49,051 INFO L213 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 18:22:49,052 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 18:22:49,052 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:22:49,052 INFO L109 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 18:22:49,052 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:22:49,058 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:22:49,059 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 18:22:49,087 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 18:22:49,088 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-02-02 18:22:49,088 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-02-02 18:22:49,088 INFO L409 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-02-02 18:22:49,088 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-02-02 18:22:49,088 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2018-02-02 18:22:49,088 INFO L87 Difference]: Start difference. First operand 70 states and 86 transitions. Second operand 6 states. [2018-02-02 18:22:49,139 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 18:22:49,139 INFO L93 Difference]: Finished difference Result 72 states and 89 transitions. [2018-02-02 18:22:49,139 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-02-02 18:22:49,139 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 25 [2018-02-02 18:22:49,139 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 18:22:49,140 INFO L225 Difference]: With dead ends: 72 [2018-02-02 18:22:49,141 INFO L226 Difference]: Without dead ends: 72 [2018-02-02 18:22:49,141 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 18:22:49,141 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 72 states. [2018-02-02 18:22:49,144 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 72 to 69. [2018-02-02 18:22:49,145 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 69 states. [2018-02-02 18:22:49,145 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 69 states to 69 states and 83 transitions. [2018-02-02 18:22:49,146 INFO L78 Accepts]: Start accepts. Automaton has 69 states and 83 transitions. Word has length 25 [2018-02-02 18:22:49,146 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 18:22:49,146 INFO L432 AbstractCegarLoop]: Abstraction has 69 states and 83 transitions. [2018-02-02 18:22:49,146 INFO L433 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-02-02 18:22:49,146 INFO L276 IsEmpty]: Start isEmpty. Operand 69 states and 83 transitions. [2018-02-02 18:22:49,147 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2018-02-02 18:22:49,147 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 18:22:49,147 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] [2018-02-02 18:22:49,147 INFO L371 AbstractCegarLoop]: === Iteration 11 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 18:22:49,147 INFO L82 PathProgramCache]: Analyzing trace with hash -557502486, now seen corresponding path program 1 times [2018-02-02 18:22:49,147 INFO L213 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 18:22:49,148 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 18:22:49,148 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:22:49,148 INFO L109 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 18:22:49,149 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:22:49,157 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:22:49,158 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 18:22:49,218 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 18:22:49,219 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-02-02 18:22:49,219 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2018-02-02 18:22:49,219 INFO L409 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-02-02 18:22:49,219 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-02-02 18:22:49,220 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=54, Unknown=0, NotChecked=0, Total=72 [2018-02-02 18:22:49,220 INFO L87 Difference]: Start difference. First operand 69 states and 83 transitions. Second operand 9 states. [2018-02-02 18:22:49,329 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 18:22:49,329 INFO L93 Difference]: Finished difference Result 98 states and 120 transitions. [2018-02-02 18:22:49,329 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-02-02 18:22:49,329 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 25 [2018-02-02 18:22:49,329 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 18:22:49,330 INFO L225 Difference]: With dead ends: 98 [2018-02-02 18:22:49,330 INFO L226 Difference]: Without dead ends: 98 [2018-02-02 18:22:49,330 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 18 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=32, Invalid=100, Unknown=0, NotChecked=0, Total=132 [2018-02-02 18:22:49,330 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 98 states. [2018-02-02 18:22:49,334 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 98 to 80. [2018-02-02 18:22:49,334 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 80 states. [2018-02-02 18:22:49,335 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 80 states to 80 states and 98 transitions. [2018-02-02 18:22:49,335 INFO L78 Accepts]: Start accepts. Automaton has 80 states and 98 transitions. Word has length 25 [2018-02-02 18:22:49,335 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 18:22:49,335 INFO L432 AbstractCegarLoop]: Abstraction has 80 states and 98 transitions. [2018-02-02 18:22:49,335 INFO L433 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-02-02 18:22:49,335 INFO L276 IsEmpty]: Start isEmpty. Operand 80 states and 98 transitions. [2018-02-02 18:22:49,335 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2018-02-02 18:22:49,335 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 18:22:49,335 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] [2018-02-02 18:22:49,335 INFO L371 AbstractCegarLoop]: === Iteration 12 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 18:22:49,335 INFO L82 PathProgramCache]: Analyzing trace with hash -59760490, now seen corresponding path program 2 times [2018-02-02 18:22:49,336 INFO L213 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 18:22:49,336 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 18:22:49,336 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:22:49,336 INFO L109 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 18:22:49,336 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:22:49,342 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:22:49,343 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 18:22:49,522 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 18:22:49,523 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-02-02 18:22:49,523 INFO L213 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 18:22:49,528 INFO L109 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-02-02 18:22:49,544 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-02-02 18:22:49,544 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-02-02 18:22:49,546 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-02-02 18:22:49,567 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 18:22:49,567 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-02-02 18:22:49,572 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 18:22:49,572 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:18, output treesize:17 [2018-02-02 18:22:49,610 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:22:49,610 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:22:49,611 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 4 [2018-02-02 18:22:49,611 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-02-02 18:22:49,615 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 18:22:49,615 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:22, output treesize:16 [2018-02-02 18:22:49,667 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 18:22:49,670 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 18:22:49,670 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 18:22:49,672 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 18:22:49,682 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 18:22:49,682 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:42, output treesize:38 [2018-02-02 18:22:49,718 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 18:22:49,721 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 10 [2018-02-02 18:22:49,721 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 18:22:49,725 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 18:22:49,733 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 18:22:49,734 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 6 variables, input treesize:52, output treesize:48 [2018-02-02 18:22:51,913 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 18:22:51,915 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 18:22:51,915 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 18:22:51,921 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:22:51,925 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 18:22:51,926 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 2 xjuncts. [2018-02-02 18:22:51,934 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-02-02 18:22:51,951 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 18:22:51,951 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 6 variables, input treesize:66, output treesize:43 [2018-02-02 18:22:52,006 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 5 refuted. 2 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 18:22:52,032 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-02-02 18:22:52,032 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 15] total 25 [2018-02-02 18:22:52,032 INFO L409 AbstractCegarLoop]: Interpolant automaton has 26 states [2018-02-02 18:22:52,033 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2018-02-02 18:22:52,033 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=63, Invalid=586, Unknown=1, NotChecked=0, Total=650 [2018-02-02 18:22:52,033 INFO L87 Difference]: Start difference. First operand 80 states and 98 transitions. Second operand 26 states. [2018-02-02 18:23:11,336 WARN L146 SmtUtils]: Spent 8079ms on a formula simplification. DAG size of input: 74 DAG size of output 72 [2018-02-02 18:23:23,141 WARN L146 SmtUtils]: Spent 8038ms on a formula simplification. DAG size of input: 61 DAG size of output 57 [2018-02-02 18:23:32,004 WARN L146 SmtUtils]: Spent 8043ms on a formula simplification. DAG size of input: 70 DAG size of output 60 [2018-02-02 18:23:49,661 WARN L146 SmtUtils]: Spent 703ms on a formula simplification. DAG size of input: 55 DAG size of output 54 [2018-02-02 18:24:01,120 WARN L146 SmtUtils]: Spent 111ms on a formula simplification. DAG size of input: 59 DAG size of output 55 [2018-02-02 18:24:04,758 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 18:24:04,758 INFO L93 Difference]: Finished difference Result 199 states and 237 transitions. [2018-02-02 18:24:04,758 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2018-02-02 18:24:04,758 INFO L78 Accepts]: Start accepts. Automaton has 26 states. Word has length 26 [2018-02-02 18:24:04,759 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 18:24:04,759 INFO L225 Difference]: With dead ends: 199 [2018-02-02 18:24:04,759 INFO L226 Difference]: Without dead ends: 199 [2018-02-02 18:24:04,760 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 67 GetRequests, 13 SyntacticMatches, 1 SemanticMatches, 53 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 571 ImplicationChecksByTransitivity, 54.9s TimeCoverageRelationStatistics Valid=410, Invalid=2547, Unknown=13, NotChecked=0, Total=2970 [2018-02-02 18:24:04,760 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 199 states. [2018-02-02 18:24:04,762 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 199 to 79. [2018-02-02 18:24:04,762 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 79 states. [2018-02-02 18:24:04,763 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 79 states to 79 states and 97 transitions. [2018-02-02 18:24:04,763 INFO L78 Accepts]: Start accepts. Automaton has 79 states and 97 transitions. Word has length 26 [2018-02-02 18:24:04,763 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 18:24:04,763 INFO L432 AbstractCegarLoop]: Abstraction has 79 states and 97 transitions. [2018-02-02 18:24:04,763 INFO L433 AbstractCegarLoop]: Interpolant automaton has 26 states. [2018-02-02 18:24:04,763 INFO L276 IsEmpty]: Start isEmpty. Operand 79 states and 97 transitions. [2018-02-02 18:24:04,763 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2018-02-02 18:24:04,763 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 18:24:04,763 INFO L351 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-02-02 18:24:04,763 INFO L371 AbstractCegarLoop]: === Iteration 13 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 18:24:04,764 INFO L82 PathProgramCache]: Analyzing trace with hash 933708271, now seen corresponding path program 1 times [2018-02-02 18:24:04,764 INFO L213 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 18:24:04,764 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 18:24:04,764 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:24:04,764 INFO L107 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-02-02 18:24:04,764 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:24:04,770 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:24:04,771 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 18:24:04,809 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 1 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 18:24:04,809 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-02-02 18:24:04,810 INFO L213 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 18:24:04,818 INFO L109 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 18:24:04,833 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:24:04,835 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-02-02 18:24:04,839 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 1 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 18:24:04,856 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-02-02 18:24:04,856 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 7 [2018-02-02 18:24:04,857 INFO L409 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-02-02 18:24:04,857 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-02-02 18:24:04,857 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2018-02-02 18:24:04,857 INFO L87 Difference]: Start difference. First operand 79 states and 97 transitions. Second operand 7 states. [2018-02-02 18:24:04,941 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 18:24:04,941 INFO L93 Difference]: Finished difference Result 142 states and 165 transitions. [2018-02-02 18:24:04,941 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-02-02 18:24:04,942 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 32 [2018-02-02 18:24:04,942 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 18:24:04,942 INFO L225 Difference]: With dead ends: 142 [2018-02-02 18:24:04,943 INFO L226 Difference]: Without dead ends: 142 [2018-02-02 18:24:04,943 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 42 GetRequests, 32 SyntacticMatches, 1 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=31, Invalid=79, Unknown=0, NotChecked=0, Total=110 [2018-02-02 18:24:04,943 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 142 states. [2018-02-02 18:24:04,946 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 142 to 123. [2018-02-02 18:24:04,946 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 123 states. [2018-02-02 18:24:04,947 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 123 states to 123 states and 148 transitions. [2018-02-02 18:24:04,947 INFO L78 Accepts]: Start accepts. Automaton has 123 states and 148 transitions. Word has length 32 [2018-02-02 18:24:04,947 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 18:24:04,947 INFO L432 AbstractCegarLoop]: Abstraction has 123 states and 148 transitions. [2018-02-02 18:24:04,947 INFO L433 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-02-02 18:24:04,948 INFO L276 IsEmpty]: Start isEmpty. Operand 123 states and 148 transitions. [2018-02-02 18:24:04,948 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2018-02-02 18:24:04,948 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 18:24:04,949 INFO L351 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-02-02 18:24:04,949 INFO L371 AbstractCegarLoop]: === Iteration 14 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 18:24:04,949 INFO L82 PathProgramCache]: Analyzing trace with hash 799694765, now seen corresponding path program 1 times [2018-02-02 18:24:04,949 INFO L213 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 18:24:04,949 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 18:24:04,950 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:24:04,950 INFO L109 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 18:24:04,950 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:24:04,978 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:24:04,979 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 18:24:05,160 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 18:24:05,161 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-02-02 18:24:05,161 INFO L213 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 18:24:05,171 INFO L109 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 18:24:05,187 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:24:05,189 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-02-02 18:24:05,194 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 18:24:05,196 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 18:24:05,196 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 18:24:05,197 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 18:24:05,201 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 18:24:05,202 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:25, output treesize:21 [2018-02-02 18:24:05,320 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 18:24:05,328 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 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 18:24:05,329 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-02-02 18:24:05,333 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-02-02 18:24:05,344 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 18:24:05,344 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:38, output treesize:29 [2018-02-02 18:24:05,396 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 18:24:05,413 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-02-02 18:24:05,413 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 10] total 18 [2018-02-02 18:24:05,413 INFO L409 AbstractCegarLoop]: Interpolant automaton has 19 states [2018-02-02 18:24:05,414 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2018-02-02 18:24:05,414 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=43, Invalid=299, Unknown=0, NotChecked=0, Total=342 [2018-02-02 18:24:05,414 INFO L87 Difference]: Start difference. First operand 123 states and 148 transitions. Second operand 19 states. [2018-02-02 18:24:10,201 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 18:24:10,201 INFO L93 Difference]: Finished difference Result 173 states and 204 transitions. [2018-02-02 18:24:10,201 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2018-02-02 18:24:10,201 INFO L78 Accepts]: Start accepts. Automaton has 19 states. Word has length 32 [2018-02-02 18:24:10,201 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 18:24:10,203 INFO L225 Difference]: With dead ends: 173 [2018-02-02 18:24:10,203 INFO L226 Difference]: Without dead ends: 173 [2018-02-02 18:24:10,203 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 52 GetRequests, 26 SyntacticMatches, 0 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 100 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=105, Invalid=651, Unknown=0, NotChecked=0, Total=756 [2018-02-02 18:24:10,203 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 173 states. [2018-02-02 18:24:10,206 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 173 to 130. [2018-02-02 18:24:10,206 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 130 states. [2018-02-02 18:24:10,206 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 130 states to 130 states and 156 transitions. [2018-02-02 18:24:10,207 INFO L78 Accepts]: Start accepts. Automaton has 130 states and 156 transitions. Word has length 32 [2018-02-02 18:24:10,207 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 18:24:10,207 INFO L432 AbstractCegarLoop]: Abstraction has 130 states and 156 transitions. [2018-02-02 18:24:10,207 INFO L433 AbstractCegarLoop]: Interpolant automaton has 19 states. [2018-02-02 18:24:10,207 INFO L276 IsEmpty]: Start isEmpty. Operand 130 states and 156 transitions. [2018-02-02 18:24:10,208 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2018-02-02 18:24:10,208 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 18:24:10,208 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, 1, 1, 1, 1, 1, 1, 1, 1] [2018-02-02 18:24:10,208 INFO L371 AbstractCegarLoop]: === Iteration 15 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 18:24:10,209 INFO L82 PathProgramCache]: Analyzing trace with hash -1376138118, now seen corresponding path program 1 times [2018-02-02 18:24:10,209 INFO L213 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 18:24:10,209 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 18:24:10,209 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:24:10,210 INFO L109 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 18:24:10,210 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:24:10,216 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:24:10,217 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 18:24:10,251 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 18:24:10,252 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-02-02 18:24:10,252 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2018-02-02 18:24:10,252 INFO L409 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-02-02 18:24:10,252 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-02-02 18:24:10,252 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2018-02-02 18:24:10,252 INFO L87 Difference]: Start difference. First operand 130 states and 156 transitions. Second operand 6 states. [2018-02-02 18:24:10,276 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 18:24:10,276 INFO L93 Difference]: Finished difference Result 156 states and 184 transitions. [2018-02-02 18:24:10,276 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-02-02 18:24:10,277 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 36 [2018-02-02 18:24:10,277 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 18:24:10,277 INFO L225 Difference]: With dead ends: 156 [2018-02-02 18:24:10,277 INFO L226 Difference]: Without dead ends: 142 [2018-02-02 18:24:10,277 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=20, Invalid=36, Unknown=0, NotChecked=0, Total=56 [2018-02-02 18:24:10,278 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 142 states. [2018-02-02 18:24:10,280 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 142 to 130. [2018-02-02 18:24:10,280 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 130 states. [2018-02-02 18:24:10,281 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 130 states to 130 states and 152 transitions. [2018-02-02 18:24:10,281 INFO L78 Accepts]: Start accepts. Automaton has 130 states and 152 transitions. Word has length 36 [2018-02-02 18:24:10,281 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 18:24:10,281 INFO L432 AbstractCegarLoop]: Abstraction has 130 states and 152 transitions. [2018-02-02 18:24:10,281 INFO L433 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-02-02 18:24:10,281 INFO L276 IsEmpty]: Start isEmpty. Operand 130 states and 152 transitions. [2018-02-02 18:24:10,282 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2018-02-02 18:24:10,282 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 18:24:10,282 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-02-02 18:24:10,282 INFO L371 AbstractCegarLoop]: === Iteration 16 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 18:24:10,283 INFO L82 PathProgramCache]: Analyzing trace with hash 336762589, now seen corresponding path program 1 times [2018-02-02 18:24:10,283 INFO L213 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 18:24:10,283 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 18:24:10,283 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:24:10,283 INFO L109 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 18:24:10,283 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:24:10,291 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:24:10,292 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 18:24:10,371 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 18:24:10,371 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-02-02 18:24:10,371 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-02-02 18:24:10,371 INFO L409 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-02-02 18:24:10,372 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-02-02 18:24:10,372 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2018-02-02 18:24:10,372 INFO L87 Difference]: Start difference. First operand 130 states and 152 transitions. Second operand 6 states. [2018-02-02 18:24:10,437 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 18:24:10,437 INFO L93 Difference]: Finished difference Result 129 states and 151 transitions. [2018-02-02 18:24:10,438 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-02-02 18:24:10,438 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 39 [2018-02-02 18:24:10,439 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 18:24:10,439 INFO L225 Difference]: With dead ends: 129 [2018-02-02 18:24:10,439 INFO L226 Difference]: Without dead ends: 99 [2018-02-02 18:24:10,439 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 18:24:10,439 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 99 states. [2018-02-02 18:24:10,440 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 99 to 95. [2018-02-02 18:24:10,440 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 95 states. [2018-02-02 18:24:10,441 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 95 states to 95 states and 103 transitions. [2018-02-02 18:24:10,441 INFO L78 Accepts]: Start accepts. Automaton has 95 states and 103 transitions. Word has length 39 [2018-02-02 18:24:10,441 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 18:24:10,441 INFO L432 AbstractCegarLoop]: Abstraction has 95 states and 103 transitions. [2018-02-02 18:24:10,441 INFO L433 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-02-02 18:24:10,441 INFO L276 IsEmpty]: Start isEmpty. Operand 95 states and 103 transitions. [2018-02-02 18:24:10,442 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2018-02-02 18:24:10,442 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 18:24:10,442 INFO L351 BasicCegarLoop]: trace histogram [3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-02-02 18:24:10,442 INFO L371 AbstractCegarLoop]: === Iteration 17 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 18:24:10,442 INFO L82 PathProgramCache]: Analyzing trace with hash 2118432619, now seen corresponding path program 1 times [2018-02-02 18:24:10,442 INFO L213 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 18:24:10,443 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 18:24:10,443 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:24:10,443 INFO L109 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 18:24:10,443 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:24:10,454 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:24:10,455 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 18:24:10,787 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 0 proven. 13 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 18:24:10,787 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-02-02 18:24:10,787 INFO L213 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 18:24:10,791 INFO L109 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 18:24:10,804 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:24:10,806 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-02-02 18:24:10,810 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 18:24:10,810 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-02-02 18:24:10,816 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 18:24:10,816 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 18:24:10,821 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 18:24:10,821 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:22, output treesize:20 [2018-02-02 18:24:10,843 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:24:10,844 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:24:10,844 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 18:24:10,844 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-02-02 18:24:10,852 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 18:24:10,852 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 18:24:10,857 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 18:24:10,857 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:31, output treesize:24 [2018-02-02 18:24:10,891 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 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 18:24:10,892 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 18:24:10,893 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 18:24:10,894 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 18:24:10,898 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 18:24:10,898 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:34, output treesize:30 [2018-02-02 18:24:10,929 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 18:24:10,931 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 18:24:10,931 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 18:24:10,934 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 18:24:10,938 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 18:24:10,938 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:41, output treesize:37 [2018-02-02 18:24:11,369 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 18:24:11,374 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 18:24:11,375 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-02-02 18:24:11,380 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 18:24:11,381 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-02-02 18:24:11,383 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-02-02 18:24:11,390 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 18:24:11,390 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 4 variables, input treesize:47, output treesize:27 [2018-02-02 18:24:11,558 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 2 proven. 11 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 18:24:11,576 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-02-02 18:24:11,576 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 16] total 27 [2018-02-02 18:24:11,576 INFO L409 AbstractCegarLoop]: Interpolant automaton has 28 states [2018-02-02 18:24:11,577 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2018-02-02 18:24:11,577 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=72, Invalid=684, Unknown=0, NotChecked=0, Total=756 [2018-02-02 18:24:11,577 INFO L87 Difference]: Start difference. First operand 95 states and 103 transitions. Second operand 28 states. [2018-02-02 18:24:12,183 WARN L146 SmtUtils]: Spent 170ms on a formula simplification. DAG size of input: 58 DAG size of output 41 [2018-02-02 18:24:12,502 WARN L146 SmtUtils]: Spent 238ms on a formula simplification. DAG size of input: 61 DAG size of output 41 [2018-02-02 18:24:12,787 WARN L146 SmtUtils]: Spent 245ms on a formula simplification. DAG size of input: 65 DAG size of output 51 [2018-02-02 18:24:13,063 WARN L146 SmtUtils]: Spent 207ms on a formula simplification. DAG size of input: 59 DAG size of output 48 [2018-02-02 18:24:13,282 WARN L146 SmtUtils]: Spent 162ms on a formula simplification. DAG size of input: 66 DAG size of output 50 [2018-02-02 18:24:13,596 WARN L146 SmtUtils]: Spent 175ms on a formula simplification. DAG size of input: 55 DAG size of output 44 [2018-02-02 18:24:14,000 WARN L146 SmtUtils]: Spent 203ms on a formula simplification. DAG size of input: 59 DAG size of output 45 [2018-02-02 18:24:14,310 WARN L146 SmtUtils]: Spent 229ms on a formula simplification. DAG size of input: 68 DAG size of output 50 [2018-02-02 18:24:14,596 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 18:24:14,596 INFO L93 Difference]: Finished difference Result 109 states and 117 transitions. [2018-02-02 18:24:14,596 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2018-02-02 18:24:14,596 INFO L78 Accepts]: Start accepts. Automaton has 28 states. Word has length 39 [2018-02-02 18:24:14,596 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 18:24:14,597 INFO L225 Difference]: With dead ends: 109 [2018-02-02 18:24:14,597 INFO L226 Difference]: Without dead ends: 67 [2018-02-02 18:24:14,597 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 70 GetRequests, 24 SyntacticMatches, 3 SemanticMatches, 43 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 333 ImplicationChecksByTransitivity, 3.0s TimeCoverageRelationStatistics Valid=272, Invalid=1708, Unknown=0, NotChecked=0, Total=1980 [2018-02-02 18:24:14,597 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 67 states. [2018-02-02 18:24:14,598 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 67 to 67. [2018-02-02 18:24:14,598 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 67 states. [2018-02-02 18:24:14,598 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 67 states to 67 states and 73 transitions. [2018-02-02 18:24:14,598 INFO L78 Accepts]: Start accepts. Automaton has 67 states and 73 transitions. Word has length 39 [2018-02-02 18:24:14,598 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 18:24:14,598 INFO L432 AbstractCegarLoop]: Abstraction has 67 states and 73 transitions. [2018-02-02 18:24:14,599 INFO L433 AbstractCegarLoop]: Interpolant automaton has 28 states. [2018-02-02 18:24:14,599 INFO L276 IsEmpty]: Start isEmpty. Operand 67 states and 73 transitions. [2018-02-02 18:24:14,599 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2018-02-02 18:24:14,599 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 18:24:14,599 INFO L351 BasicCegarLoop]: trace histogram [3, 3, 3, 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] [2018-02-02 18:24:14,599 INFO L371 AbstractCegarLoop]: === Iteration 18 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 18:24:14,599 INFO L82 PathProgramCache]: Analyzing trace with hash -2098962228, now seen corresponding path program 2 times [2018-02-02 18:24:14,599 INFO L213 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 18:24:14,599 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 18:24:14,600 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:24:14,600 INFO L109 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 18:24:14,600 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:24:14,610 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:24:14,610 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 18:24:14,915 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 18:24:14,915 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-02-02 18:24:14,915 INFO L213 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 18:24:14,920 INFO L109 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-02-02 18:24:14,935 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-02-02 18:24:14,936 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-02-02 18:24:14,938 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-02-02 18:24:14,950 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 18:24:14,950 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-02-02 18:24:14,952 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 18:24:14,952 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:10, output treesize:9 [2018-02-02 18:24:14,978 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:24:14,978 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:24:14,979 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 18:24:14,979 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-02-02 18:24:14,980 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 18:24:14,980 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:14, output treesize:8 [2018-02-02 18:24:15,006 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 14 treesize of output 11 [2018-02-02 18:24:15,008 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 18:24:15,008 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 18:24:15,009 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 18:24:15,012 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 18:24:15,012 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:29, output treesize:25 [2018-02-02 18:24:16,237 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 18:24:16,238 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 18:24:16,239 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 18:24:16,242 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 18:24:16,250 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 18:24:16,250 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:53, output treesize:49 [2018-02-02 18:24:16,550 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 43 treesize of output 37 [2018-02-02 18:24:16,552 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 9 treesize of output 1 [2018-02-02 18:24:16,552 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 18:24:16,557 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:24:16,561 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 24 treesize of output 35 [2018-02-02 18:24:16,562 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 2 xjuncts. [2018-02-02 18:24:16,569 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-02-02 18:24:16,580 INFO L267 ElimStorePlain]: Start of recursive call 1: 4 dim-0 vars, 1 dim-2 vars, End of recursive call: and 2 xjuncts. [2018-02-02 18:24:16,580 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 5 variables, input treesize:65, output treesize:43 [2018-02-02 18:24:16,675 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 18:24:16,692 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-02-02 18:24:16,692 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 19] total 32 [2018-02-02 18:24:16,693 INFO L409 AbstractCegarLoop]: Interpolant automaton has 33 states [2018-02-02 18:24:16,693 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2018-02-02 18:24:16,693 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=79, Invalid=977, Unknown=0, NotChecked=0, Total=1056 [2018-02-02 18:24:16,693 INFO L87 Difference]: Start difference. First operand 67 states and 73 transitions. Second operand 33 states. [2018-02-02 18:24:19,380 WARN L146 SmtUtils]: Spent 132ms on a formula simplification. DAG size of input: 78 DAG size of output 53 [2018-02-02 18:24:21,492 WARN L146 SmtUtils]: Spent 2058ms on a formula simplification. DAG size of input: 43 DAG size of output 37 [2018-02-02 18:24:24,455 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 18:24:24,456 INFO L93 Difference]: Finished difference Result 81 states and 86 transitions. [2018-02-02 18:24:24,456 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2018-02-02 18:24:24,456 INFO L78 Accepts]: Start accepts. Automaton has 33 states. Word has length 39 [2018-02-02 18:24:24,456 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 18:24:24,456 INFO L225 Difference]: With dead ends: 81 [2018-02-02 18:24:24,456 INFO L226 Difference]: Without dead ends: 81 [2018-02-02 18:24:24,457 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 76 GetRequests, 23 SyntacticMatches, 0 SemanticMatches, 53 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 468 ImplicationChecksByTransitivity, 6.7s TimeCoverageRelationStatistics Valid=273, Invalid=2697, Unknown=0, NotChecked=0, Total=2970 [2018-02-02 18:24:24,457 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 81 states. [2018-02-02 18:24:24,458 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 81 to 55. [2018-02-02 18:24:24,458 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 55 states. [2018-02-02 18:24:24,458 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 60 transitions. [2018-02-02 18:24:24,458 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 60 transitions. Word has length 39 [2018-02-02 18:24:24,458 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 18:24:24,458 INFO L432 AbstractCegarLoop]: Abstraction has 55 states and 60 transitions. [2018-02-02 18:24:24,458 INFO L433 AbstractCegarLoop]: Interpolant automaton has 33 states. [2018-02-02 18:24:24,458 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 60 transitions. [2018-02-02 18:24:24,458 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2018-02-02 18:24:24,459 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 18:24:24,459 INFO L351 BasicCegarLoop]: trace histogram [3, 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 18:24:24,459 INFO L371 AbstractCegarLoop]: === Iteration 19 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 18:24:24,459 INFO L82 PathProgramCache]: Analyzing trace with hash -1474943839, now seen corresponding path program 1 times [2018-02-02 18:24:24,459 INFO L213 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 18:24:24,459 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 18:24:24,459 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:24:24,460 INFO L107 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-02-02 18:24:24,460 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:24:24,466 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:24:24,467 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 18:24:24,708 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 0 proven. 14 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 18:24:24,708 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-02-02 18:24:24,708 INFO L213 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 18:24:24,713 INFO L109 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 18:24:24,728 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:24:24,730 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-02-02 18:24:24,733 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-02-02 18:24:24,733 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-02-02 18:24:24,738 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 18:24:24,739 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 18:24:24,743 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 18:24:24,743 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:24, output treesize:19 [2018-02-02 18:24:24,787 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:24:24,788 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:24:24,788 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 18:24:24,789 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-02-02 18:24:24,797 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:24:24,797 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:24:24,798 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 18:24:24,798 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 18:24:24,802 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 18:24:24,802 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:30, output treesize:16 [2018-02-02 18:24:25,054 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 0 proven. 14 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 18:24:25,072 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-02-02 18:24:25,072 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 18] total 35 [2018-02-02 18:24:25,072 INFO L409 AbstractCegarLoop]: Interpolant automaton has 36 states [2018-02-02 18:24:25,072 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 36 interpolants. [2018-02-02 18:24:25,072 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=113, Invalid=1147, Unknown=0, NotChecked=0, Total=1260 [2018-02-02 18:24:25,072 INFO L87 Difference]: Start difference. First operand 55 states and 60 transitions. Second operand 36 states. [2018-02-02 18:24:26,194 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 18:24:26,194 INFO L93 Difference]: Finished difference Result 94 states and 100 transitions. [2018-02-02 18:24:26,194 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2018-02-02 18:24:26,194 INFO L78 Accepts]: Start accepts. Automaton has 36 states. Word has length 39 [2018-02-02 18:24:26,194 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 18:24:26,195 INFO L225 Difference]: With dead ends: 94 [2018-02-02 18:24:26,195 INFO L226 Difference]: Without dead ends: 89 [2018-02-02 18:24:26,195 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 82 GetRequests, 24 SyntacticMatches, 0 SemanticMatches, 58 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1081 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=388, Invalid=3152, Unknown=0, NotChecked=0, Total=3540 [2018-02-02 18:24:26,195 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 89 states. [2018-02-02 18:24:26,196 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 89 to 70. [2018-02-02 18:24:26,196 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 70 states. [2018-02-02 18:24:26,196 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 70 states to 70 states and 77 transitions. [2018-02-02 18:24:26,197 INFO L78 Accepts]: Start accepts. Automaton has 70 states and 77 transitions. Word has length 39 [2018-02-02 18:24:26,197 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 18:24:26,197 INFO L432 AbstractCegarLoop]: Abstraction has 70 states and 77 transitions. [2018-02-02 18:24:26,197 INFO L433 AbstractCegarLoop]: Interpolant automaton has 36 states. [2018-02-02 18:24:26,197 INFO L276 IsEmpty]: Start isEmpty. Operand 70 states and 77 transitions. [2018-02-02 18:24:26,197 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2018-02-02 18:24:26,197 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 18:24:26,197 INFO L351 BasicCegarLoop]: trace histogram [3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-02-02 18:24:26,197 INFO L371 AbstractCegarLoop]: === Iteration 20 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 18:24:26,198 INFO L82 PathProgramCache]: Analyzing trace with hash -1474934803, now seen corresponding path program 1 times [2018-02-02 18:24:26,198 INFO L213 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 18:24:26,198 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 18:24:26,198 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:24:26,198 INFO L109 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 18:24:26,199 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:24:26,206 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:24:26,207 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 18:24:26,653 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 0 proven. 13 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 18:24:26,654 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-02-02 18:24:26,654 INFO L213 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 18:24:26,662 INFO L109 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 18:24:26,682 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:24:26,686 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-02-02 18:24:26,697 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 18:24:26,698 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-02-02 18:24:26,703 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 18:24:26,703 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 18:24:26,707 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 18:24:26,708 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:16, output treesize:14 [2018-02-02 18:24:26,751 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:24:26,753 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 18:24:26,754 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-02-02 18:24:26,765 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:24:26,766 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:24:26,766 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 18:24:26,767 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 18:24:26,773 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 18:24:26,773 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:25, output treesize:18 [2018-02-02 18:24:26,832 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 18:24:26,834 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 18:24:26,834 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 18:24:26,835 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 18:24:26,839 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-02-02 18:24:26,839 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:28, output treesize:24 [2018-02-02 18:24:26,862 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 18:24:26,863 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 18:24:26,863 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 18:24:26,868 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 18:24:26,872 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 18:24:26,872 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:35, output treesize:31 [2018-02-02 18:24:27,043 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 18:24:27,046 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 18:24:27,046 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 18:24:27,064 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 18:24:27,064 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 2 xjuncts. [2018-02-02 18:24:27,066 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-02-02 18:24:27,071 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 18:24:27,071 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 3 variables, input treesize:41, output treesize:23 [2018-02-02 18:24:27,232 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 2 proven. 11 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 18:24:27,249 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-02-02 18:24:27,250 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 17] total 32 [2018-02-02 18:24:27,250 INFO L409 AbstractCegarLoop]: Interpolant automaton has 33 states [2018-02-02 18:24:27,250 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2018-02-02 18:24:27,250 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=85, Invalid=971, Unknown=0, NotChecked=0, Total=1056 [2018-02-02 18:24:27,250 INFO L87 Difference]: Start difference. First operand 70 states and 77 transitions. Second operand 33 states. [2018-02-02 18:24:28,246 WARN L146 SmtUtils]: Spent 604ms on a formula simplification. DAG size of input: 56 DAG size of output 51 Received shutdown request... [2018-02-02 18:24:30,346 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-02-02 18:24:30,346 WARN L491 AbstractCegarLoop]: Verification canceled [2018-02-02 18:24:30,349 WARN L185 ceAbstractionStarter]: Timeout [2018-02-02 18:24:30,349 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 02.02 06:24:30 BoogieIcfgContainer [2018-02-02 18:24:30,349 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-02-02 18:24:30,350 INFO L168 Benchmark]: Toolchain (without parser) took 103835.09 ms. Allocated memory was 400.0 MB in the beginning and 705.2 MB in the end (delta: 305.1 MB). Free memory was 358.0 MB in the beginning and 647.8 MB in the end (delta: -289.7 MB). Peak memory consumption was 15.4 MB. Max. memory is 5.3 GB. [2018-02-02 18:24:30,351 INFO L168 Benchmark]: CDTParser took 0.10 ms. Allocated memory is still 400.0 MB. Free memory is still 363.3 MB. There was no memory consumed. Max. memory is 5.3 GB. [2018-02-02 18:24:30,351 INFO L168 Benchmark]: CACSL2BoogieTranslator took 159.78 ms. Allocated memory is still 400.0 MB. Free memory was 356.7 MB in the beginning and 346.1 MB in the end (delta: 10.6 MB). Peak memory consumption was 10.6 MB. Max. memory is 5.3 GB. [2018-02-02 18:24:30,351 INFO L168 Benchmark]: Boogie Preprocessor took 29.64 ms. Allocated memory is still 400.0 MB. Free memory was 346.1 MB in the beginning and 344.8 MB in the end (delta: 1.3 MB). Peak memory consumption was 1.3 MB. Max. memory is 5.3 GB. [2018-02-02 18:24:30,351 INFO L168 Benchmark]: RCFGBuilder took 215.94 ms. Allocated memory is still 400.0 MB. Free memory was 344.8 MB in the beginning and 322.2 MB in the end (delta: 22.5 MB). Peak memory consumption was 22.5 MB. Max. memory is 5.3 GB. [2018-02-02 18:24:30,351 INFO L168 Benchmark]: TraceAbstraction took 103426.96 ms. Allocated memory was 400.0 MB in the beginning and 705.2 MB in the end (delta: 305.1 MB). Free memory was 322.2 MB in the beginning and 647.8 MB in the end (delta: -325.5 MB). There was no memory consumed. Max. memory is 5.3 GB. [2018-02-02 18:24:30,352 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.10 ms. Allocated memory is still 400.0 MB. Free memory is still 363.3 MB. There was no memory consumed. Max. memory is 5.3 GB. * CACSL2BoogieTranslator took 159.78 ms. Allocated memory is still 400.0 MB. Free memory was 356.7 MB in the beginning and 346.1 MB in the end (delta: 10.6 MB). Peak memory consumption was 10.6 MB. Max. memory is 5.3 GB. * Boogie Preprocessor took 29.64 ms. Allocated memory is still 400.0 MB. Free memory was 346.1 MB in the beginning and 344.8 MB in the end (delta: 1.3 MB). Peak memory consumption was 1.3 MB. Max. memory is 5.3 GB. * RCFGBuilder took 215.94 ms. Allocated memory is still 400.0 MB. Free memory was 344.8 MB in the beginning and 322.2 MB in the end (delta: 22.5 MB). Peak memory consumption was 22.5 MB. Max. memory is 5.3 GB. * TraceAbstraction took 103426.96 ms. Allocated memory was 400.0 MB in the beginning and 705.2 MB in the end (delta: 305.1 MB). Free memory was 322.2 MB in the beginning and 647.8 MB in the end (delta: -325.5 MB). There was no memory consumed. Max. memory is 5.3 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 570). Cancelled while BasicCegarLoop was constructing difference of abstraction (70states) and interpolant automaton (currently 11 states, 33 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 58. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 569). Cancelled while BasicCegarLoop was constructing difference of abstraction (70states) and interpolant automaton (currently 11 states, 33 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 58. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 570). Cancelled while BasicCegarLoop was constructing difference of abstraction (70states) and interpolant automaton (currently 11 states, 33 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 58. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 569). Cancelled while BasicCegarLoop was constructing difference of abstraction (70states) and interpolant automaton (currently 11 states, 33 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 58. - TimeoutResultAtElement [Line: 553]: Timeout (TraceAbstraction) Unable to prove that all allocated memory was freed (line 553). Cancelled while BasicCegarLoop was constructing difference of abstraction (70states) and interpolant automaton (currently 11 states, 33 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 58. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 549). Cancelled while BasicCegarLoop was constructing difference of abstraction (70states) and interpolant automaton (currently 11 states, 33 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 58. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 545). Cancelled while BasicCegarLoop was constructing difference of abstraction (70states) and interpolant automaton (currently 11 states, 33 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 58. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 543). Cancelled while BasicCegarLoop was constructing difference of abstraction (70states) and interpolant automaton (currently 11 states, 33 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 58. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 545). Cancelled while BasicCegarLoop was constructing difference of abstraction (70states) and interpolant automaton (currently 11 states, 33 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 58. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 550). Cancelled while BasicCegarLoop was constructing difference of abstraction (70states) and interpolant automaton (currently 11 states, 33 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 58. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 543). Cancelled while BasicCegarLoop was constructing difference of abstraction (70states) and interpolant automaton (currently 11 states, 33 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 58. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 545). Cancelled while BasicCegarLoop was constructing difference of abstraction (70states) and interpolant automaton (currently 11 states, 33 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 58. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 550). Cancelled while BasicCegarLoop was constructing difference of abstraction (70states) and interpolant automaton (currently 11 states, 33 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 58. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 549). Cancelled while BasicCegarLoop was constructing difference of abstraction (70states) and interpolant automaton (currently 11 states, 33 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 58. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 545). Cancelled while BasicCegarLoop was constructing difference of abstraction (70states) and interpolant automaton (currently 11 states, 33 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 58. - StatisticsResult: Ultimate Automizer benchmark data CFG has 4 procedures, 58 locations, 15 error locations. TIMEOUT Result, 103.3s OverallTime, 20 OverallIterations, 3 TraceHistogramMax, 93.8s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 857 SDtfs, 1809 SDslu, 4824 SDs, 0 SdLazy, 4954 SolverSat, 433 SolverUnsat, 9 SolverUnknown, 0 SolverNotchecked, 29.3s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 583 GetRequests, 195 SyntacticMatches, 6 SemanticMatches, 381 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3066 ImplicationChecksByTransitivity, 69.1s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=130occurred in iteration=14, 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, 19 MinimizatonAttempts, 282 StatesRemovedByMinimization, 11 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.2s SatisfiabilityAnalysisTime, 8.7s InterpolantComputationTime, 791 NumberOfCodeBlocks, 791 NumberOfCodeBlocksAsserted, 30 NumberOfCheckSat, 763 ConstructedInterpolants, 58 QuantifiedInterpolants, 279763 SizeOfPredicates, 97 NumberOfNonLiveVariables, 1264 ConjunctsInSsa, 316 ConjunctsInUnsatCore, 28 InterpolantComputations, 12 PerfectInterpolantSequences, 6/144 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/cstrncat-alloca_true-valid-memsafety_true-termination.i_svcomp-DerefFreeMemtrack-32bit-Automizer_Camel.epf_AutomizerC.xml/Csv-Benchmark-0-2018-02-02_18-24-30-359.csv Written .csv to /home/ultimate/work/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/cstrncat-alloca_true-valid-memsafety_true-termination.i_svcomp-DerefFreeMemtrack-32bit-Automizer_Camel.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-0-2018-02-02_18-24-30-359.csv Completed graceful shutdown