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/openbsd_cstrncat-alloca_true-valid-memsafety_true-termination.i -------------------------------------------------------------------------------- This is Ultimate 0.1.23-a74eeac-m [2018-02-02 18:26:37,880 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-02-02 18:26:37,882 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-02-02 18:26:37,894 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-02-02 18:26:37,894 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-02-02 18:26:37,895 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-02-02 18:26:37,896 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-02-02 18:26:37,897 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-02-02 18:26:37,899 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-02-02 18:26:37,900 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-02-02 18:26:37,900 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-02-02 18:26:37,901 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-02-02 18:26:37,901 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-02-02 18:26:37,902 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-02-02 18:26:37,903 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-02-02 18:26:37,905 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-02-02 18:26:37,906 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-02-02 18:26:37,908 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-02-02 18:26:37,909 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-02-02 18:26:37,910 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-02-02 18:26:37,911 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-02-02 18:26:37,912 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-02-02 18:26:37,912 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-02-02 18:26:37,913 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-02-02 18:26:37,913 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-02-02 18:26:37,914 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-02-02 18:26:37,915 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-02-02 18:26:37,915 INFO L177 SettingsManager]: PEA to Boogie provides no preferences, ignoring... [2018-02-02 18:26:37,915 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-02-02 18:26:37,915 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-02-02 18:26:37,916 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-02-02 18:26:37,916 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:26:37,925 INFO L110 SettingsManager]: Loading preferences was successful [2018-02-02 18:26:37,925 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-02-02 18:26:37,926 INFO L131 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2018-02-02 18:26:37,926 INFO L133 SettingsManager]: * Create parallel compositions if possible=false [2018-02-02 18:26:37,926 INFO L133 SettingsManager]: * Use SBE=true [2018-02-02 18:26:37,927 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-02-02 18:26:37,927 INFO L133 SettingsManager]: * sizeof long=4 [2018-02-02 18:26:37,927 INFO L133 SettingsManager]: * Check unreachability of error function in SV-COMP mode=false [2018-02-02 18:26:37,927 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-02-02 18:26:37,927 INFO L133 SettingsManager]: * sizeof POINTER=4 [2018-02-02 18:26:37,928 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-02-02 18:26:37,928 INFO L133 SettingsManager]: * Check for the main procedure if all allocated memory was freed=true [2018-02-02 18:26:37,928 INFO L133 SettingsManager]: * Bitprecise bitfields=true [2018-02-02 18:26:37,928 INFO L133 SettingsManager]: * SV-COMP memtrack compatibility mode=true [2018-02-02 18:26:37,928 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-02-02 18:26:37,928 INFO L133 SettingsManager]: * sizeof long double=12 [2018-02-02 18:26:37,928 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-02-02 18:26:37,929 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-02-02 18:26:37,929 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-02-02 18:26:37,929 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-02-02 18:26:37,929 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-02-02 18:26:37,929 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-02-02 18:26:37,929 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-02-02 18:26:37,929 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-02-02 18:26:37,930 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-02-02 18:26:37,959 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-02-02 18:26:37,969 INFO L266 ainManager$Toolchain]: [Toolchain 1]: Parser(s) successfully initialized [2018-02-02 18:26:37,972 INFO L222 ainManager$Toolchain]: [Toolchain 1]: Toolchain data selected. [2018-02-02 18:26:37,973 INFO L271 PluginConnector]: Initializing CDTParser... [2018-02-02 18:26:37,974 INFO L276 PluginConnector]: CDTParser initialized [2018-02-02 18:26:37,974 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /home/ultimate/work/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/array-memsafety/openbsd_cstrncat-alloca_true-valid-memsafety_true-termination.i [2018-02-02 18:26:38,109 INFO L304 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-02-02 18:26:38,110 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2018-02-02 18:26:38,110 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2018-02-02 18:26:38,110 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2018-02-02 18:26:38,115 INFO L276 PluginConnector]: CACSL2BoogieTranslator initialized [2018-02-02 18:26:38,115 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 02.02 06:26:38" (1/1) ... [2018-02-02 18:26:38,117 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@309783a9 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.02 06:26:38, skipping insertion in model container [2018-02-02 18:26:38,117 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 02.02 06:26:38" (1/1) ... [2018-02-02 18:26:38,128 INFO L153 Dispatcher]: Using SV-COMP mode [2018-02-02 18:26:38,159 INFO L153 Dispatcher]: Using SV-COMP mode [2018-02-02 18:26:38,244 INFO L450 PostProcessor]: Settings: Checked method=main [2018-02-02 18:26:38,257 INFO L450 PostProcessor]: Settings: Checked method=main [2018-02-02 18:26:38,261 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.02 06:26:38 WrapperNode [2018-02-02 18:26:38,262 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2018-02-02 18:26:38,262 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-02-02 18:26:38,262 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-02-02 18:26:38,262 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-02-02 18:26:38,275 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.02 06:26:38" (1/1) ... [2018-02-02 18:26:38,275 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.02 06:26:38" (1/1) ... [2018-02-02 18:26:38,281 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.02 06:26:38" (1/1) ... [2018-02-02 18:26:38,281 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.02 06:26:38" (1/1) ... [2018-02-02 18:26:38,284 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.02 06:26:38" (1/1) ... [2018-02-02 18:26:38,286 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.02 06:26:38" (1/1) ... [2018-02-02 18:26:38,287 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.02 06:26:38" (1/1) ... [2018-02-02 18:26:38,289 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-02-02 18:26:38,289 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-02-02 18:26:38,289 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-02-02 18:26:38,289 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-02-02 18:26:38,290 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.02 06:26:38" (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:26:38,325 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2018-02-02 18:26:38,325 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-02-02 18:26:38,325 INFO L136 BoogieDeclarations]: Found implementation of procedure cstrncat [2018-02-02 18:26:38,326 INFO L136 BoogieDeclarations]: Found implementation of procedure main [2018-02-02 18:26:38,326 INFO L128 BoogieDeclarations]: Found specification of procedure write~int [2018-02-02 18:26:38,326 INFO L128 BoogieDeclarations]: Found specification of procedure read~int [2018-02-02 18:26:38,326 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.free [2018-02-02 18:26:38,326 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2018-02-02 18:26:38,326 INFO L128 BoogieDeclarations]: Found specification of procedure #Ultimate.alloc [2018-02-02 18:26:38,326 INFO L128 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2018-02-02 18:26:38,326 INFO L128 BoogieDeclarations]: Found specification of procedure cstrncat [2018-02-02 18:26:38,327 INFO L128 BoogieDeclarations]: Found specification of procedure main [2018-02-02 18:26:38,327 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2018-02-02 18:26:38,327 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-02-02 18:26:38,508 INFO L257 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-02-02 18:26:38,509 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 02.02 06:26:38 BoogieIcfgContainer [2018-02-02 18:26:38,509 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-02-02 18:26:38,509 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-02-02 18:26:38,509 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-02-02 18:26:38,511 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-02-02 18:26:38,511 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 02.02 06:26:38" (1/3) ... [2018-02-02 18:26:38,512 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5e957d18 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 02.02 06:26:38, skipping insertion in model container [2018-02-02 18:26:38,512 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.02 06:26:38" (2/3) ... [2018-02-02 18:26:38,512 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5e957d18 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 02.02 06:26:38, skipping insertion in model container [2018-02-02 18:26:38,512 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 02.02 06:26:38" (3/3) ... [2018-02-02 18:26:38,513 INFO L107 eAbstractionObserver]: Analyzing ICFG openbsd_cstrncat-alloca_true-valid-memsafety_true-termination.i [2018-02-02 18:26:38,520 INFO L128 ceAbstractionStarter]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-02-02 18:26:38,528 INFO L140 ceAbstractionStarter]: Appying trace abstraction to program that has 13 error locations. [2018-02-02 18:26:38,556 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-02-02 18:26:38,556 INFO L323 AbstractCegarLoop]: Hoare is false [2018-02-02 18:26:38,556 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-02-02 18:26:38,556 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-02-02 18:26:38,556 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-02-02 18:26:38,556 INFO L327 AbstractCegarLoop]: Difference is false [2018-02-02 18:26:38,556 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-02-02 18:26:38,557 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-02-02 18:26:38,557 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-02-02 18:26:38,567 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states. [2018-02-02 18:26:38,574 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2018-02-02 18:26:38,575 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 18:26:38,575 INFO L351 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-02-02 18:26:38,575 INFO L371 AbstractCegarLoop]: === Iteration 1 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 18:26:38,578 INFO L82 PathProgramCache]: Analyzing trace with hash 2055638365, now seen corresponding path program 1 times [2018-02-02 18:26:38,579 INFO L213 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 18:26:38,580 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 18:26:38,610 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:26:38,610 INFO L109 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 18:26:38,610 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:26:38,645 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:26:38,649 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 18:26:38,684 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:26:38,686 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-02-02 18:26:38,686 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-02-02 18:26:38,687 INFO L409 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-02-02 18:26:38,698 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-02-02 18:26:38,698 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-02-02 18:26:38,700 INFO L87 Difference]: Start difference. First operand 54 states. Second operand 3 states. [2018-02-02 18:26:38,887 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 18:26:38,887 INFO L93 Difference]: Finished difference Result 55 states and 62 transitions. [2018-02-02 18:26:38,887 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-02-02 18:26:38,889 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 11 [2018-02-02 18:26:38,889 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 18:26:38,897 INFO L225 Difference]: With dead ends: 55 [2018-02-02 18:26:38,897 INFO L226 Difference]: Without dead ends: 51 [2018-02-02 18:26:38,899 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:26:38,913 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2018-02-02 18:26:38,928 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 51. [2018-02-02 18:26:38,929 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 51 states. [2018-02-02 18:26:38,930 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 57 transitions. [2018-02-02 18:26:38,931 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 57 transitions. Word has length 11 [2018-02-02 18:26:38,931 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 18:26:38,931 INFO L432 AbstractCegarLoop]: Abstraction has 51 states and 57 transitions. [2018-02-02 18:26:38,931 INFO L433 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-02-02 18:26:38,931 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 57 transitions. [2018-02-02 18:26:38,932 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2018-02-02 18:26:38,932 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 18:26:38,932 INFO L351 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-02-02 18:26:38,932 INFO L371 AbstractCegarLoop]: === Iteration 2 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 18:26:38,932 INFO L82 PathProgramCache]: Analyzing trace with hash -1872133330, now seen corresponding path program 1 times [2018-02-02 18:26:38,932 INFO L213 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 18:26:38,932 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 18:26:38,933 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:26:38,933 INFO L109 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 18:26:38,933 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:26:38,942 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:26:38,942 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 18:26:38,998 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:26:38,999 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-02-02 18:26:38,999 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-02-02 18:26:39,000 INFO L409 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-02-02 18:26:39,000 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-02-02 18:26:39,000 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-02-02 18:26:39,001 INFO L87 Difference]: Start difference. First operand 51 states and 57 transitions. Second operand 5 states. [2018-02-02 18:26:39,047 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 18:26:39,047 INFO L93 Difference]: Finished difference Result 54 states and 61 transitions. [2018-02-02 18:26:39,047 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-02-02 18:26:39,048 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 15 [2018-02-02 18:26:39,048 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 18:26:39,048 INFO L225 Difference]: With dead ends: 54 [2018-02-02 18:26:39,048 INFO L226 Difference]: Without dead ends: 51 [2018-02-02 18:26:39,055 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:26:39,055 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2018-02-02 18:26:39,058 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 51. [2018-02-02 18:26:39,058 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 51 states. [2018-02-02 18:26:39,059 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 56 transitions. [2018-02-02 18:26:39,059 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 56 transitions. Word has length 15 [2018-02-02 18:26:39,059 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 18:26:39,059 INFO L432 AbstractCegarLoop]: Abstraction has 51 states and 56 transitions. [2018-02-02 18:26:39,059 INFO L433 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-02-02 18:26:39,059 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 56 transitions. [2018-02-02 18:26:39,060 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2018-02-02 18:26:39,060 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 18:26:39,060 INFO L351 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-02-02 18:26:39,060 INFO L371 AbstractCegarLoop]: === Iteration 3 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 18:26:39,060 INFO L82 PathProgramCache]: Analyzing trace with hash -1192074960, now seen corresponding path program 1 times [2018-02-02 18:26:39,060 INFO L213 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 18:26:39,060 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 18:26:39,061 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:26:39,061 INFO L109 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 18:26:39,061 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:26:39,102 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:26:39,103 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 18:26:39,148 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:26:39,149 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-02-02 18:26:39,149 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-02-02 18:26:39,149 INFO L409 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-02-02 18:26:39,149 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-02-02 18:26:39,149 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-02-02 18:26:39,149 INFO L87 Difference]: Start difference. First operand 51 states and 56 transitions. Second operand 4 states. [2018-02-02 18:26:39,183 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 18:26:39,183 INFO L93 Difference]: Finished difference Result 50 states and 55 transitions. [2018-02-02 18:26:39,183 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-02-02 18:26:39,183 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 15 [2018-02-02 18:26:39,183 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 18:26:39,185 INFO L225 Difference]: With dead ends: 50 [2018-02-02 18:26:39,185 INFO L226 Difference]: Without dead ends: 50 [2018-02-02 18:26:39,185 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:26:39,186 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 50 states. [2018-02-02 18:26:39,187 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 50 to 50. [2018-02-02 18:26:39,188 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 50 states. [2018-02-02 18:26:39,188 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 50 states to 50 states and 55 transitions. [2018-02-02 18:26:39,188 INFO L78 Accepts]: Start accepts. Automaton has 50 states and 55 transitions. Word has length 15 [2018-02-02 18:26:39,188 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 18:26:39,188 INFO L432 AbstractCegarLoop]: Abstraction has 50 states and 55 transitions. [2018-02-02 18:26:39,189 INFO L433 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-02-02 18:26:39,189 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 55 transitions. [2018-02-02 18:26:39,189 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2018-02-02 18:26:39,189 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 18:26:39,189 INFO L351 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-02-02 18:26:39,189 INFO L371 AbstractCegarLoop]: === Iteration 4 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 18:26:39,189 INFO L82 PathProgramCache]: Analyzing trace with hash -1192074959, now seen corresponding path program 1 times [2018-02-02 18:26:39,189 INFO L213 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 18:26:39,189 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 18:26:39,190 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:26:39,190 INFO L109 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 18:26:39,190 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:26:39,197 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:26:39,198 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 18:26:39,273 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:26:39,273 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-02-02 18:26:39,273 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2018-02-02 18:26:39,274 INFO L409 AbstractCegarLoop]: Interpolant automaton has 8 states [2018-02-02 18:26:39,274 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2018-02-02 18:26:39,274 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=38, Unknown=0, NotChecked=0, Total=56 [2018-02-02 18:26:39,274 INFO L87 Difference]: Start difference. First operand 50 states and 55 transitions. Second operand 8 states. [2018-02-02 18:26:39,419 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 18:26:39,420 INFO L93 Difference]: Finished difference Result 49 states and 54 transitions. [2018-02-02 18:26:39,420 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-02-02 18:26:39,420 INFO L78 Accepts]: Start accepts. Automaton has 8 states. Word has length 15 [2018-02-02 18:26:39,421 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 18:26:39,421 INFO L225 Difference]: With dead ends: 49 [2018-02-02 18:26:39,421 INFO L226 Difference]: Without dead ends: 49 [2018-02-02 18:26:39,422 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=48, Invalid=84, Unknown=0, NotChecked=0, Total=132 [2018-02-02 18:26:39,422 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 49 states. [2018-02-02 18:26:39,427 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 49 to 49. [2018-02-02 18:26:39,427 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 49 states. [2018-02-02 18:26:39,428 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 49 states to 49 states and 54 transitions. [2018-02-02 18:26:39,428 INFO L78 Accepts]: Start accepts. Automaton has 49 states and 54 transitions. Word has length 15 [2018-02-02 18:26:39,428 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 18:26:39,428 INFO L432 AbstractCegarLoop]: Abstraction has 49 states and 54 transitions. [2018-02-02 18:26:39,428 INFO L433 AbstractCegarLoop]: Interpolant automaton has 8 states. [2018-02-02 18:26:39,428 INFO L276 IsEmpty]: Start isEmpty. Operand 49 states and 54 transitions. [2018-02-02 18:26:39,429 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2018-02-02 18:26:39,429 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 18:26:39,429 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:26:39,429 INFO L371 AbstractCegarLoop]: === Iteration 5 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 18:26:39,429 INFO L82 PathProgramCache]: Analyzing trace with hash 1700381909, now seen corresponding path program 1 times [2018-02-02 18:26:39,429 INFO L213 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 18:26:39,429 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 18:26:39,430 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:26:39,430 INFO L109 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 18:26:39,430 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:26:39,443 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:26:39,444 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 18:26:39,471 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:26:39,471 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-02-02 18:26:39,471 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-02-02 18:26:39,472 INFO L409 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-02-02 18:26:39,472 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-02-02 18:26:39,472 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-02-02 18:26:39,472 INFO L87 Difference]: Start difference. First operand 49 states and 54 transitions. Second operand 4 states. [2018-02-02 18:26:39,498 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 18:26:39,499 INFO L93 Difference]: Finished difference Result 48 states and 53 transitions. [2018-02-02 18:26:39,499 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-02-02 18:26:39,499 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 16 [2018-02-02 18:26:39,499 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 18:26:39,500 INFO L225 Difference]: With dead ends: 48 [2018-02-02 18:26:39,500 INFO L226 Difference]: Without dead ends: 48 [2018-02-02 18:26:39,500 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:26:39,500 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states. [2018-02-02 18:26:39,505 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 48. [2018-02-02 18:26:39,505 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 48 states. [2018-02-02 18:26:39,506 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 53 transitions. [2018-02-02 18:26:39,506 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 53 transitions. Word has length 16 [2018-02-02 18:26:39,506 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 18:26:39,506 INFO L432 AbstractCegarLoop]: Abstraction has 48 states and 53 transitions. [2018-02-02 18:26:39,506 INFO L433 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-02-02 18:26:39,506 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 53 transitions. [2018-02-02 18:26:39,507 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2018-02-02 18:26:39,507 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 18:26:39,507 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:26:39,507 INFO L371 AbstractCegarLoop]: === Iteration 6 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 18:26:39,507 INFO L82 PathProgramCache]: Analyzing trace with hash 1700381910, now seen corresponding path program 1 times [2018-02-02 18:26:39,507 INFO L213 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 18:26:39,507 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 18:26:39,508 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:26:39,508 INFO L109 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 18:26:39,508 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:26:39,517 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:26:39,518 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 18:26:39,576 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:26:39,592 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-02-02 18:26:39,593 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-02-02 18:26:39,593 INFO L409 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-02-02 18:26:39,593 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-02-02 18:26:39,593 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-02-02 18:26:39,593 INFO L87 Difference]: Start difference. First operand 48 states and 53 transitions. Second operand 5 states. [2018-02-02 18:26:39,615 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 18:26:39,615 INFO L93 Difference]: Finished difference Result 47 states and 52 transitions. [2018-02-02 18:26:39,616 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-02-02 18:26:39,616 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 16 [2018-02-02 18:26:39,616 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 18:26:39,616 INFO L225 Difference]: With dead ends: 47 [2018-02-02 18:26:39,616 INFO L226 Difference]: Without dead ends: 47 [2018-02-02 18:26:39,616 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:26:39,617 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2018-02-02 18:26:39,618 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 47. [2018-02-02 18:26:39,618 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 47 states. [2018-02-02 18:26:39,619 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 47 states to 47 states and 52 transitions. [2018-02-02 18:26:39,619 INFO L78 Accepts]: Start accepts. Automaton has 47 states and 52 transitions. Word has length 16 [2018-02-02 18:26:39,619 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 18:26:39,619 INFO L432 AbstractCegarLoop]: Abstraction has 47 states and 52 transitions. [2018-02-02 18:26:39,619 INFO L433 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-02-02 18:26:39,619 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 52 transitions. [2018-02-02 18:26:39,619 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2018-02-02 18:26:39,619 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 18:26:39,620 INFO L351 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-02-02 18:26:39,620 INFO L371 AbstractCegarLoop]: === Iteration 7 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 18:26:39,620 INFO L82 PathProgramCache]: Analyzing trace with hash -275307336, now seen corresponding path program 1 times [2018-02-02 18:26:39,620 INFO L213 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 18:26:39,620 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 18:26:39,620 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:26:39,621 INFO L109 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 18:26:39,621 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:26:39,632 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:26:39,633 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 18:26:39,660 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:26:39,660 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-02-02 18:26:39,660 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-02-02 18:26:39,660 INFO L409 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-02-02 18:26:39,660 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-02-02 18:26:39,661 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2018-02-02 18:26:39,661 INFO L87 Difference]: Start difference. First operand 47 states and 52 transitions. Second operand 6 states. [2018-02-02 18:26:39,715 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 18:26:39,715 INFO L93 Difference]: Finished difference Result 47 states and 52 transitions. [2018-02-02 18:26:39,715 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-02-02 18:26:39,715 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 21 [2018-02-02 18:26:39,715 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 18:26:39,717 INFO L225 Difference]: With dead ends: 47 [2018-02-02 18:26:39,717 INFO L226 Difference]: Without dead ends: 47 [2018-02-02 18:26:39,717 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:26:39,717 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2018-02-02 18:26:39,719 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 44. [2018-02-02 18:26:39,719 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 44 states. [2018-02-02 18:26:39,719 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 44 states to 44 states and 49 transitions. [2018-02-02 18:26:39,719 INFO L78 Accepts]: Start accepts. Automaton has 44 states and 49 transitions. Word has length 21 [2018-02-02 18:26:39,719 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 18:26:39,719 INFO L432 AbstractCegarLoop]: Abstraction has 44 states and 49 transitions. [2018-02-02 18:26:39,719 INFO L433 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-02-02 18:26:39,720 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 49 transitions. [2018-02-02 18:26:39,720 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2018-02-02 18:26:39,720 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 18:26:39,720 INFO L351 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-02-02 18:26:39,720 INFO L371 AbstractCegarLoop]: === Iteration 8 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 18:26:39,720 INFO L82 PathProgramCache]: Analyzing trace with hash -275307335, now seen corresponding path program 1 times [2018-02-02 18:26:39,720 INFO L213 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 18:26:39,720 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 18:26:39,721 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:26:39,721 INFO L109 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 18:26:39,721 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:26:39,730 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:26:39,731 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 18:26:39,886 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:26:39,886 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-02-02 18:26:39,886 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2018-02-02 18:26:39,886 INFO L409 AbstractCegarLoop]: Interpolant automaton has 10 states [2018-02-02 18:26:39,886 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2018-02-02 18:26:39,887 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=71, Unknown=0, NotChecked=0, Total=90 [2018-02-02 18:26:39,887 INFO L87 Difference]: Start difference. First operand 44 states and 49 transitions. Second operand 10 states. [2018-02-02 18:26:40,015 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 18:26:40,015 INFO L93 Difference]: Finished difference Result 57 states and 64 transitions. [2018-02-02 18:26:40,015 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-02-02 18:26:40,016 INFO L78 Accepts]: Start accepts. Automaton has 10 states. Word has length 21 [2018-02-02 18:26:40,016 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 18:26:40,016 INFO L225 Difference]: With dead ends: 57 [2018-02-02 18:26:40,016 INFO L226 Difference]: Without dead ends: 57 [2018-02-02 18:26:40,016 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 16 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 25 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=65, Invalid=207, Unknown=0, NotChecked=0, Total=272 [2018-02-02 18:26:40,016 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 57 states. [2018-02-02 18:26:40,018 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 57 to 52. [2018-02-02 18:26:40,018 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 52 states. [2018-02-02 18:26:40,018 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 52 states to 52 states and 61 transitions. [2018-02-02 18:26:40,018 INFO L78 Accepts]: Start accepts. Automaton has 52 states and 61 transitions. Word has length 21 [2018-02-02 18:26:40,018 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 18:26:40,019 INFO L432 AbstractCegarLoop]: Abstraction has 52 states and 61 transitions. [2018-02-02 18:26:40,019 INFO L433 AbstractCegarLoop]: Interpolant automaton has 10 states. [2018-02-02 18:26:40,019 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 61 transitions. [2018-02-02 18:26:40,019 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2018-02-02 18:26:40,019 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 18:26:40,019 INFO L351 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-02-02 18:26:40,019 INFO L371 AbstractCegarLoop]: === Iteration 9 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 18:26:40,019 INFO L82 PathProgramCache]: Analyzing trace with hash 1706718631, now seen corresponding path program 1 times [2018-02-02 18:26:40,019 INFO L213 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 18:26:40,019 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 18:26:40,020 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:26:40,020 INFO L109 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 18:26:40,020 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:26:40,028 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:26:40,029 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 18:26:40,070 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:26:40,071 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-02-02 18:26:40,071 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2018-02-02 18:26:40,071 INFO L409 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-02-02 18:26:40,071 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-02-02 18:26:40,071 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2018-02-02 18:26:40,072 INFO L87 Difference]: Start difference. First operand 52 states and 61 transitions. Second operand 7 states. [2018-02-02 18:26:40,137 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 18:26:40,137 INFO L93 Difference]: Finished difference Result 54 states and 62 transitions. [2018-02-02 18:26:40,137 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-02-02 18:26:40,137 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 24 [2018-02-02 18:26:40,137 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 18:26:40,138 INFO L225 Difference]: With dead ends: 54 [2018-02-02 18:26:40,138 INFO L226 Difference]: Without dead ends: 54 [2018-02-02 18:26:40,138 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 9 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=29, Invalid=61, Unknown=0, NotChecked=0, Total=90 [2018-02-02 18:26:40,138 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2018-02-02 18:26:40,140 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 51. [2018-02-02 18:26:40,140 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 51 states. [2018-02-02 18:26:40,141 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 59 transitions. [2018-02-02 18:26:40,141 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 59 transitions. Word has length 24 [2018-02-02 18:26:40,141 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 18:26:40,141 INFO L432 AbstractCegarLoop]: Abstraction has 51 states and 59 transitions. [2018-02-02 18:26:40,142 INFO L433 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-02-02 18:26:40,142 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 59 transitions. [2018-02-02 18:26:40,142 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2018-02-02 18:26:40,142 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 18:26:40,142 INFO L351 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-02-02 18:26:40,142 INFO L371 AbstractCegarLoop]: === Iteration 10 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 18:26:40,143 INFO L82 PathProgramCache]: Analyzing trace with hash 1706718632, now seen corresponding path program 1 times [2018-02-02 18:26:40,143 INFO L213 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 18:26:40,143 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 18:26:40,143 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:26:40,143 INFO L109 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 18:26:40,143 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:26:40,152 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:26:40,152 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 18:26:40,234 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:26:40,234 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-02-02 18:26:40,234 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2018-02-02 18:26:40,234 INFO L409 AbstractCegarLoop]: Interpolant automaton has 10 states [2018-02-02 18:26:40,234 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2018-02-02 18:26:40,235 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=70, Unknown=0, NotChecked=0, Total=90 [2018-02-02 18:26:40,235 INFO L87 Difference]: Start difference. First operand 51 states and 59 transitions. Second operand 10 states. [2018-02-02 18:26:40,356 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 18:26:40,356 INFO L93 Difference]: Finished difference Result 56 states and 64 transitions. [2018-02-02 18:26:40,356 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-02-02 18:26:40,356 INFO L78 Accepts]: Start accepts. Automaton has 10 states. Word has length 24 [2018-02-02 18:26:40,356 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 18:26:40,357 INFO L225 Difference]: With dead ends: 56 [2018-02-02 18:26:40,357 INFO L226 Difference]: Without dead ends: 56 [2018-02-02 18:26:40,357 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 24 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=42, Invalid=140, Unknown=0, NotChecked=0, Total=182 [2018-02-02 18:26:40,357 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 56 states. [2018-02-02 18:26:40,359 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 56 to 53. [2018-02-02 18:26:40,359 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 53 states. [2018-02-02 18:26:40,360 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 53 states to 53 states and 60 transitions. [2018-02-02 18:26:40,360 INFO L78 Accepts]: Start accepts. Automaton has 53 states and 60 transitions. Word has length 24 [2018-02-02 18:26:40,360 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 18:26:40,360 INFO L432 AbstractCegarLoop]: Abstraction has 53 states and 60 transitions. [2018-02-02 18:26:40,360 INFO L433 AbstractCegarLoop]: Interpolant automaton has 10 states. [2018-02-02 18:26:40,360 INFO L276 IsEmpty]: Start isEmpty. Operand 53 states and 60 transitions. [2018-02-02 18:26:40,361 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2018-02-02 18:26:40,361 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 18:26:40,361 INFO L351 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-02-02 18:26:40,361 INFO L371 AbstractCegarLoop]: === Iteration 11 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 18:26:40,361 INFO L82 PathProgramCache]: Analyzing trace with hash 1706720075, now seen corresponding path program 1 times [2018-02-02 18:26:40,361 INFO L213 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 18:26:40,362 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 18:26:40,362 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:26:40,362 INFO L109 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 18:26:40,363 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:26:40,372 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:26:40,373 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 18:26:40,501 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:26:40,501 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-02-02 18:26:40,501 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:26:40,507 INFO L109 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 18:26:40,528 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:26:40,536 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-02-02 18:26:40,600 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:26:40,601 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-02-02 18:26:40,607 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:26:40,607 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 18:26:40,612 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:26:40,612 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:24, output treesize:19 [2018-02-02 18:26:40,650 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:26:40,651 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:26:40,653 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:26:40,654 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-02-02 18:26:40,664 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:26:40,664 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:26:40,665 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:26:40,665 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 18:26:40,670 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:26:40,671 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:30, output treesize:18 [2018-02-02 18:26:40,824 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:26:40,851 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-02-02 18:26:40,851 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 13] total 23 [2018-02-02 18:26:40,851 INFO L409 AbstractCegarLoop]: Interpolant automaton has 24 states [2018-02-02 18:26:40,852 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2018-02-02 18:26:40,852 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=61, Invalid=491, Unknown=0, NotChecked=0, Total=552 [2018-02-02 18:26:40,852 INFO L87 Difference]: Start difference. First operand 53 states and 60 transitions. Second operand 24 states. [2018-02-02 18:26:41,404 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 18:26:41,405 INFO L93 Difference]: Finished difference Result 72 states and 82 transitions. [2018-02-02 18:26:41,405 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-02-02 18:26:41,405 INFO L78 Accepts]: Start accepts. Automaton has 24 states. Word has length 24 [2018-02-02 18:26:41,405 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 18:26:41,405 INFO L225 Difference]: With dead ends: 72 [2018-02-02 18:26:41,406 INFO L226 Difference]: Without dead ends: 72 [2018-02-02 18:26:41,406 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 45 GetRequests, 13 SyntacticMatches, 0 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 192 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=169, Invalid=953, Unknown=0, NotChecked=0, Total=1122 [2018-02-02 18:26:41,406 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 72 states. [2018-02-02 18:26:41,408 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 72 to 64. [2018-02-02 18:26:41,408 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 64 states. [2018-02-02 18:26:41,408 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 64 states to 64 states and 75 transitions. [2018-02-02 18:26:41,409 INFO L78 Accepts]: Start accepts. Automaton has 64 states and 75 transitions. Word has length 24 [2018-02-02 18:26:41,409 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 18:26:41,412 INFO L432 AbstractCegarLoop]: Abstraction has 64 states and 75 transitions. [2018-02-02 18:26:41,412 INFO L433 AbstractCegarLoop]: Interpolant automaton has 24 states. [2018-02-02 18:26:41,412 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 75 transitions. [2018-02-02 18:26:41,413 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2018-02-02 18:26:41,413 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 18:26:41,413 INFO L351 BasicCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-02-02 18:26:41,413 INFO L371 AbstractCegarLoop]: === Iteration 12 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 18:26:41,413 INFO L82 PathProgramCache]: Analyzing trace with hash 1074905977, now seen corresponding path program 2 times [2018-02-02 18:26:41,413 INFO L213 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 18:26:41,413 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 18:26:41,414 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:26:41,414 INFO L109 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 18:26:41,414 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:26:41,427 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:26:41,427 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 18:26:41,642 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:26:41,642 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-02-02 18:26:41,642 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:26:41,648 INFO L109 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-02-02 18:26:41,663 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-02-02 18:26:41,663 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-02-02 18:26:41,665 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-02-02 18:26:41,696 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-02-02 18:26:41,696 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-02-02 18:26:41,701 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 18:26:41,701 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:18, output treesize:17 [2018-02-02 18:26:41,741 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:26:41,742 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:26:41,742 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:26:41,743 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-02-02 18:26:41,747 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 18:26:41,747 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:22, output treesize:16 [2018-02-02 18:26:41,781 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:26:41,782 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:26:41,782 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 18:26:41,784 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 18:26:41,790 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:26:41,790 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:42, output treesize:38 [2018-02-02 18:26:41,819 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:26:41,822 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:26:41,822 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 18:26:41,826 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 18:26:41,834 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:26:41,834 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 6 variables, input treesize:52, output treesize:48 [2018-02-02 18:26:42,186 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:26:42,190 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:26:42,195 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:26:42,196 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-02-02 18:26:42,237 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:26:42,237 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-02-02 18:26:42,243 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-02-02 18:26:42,257 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:26:42,257 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 6 variables, input treesize:66, output treesize:43 [2018-02-02 18:26:42,318 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 2 proven. 5 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 18:26:42,342 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-02-02 18:26:42,343 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 16] total 27 [2018-02-02 18:26:42,343 INFO L409 AbstractCegarLoop]: Interpolant automaton has 28 states [2018-02-02 18:26:42,343 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2018-02-02 18:26:42,343 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=68, Invalid=688, Unknown=0, NotChecked=0, Total=756 [2018-02-02 18:26:42,343 INFO L87 Difference]: Start difference. First operand 64 states and 75 transitions. Second operand 28 states. [2018-02-02 18:26:42,991 WARN L146 SmtUtils]: Spent 129ms on a formula simplification. DAG size of input: 80 DAG size of output 77 [2018-02-02 18:26:49,891 WARN L146 SmtUtils]: Spent 160ms on a formula simplification. DAG size of input: 69 DAG size of output 67 [2018-02-02 18:27:02,337 WARN L146 SmtUtils]: Spent 8088ms on a formula simplification. DAG size of input: 83 DAG size of output 81 [2018-02-02 18:27:13,742 WARN L146 SmtUtils]: Spent 8100ms on a formula simplification. DAG size of input: 90 DAG size of output 79 [2018-02-02 18:27:22,520 WARN L146 SmtUtils]: Spent 2052ms on a formula simplification. DAG size of input: 79 DAG size of output 62 [2018-02-02 18:27:24,933 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 18:27:24,933 INFO L93 Difference]: Finished difference Result 109 states and 124 transitions. [2018-02-02 18:27:24,933 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 31 states. [2018-02-02 18:27:24,933 INFO L78 Accepts]: Start accepts. Automaton has 28 states. Word has length 27 [2018-02-02 18:27:24,933 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 18:27:24,934 INFO L225 Difference]: With dead ends: 109 [2018-02-02 18:27:24,934 INFO L226 Difference]: Without dead ends: 109 [2018-02-02 18:27:24,935 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 69 GetRequests, 14 SyntacticMatches, 1 SemanticMatches, 54 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 598 ImplicationChecksByTransitivity, 25.1s TimeCoverageRelationStatistics Valid=408, Invalid=2670, Unknown=2, NotChecked=0, Total=3080 [2018-02-02 18:27:24,935 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 109 states. [2018-02-02 18:27:24,938 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 109 to 61. [2018-02-02 18:27:24,938 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 61 states. [2018-02-02 18:27:24,939 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 61 states to 61 states and 72 transitions. [2018-02-02 18:27:24,939 INFO L78 Accepts]: Start accepts. Automaton has 61 states and 72 transitions. Word has length 27 [2018-02-02 18:27:24,939 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 18:27:24,939 INFO L432 AbstractCegarLoop]: Abstraction has 61 states and 72 transitions. [2018-02-02 18:27:24,939 INFO L433 AbstractCegarLoop]: Interpolant automaton has 28 states. [2018-02-02 18:27:24,939 INFO L276 IsEmpty]: Start isEmpty. Operand 61 states and 72 transitions. [2018-02-02 18:27:24,940 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2018-02-02 18:27:24,940 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 18:27:24,940 INFO L351 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-02-02 18:27:24,940 INFO L371 AbstractCegarLoop]: === Iteration 13 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 18:27:24,940 INFO L82 PathProgramCache]: Analyzing trace with hash 94248296, now seen corresponding path program 1 times [2018-02-02 18:27:24,940 INFO L213 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 18:27:24,940 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 18:27:24,941 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:27:24,941 INFO L107 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-02-02 18:27:24,941 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:27:24,948 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:27:24,948 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 18:27:24,995 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:27:24,995 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-02-02 18:27:24,995 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-02-02 18:27:24,995 INFO L409 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-02-02 18:27:24,996 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-02-02 18:27:24,996 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-02-02 18:27:24,996 INFO L87 Difference]: Start difference. First operand 61 states and 72 transitions. Second operand 5 states. [2018-02-02 18:27:25,037 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 18:27:25,037 INFO L93 Difference]: Finished difference Result 86 states and 99 transitions. [2018-02-02 18:27:25,038 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-02-02 18:27:25,038 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 28 [2018-02-02 18:27:25,038 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 18:27:25,039 INFO L225 Difference]: With dead ends: 86 [2018-02-02 18:27:25,040 INFO L226 Difference]: Without dead ends: 86 [2018-02-02 18:27:25,040 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2018-02-02 18:27:25,040 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 86 states. [2018-02-02 18:27:25,046 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 86 to 72. [2018-02-02 18:27:25,047 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 72 states. [2018-02-02 18:27:25,047 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 72 states to 72 states and 84 transitions. [2018-02-02 18:27:25,048 INFO L78 Accepts]: Start accepts. Automaton has 72 states and 84 transitions. Word has length 28 [2018-02-02 18:27:25,048 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 18:27:25,048 INFO L432 AbstractCegarLoop]: Abstraction has 72 states and 84 transitions. [2018-02-02 18:27:25,048 INFO L433 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-02-02 18:27:25,048 INFO L276 IsEmpty]: Start isEmpty. Operand 72 states and 84 transitions. [2018-02-02 18:27:25,049 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2018-02-02 18:27:25,049 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 18:27:25,049 INFO L351 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-02-02 18:27:25,065 INFO L371 AbstractCegarLoop]: === Iteration 14 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 18:27:25,066 INFO L82 PathProgramCache]: Analyzing trace with hash -723400154, now seen corresponding path program 1 times [2018-02-02 18:27:25,066 INFO L213 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 18:27:25,067 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 18:27:25,067 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:27:25,067 INFO L109 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 18:27:25,067 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:27:25,076 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:27:25,077 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 18:27:25,130 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:27:25,131 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-02-02 18:27:25,131 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-02-02 18:27:25,131 INFO L409 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-02-02 18:27:25,131 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-02-02 18:27:25,131 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2018-02-02 18:27:25,131 INFO L87 Difference]: Start difference. First operand 72 states and 84 transitions. Second operand 6 states. [2018-02-02 18:27:25,243 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 18:27:25,243 INFO L93 Difference]: Finished difference Result 71 states and 83 transitions. [2018-02-02 18:27:25,243 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-02-02 18:27:25,244 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 28 [2018-02-02 18:27:25,244 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 18:27:25,244 INFO L225 Difference]: With dead ends: 71 [2018-02-02 18:27:25,244 INFO L226 Difference]: Without dead ends: 58 [2018-02-02 18:27:25,244 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:27:25,244 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 58 states. [2018-02-02 18:27:25,246 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 58 to 50. [2018-02-02 18:27:25,246 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 50 states. [2018-02-02 18:27:25,246 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 50 states to 50 states and 57 transitions. [2018-02-02 18:27:25,246 INFO L78 Accepts]: Start accepts. Automaton has 50 states and 57 transitions. Word has length 28 [2018-02-02 18:27:25,246 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 18:27:25,247 INFO L432 AbstractCegarLoop]: Abstraction has 50 states and 57 transitions. [2018-02-02 18:27:25,247 INFO L433 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-02-02 18:27:25,247 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 57 transitions. [2018-02-02 18:27:25,247 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2018-02-02 18:27:25,247 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 18:27:25,247 INFO L351 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-02-02 18:27:25,247 INFO L371 AbstractCegarLoop]: === Iteration 15 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 18:27:25,248 INFO L82 PathProgramCache]: Analyzing trace with hash -1208652779, now seen corresponding path program 1 times [2018-02-02 18:27:25,248 INFO L213 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 18:27:25,248 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 18:27:25,248 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:27:25,248 INFO L109 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 18:27:25,249 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:27:25,259 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:27:25,260 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 18:27:25,347 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 18:27:25,347 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-02-02 18:27:25,347 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2018-02-02 18:27:25,347 INFO L409 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-02-02 18:27:25,348 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-02-02 18:27:25,348 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2018-02-02 18:27:25,348 INFO L87 Difference]: Start difference. First operand 50 states and 57 transitions. Second operand 7 states. [2018-02-02 18:27:25,393 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 18:27:25,393 INFO L93 Difference]: Finished difference Result 83 states and 91 transitions. [2018-02-02 18:27:25,393 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-02-02 18:27:25,393 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 30 [2018-02-02 18:27:25,393 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 18:27:25,393 INFO L225 Difference]: With dead ends: 83 [2018-02-02 18:27:25,393 INFO L226 Difference]: Without dead ends: 77 [2018-02-02 18:27:25,394 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2018-02-02 18:27:25,394 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 77 states. [2018-02-02 18:27:25,395 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 77 to 75. [2018-02-02 18:27:25,396 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 75 states. [2018-02-02 18:27:25,396 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 75 states to 75 states and 83 transitions. [2018-02-02 18:27:25,396 INFO L78 Accepts]: Start accepts. Automaton has 75 states and 83 transitions. Word has length 30 [2018-02-02 18:27:25,396 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 18:27:25,396 INFO L432 AbstractCegarLoop]: Abstraction has 75 states and 83 transitions. [2018-02-02 18:27:25,396 INFO L433 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-02-02 18:27:25,397 INFO L276 IsEmpty]: Start isEmpty. Operand 75 states and 83 transitions. [2018-02-02 18:27:25,397 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2018-02-02 18:27:25,397 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 18:27:25,397 INFO L351 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-02-02 18:27:25,397 INFO L371 AbstractCegarLoop]: === Iteration 16 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 18:27:25,398 INFO L82 PathProgramCache]: Analyzing trace with hash -989798061, now seen corresponding path program 1 times [2018-02-02 18:27:25,398 INFO L213 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 18:27:25,398 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 18:27:25,398 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:27:25,399 INFO L109 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 18:27:25,399 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:27:25,410 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:27:25,411 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 18:27:25,564 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:27:25,564 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-02-02 18:27:25,564 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:27:25,574 INFO L109 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 18:27:25,589 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:27:25,591 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-02-02 18:27:25,604 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:27:25,607 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:27:25,607 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 18:27:25,609 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 18:27:25,615 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:27:25,615 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:25, output treesize:21 [2018-02-02 18:27:25,733 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:27:25,738 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:27:25,738 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-02-02 18:27:25,741 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-02-02 18:27:25,749 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:27:25,749 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:38, output treesize:29 [2018-02-02 18:27:25,781 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:27:25,798 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-02-02 18:27:25,798 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 10] total 18 [2018-02-02 18:27:25,798 INFO L409 AbstractCegarLoop]: Interpolant automaton has 19 states [2018-02-02 18:27:25,798 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2018-02-02 18:27:25,799 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=40, Invalid=302, Unknown=0, NotChecked=0, Total=342 [2018-02-02 18:27:25,799 INFO L87 Difference]: Start difference. First operand 75 states and 83 transitions. Second operand 19 states. [2018-02-02 18:27:26,372 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 18:27:26,372 INFO L93 Difference]: Finished difference Result 86 states and 94 transitions. [2018-02-02 18:27:26,372 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-02-02 18:27:26,372 INFO L78 Accepts]: Start accepts. Automaton has 19 states. Word has length 30 [2018-02-02 18:27:26,372 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 18:27:26,373 INFO L225 Difference]: With dead ends: 86 [2018-02-02 18:27:26,373 INFO L226 Difference]: Without dead ends: 86 [2018-02-02 18:27:26,373 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 49 GetRequests, 24 SyntacticMatches, 0 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 77 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=103, Invalid=599, Unknown=0, NotChecked=0, Total=702 [2018-02-02 18:27:26,373 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 86 states. [2018-02-02 18:27:26,375 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 86 to 81. [2018-02-02 18:27:26,375 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 81 states. [2018-02-02 18:27:26,376 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 81 states to 81 states and 89 transitions. [2018-02-02 18:27:26,376 INFO L78 Accepts]: Start accepts. Automaton has 81 states and 89 transitions. Word has length 30 [2018-02-02 18:27:26,376 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 18:27:26,376 INFO L432 AbstractCegarLoop]: Abstraction has 81 states and 89 transitions. [2018-02-02 18:27:26,376 INFO L433 AbstractCegarLoop]: Interpolant automaton has 19 states. [2018-02-02 18:27:26,376 INFO L276 IsEmpty]: Start isEmpty. Operand 81 states and 89 transitions. [2018-02-02 18:27:26,377 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2018-02-02 18:27:26,377 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 18:27:26,377 INFO L351 BasicCegarLoop]: trace histogram [3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-02-02 18:27:26,377 INFO L371 AbstractCegarLoop]: === Iteration 17 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 18:27:26,377 INFO L82 PathProgramCache]: Analyzing trace with hash -1959345908, now seen corresponding path program 1 times [2018-02-02 18:27:26,378 INFO L213 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 18:27:26,378 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 18:27:26,378 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:27:26,378 INFO L109 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 18:27:26,379 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:27:26,392 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:27:26,393 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 18:27:26,724 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 0 proven. 9 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 18:27:26,724 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-02-02 18:27:26,724 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:27:26,729 INFO L109 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 18:27:26,742 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:27:26,744 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-02-02 18:27:26,748 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:27:26,748 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-02-02 18:27:26,756 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:27:26,756 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 18:27:26,767 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 18:27:26,767 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:22, output treesize:20 [2018-02-02 18:27:26,816 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:27:26,817 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:27:26,817 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-02-02 18:27:26,829 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:27:26,829 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:27:26,830 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:27:26,830 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 18:27:26,835 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 18:27:26,835 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:31, output treesize:24 [2018-02-02 18:27:26,873 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:27:26,875 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:27:26,875 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 18:27:26,876 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 18:27:26,881 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:27:26,882 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:34, output treesize:30 [2018-02-02 18:27:26,908 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:27:26,910 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:27:26,910 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 18:27:26,913 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 18:27:26,919 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:27:26,919 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:41, output treesize:37 [2018-02-02 18:27:27,177 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:27:27,179 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 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:27:27,179 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 18:27:27,185 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:27:27,185 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 2 xjuncts. [2018-02-02 18:27:27,187 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-02-02 18:27:27,194 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:27:27,194 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 4 variables, input treesize:47, output treesize:27 [2018-02-02 18:27:27,310 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 2 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 18:27:27,327 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-02-02 18:27:27,327 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 17] total 29 [2018-02-02 18:27:27,327 INFO L409 AbstractCegarLoop]: Interpolant automaton has 30 states [2018-02-02 18:27:27,328 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2018-02-02 18:27:27,328 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=76, Invalid=794, Unknown=0, NotChecked=0, Total=870 [2018-02-02 18:27:27,328 INFO L87 Difference]: Start difference. First operand 81 states and 89 transitions. Second operand 30 states. [2018-02-02 18:27:27,912 WARN L146 SmtUtils]: Spent 157ms on a formula simplification. DAG size of input: 77 DAG size of output 51 [2018-02-02 18:27:31,501 WARN L146 SmtUtils]: Spent 3411ms on a formula simplification. DAG size of input: 84 DAG size of output 61 [2018-02-02 18:27:34,914 WARN L146 SmtUtils]: Spent 2454ms on a formula simplification. DAG size of input: 76 DAG size of output 61 [2018-02-02 18:27:36,049 WARN L146 SmtUtils]: Spent 944ms on a formula simplification. DAG size of input: 65 DAG size of output 55 [2018-02-02 18:27:36,332 WARN L146 SmtUtils]: Spent 167ms on a formula simplification. DAG size of input: 69 DAG size of output 56 [2018-02-02 18:27:36,578 WARN L146 SmtUtils]: Spent 184ms on a formula simplification. DAG size of input: 78 DAG size of output 61 [2018-02-02 18:27:36,888 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 18:27:36,888 INFO L93 Difference]: Finished difference Result 89 states and 97 transitions. [2018-02-02 18:27:36,888 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2018-02-02 18:27:36,888 INFO L78 Accepts]: Start accepts. Automaton has 30 states. Word has length 35 [2018-02-02 18:27:36,888 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 18:27:36,888 INFO L225 Difference]: With dead ends: 89 [2018-02-02 18:27:36,888 INFO L226 Difference]: Without dead ends: 56 [2018-02-02 18:27:36,889 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 68 GetRequests, 19 SyntacticMatches, 3 SemanticMatches, 46 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 364 ImplicationChecksByTransitivity, 8.7s TimeCoverageRelationStatistics Valid=300, Invalid=1956, Unknown=0, NotChecked=0, Total=2256 [2018-02-02 18:27:36,889 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 56 states. [2018-02-02 18:27:36,890 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 56 to 56. [2018-02-02 18:27:36,890 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 56 states. [2018-02-02 18:27:36,890 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 56 states to 56 states and 62 transitions. [2018-02-02 18:27:36,890 INFO L78 Accepts]: Start accepts. Automaton has 56 states and 62 transitions. Word has length 35 [2018-02-02 18:27:36,891 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 18:27:36,891 INFO L432 AbstractCegarLoop]: Abstraction has 56 states and 62 transitions. [2018-02-02 18:27:36,891 INFO L433 AbstractCegarLoop]: Interpolant automaton has 30 states. [2018-02-02 18:27:36,891 INFO L276 IsEmpty]: Start isEmpty. Operand 56 states and 62 transitions. [2018-02-02 18:27:36,892 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2018-02-02 18:27:36,892 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 18:27:36,892 INFO L351 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-02-02 18:27:36,892 INFO L371 AbstractCegarLoop]: === Iteration 18 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 18:27:36,892 INFO L82 PathProgramCache]: Analyzing trace with hash -608695935, now seen corresponding path program 1 times [2018-02-02 18:27:36,892 INFO L213 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 18:27:36,892 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 18:27:36,893 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:27:36,893 INFO L109 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 18:27:36,893 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:27:36,901 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:27:36,902 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 18:27:37,157 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 18:27:37,157 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-02-02 18:27:37,157 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:27:37,162 INFO L109 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 18:27:37,176 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:27:37,178 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-02-02 18:27:37,182 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:27:37,182 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-02-02 18:27:37,187 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:27:37,187 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 18:27:37,191 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:27:37,191 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:21, output treesize:16 [2018-02-02 18:27:37,220 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:27:37,221 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:27:37,221 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:27:37,221 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-02-02 18:27:37,226 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:27:37,226 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:27:37,227 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 18:27:37,231 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:27:37,231 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:27, output treesize:13 [2018-02-02 18:27:37,423 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 18:27:37,440 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-02-02 18:27:37,440 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 17] total 32 [2018-02-02 18:27:37,440 INFO L409 AbstractCegarLoop]: Interpolant automaton has 33 states [2018-02-02 18:27:37,440 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2018-02-02 18:27:37,440 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=91, Invalid=965, Unknown=0, NotChecked=0, Total=1056 [2018-02-02 18:27:37,440 INFO L87 Difference]: Start difference. First operand 56 states and 62 transitions. Second operand 33 states. [2018-02-02 18:27:37,900 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 18:27:37,900 INFO L93 Difference]: Finished difference Result 74 states and 81 transitions. [2018-02-02 18:27:37,900 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2018-02-02 18:27:37,900 INFO L78 Accepts]: Start accepts. Automaton has 33 states. Word has length 35 [2018-02-02 18:27:37,900 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 18:27:37,900 INFO L225 Difference]: With dead ends: 74 [2018-02-02 18:27:37,900 INFO L226 Difference]: Without dead ends: 73 [2018-02-02 18:27:37,901 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 64 GetRequests, 21 SyntacticMatches, 0 SemanticMatches, 43 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 402 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=217, Invalid=1763, Unknown=0, NotChecked=0, Total=1980 [2018-02-02 18:27:37,901 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 73 states. [2018-02-02 18:27:37,902 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 73 to 70. [2018-02-02 18:27:37,902 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 70 states. [2018-02-02 18:27:37,902 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 70 states to 70 states and 77 transitions. [2018-02-02 18:27:37,902 INFO L78 Accepts]: Start accepts. Automaton has 70 states and 77 transitions. Word has length 35 [2018-02-02 18:27:37,903 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 18:27:37,903 INFO L432 AbstractCegarLoop]: Abstraction has 70 states and 77 transitions. [2018-02-02 18:27:37,903 INFO L433 AbstractCegarLoop]: Interpolant automaton has 33 states. [2018-02-02 18:27:37,903 INFO L276 IsEmpty]: Start isEmpty. Operand 70 states and 77 transitions. [2018-02-02 18:27:37,903 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2018-02-02 18:27:37,903 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 18:27:37,903 INFO L351 BasicCegarLoop]: trace histogram [3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-02-02 18:27:37,904 INFO L371 AbstractCegarLoop]: === Iteration 19 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 18:27:37,904 INFO L82 PathProgramCache]: Analyzing trace with hash -36117874, now seen corresponding path program 1 times [2018-02-02 18:27:37,904 INFO L213 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 18:27:37,904 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 18:27:37,905 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:27:37,905 INFO L109 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 18:27:37,905 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:27:37,913 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:27:37,914 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 18:27:38,451 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 0 proven. 9 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 18:27:38,451 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-02-02 18:27:38,451 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:27:38,456 INFO L109 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 18:27:38,468 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:27:38,471 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-02-02 18:27:38,484 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:27:38,484 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-02-02 18:27:38,491 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:27:38,491 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 18:27:38,497 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 18:27:38,497 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:27, output treesize:25 [2018-02-02 18:27:38,543 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:27:38,544 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:27:38,544 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:27:38,544 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-02-02 18:27:38,552 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:27:38,552 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 21 [2018-02-02 18:27:38,552 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 18:27:38,558 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 18:27:38,558 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:36, output treesize:25 [2018-02-02 18:27:38,608 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 16 [2018-02-02 18:27:38,609 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 15 [2018-02-02 18:27:38,609 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 18:27:38,611 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 18:27:38,617 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:27:38,617 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:41, output treesize:37 [2018-02-02 18:27:38,648 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:27:38,651 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 32 treesize of output 33 [2018-02-02 18:27:38,652 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:27:38,652 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 18:27:38,655 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 18:27:38,661 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:27:38,661 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:52, output treesize:48 [2018-02-02 18:27:39,004 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:27:39,005 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 45 treesize of output 41 [2018-02-02 18:27:39,007 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 19 [2018-02-02 18:27:39,007 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 18:27:39,019 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:27:39,020 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 2 xjuncts. [2018-02-02 18:27:39,024 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-02-02 18:27:39,043 INFO L267 ElimStorePlain]: Start of recursive call 1: 4 dim-0 vars, 1 dim-2 vars, End of recursive call: 6 dim-0 vars, and 2 xjuncts. [2018-02-02 18:27:39,043 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 5 variables, input treesize:73, output treesize:128 [2018-02-02 18:27:39,164 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 0 proven. 9 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 18:27:39,181 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-02-02 18:27:39,181 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 20] total 36 [2018-02-02 18:27:39,181 INFO L409 AbstractCegarLoop]: Interpolant automaton has 37 states [2018-02-02 18:27:39,181 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 37 interpolants. [2018-02-02 18:27:39,182 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=119, Invalid=1213, Unknown=0, NotChecked=0, Total=1332 [2018-02-02 18:27:39,182 INFO L87 Difference]: Start difference. First operand 70 states and 77 transitions. Second operand 37 states. [2018-02-02 18:27:39,769 WARN L146 SmtUtils]: Spent 202ms on a formula simplification. DAG size of input: 118 DAG size of output 51 [2018-02-02 18:27:41,123 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 18:27:41,124 INFO L93 Difference]: Finished difference Result 87 states and 95 transitions. [2018-02-02 18:27:41,124 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 29 states. [2018-02-02 18:27:41,124 INFO L78 Accepts]: Start accepts. Automaton has 37 states. Word has length 35 [2018-02-02 18:27:41,124 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 18:27:41,125 INFO L225 Difference]: With dead ends: 87 [2018-02-02 18:27:41,125 INFO L226 Difference]: Without dead ends: 85 [2018-02-02 18:27:41,126 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 75 GetRequests, 19 SyntacticMatches, 0 SemanticMatches, 56 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 815 ImplicationChecksByTransitivity, 2.5s TimeCoverageRelationStatistics Valid=368, Invalid=2938, Unknown=0, NotChecked=0, Total=3306 [2018-02-02 18:27:41,126 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 85 states. [2018-02-02 18:27:41,127 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 85 to 73. [2018-02-02 18:27:41,127 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 73 states. [2018-02-02 18:27:41,127 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 73 states to 73 states and 81 transitions. [2018-02-02 18:27:41,127 INFO L78 Accepts]: Start accepts. Automaton has 73 states and 81 transitions. Word has length 35 [2018-02-02 18:27:41,127 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 18:27:41,127 INFO L432 AbstractCegarLoop]: Abstraction has 73 states and 81 transitions. [2018-02-02 18:27:41,127 INFO L433 AbstractCegarLoop]: Interpolant automaton has 37 states. [2018-02-02 18:27:41,127 INFO L276 IsEmpty]: Start isEmpty. Operand 73 states and 81 transitions. [2018-02-02 18:27:41,128 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2018-02-02 18:27:41,128 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 18:27:41,128 INFO L351 BasicCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-02-02 18:27:41,128 INFO L371 AbstractCegarLoop]: === Iteration 20 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 18:27:41,128 INFO L82 PathProgramCache]: Analyzing trace with hash -1689703552, now seen corresponding path program 2 times [2018-02-02 18:27:41,128 INFO L213 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 18:27:41,128 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 18:27:41,129 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:27:41,129 INFO L109 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 18:27:41,129 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:27:41,142 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:27:41,143 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 18:27:41,402 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 18:27:41,402 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-02-02 18:27:41,402 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:27:41,408 INFO L109 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-02-02 18:27:41,426 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-02-02 18:27:41,426 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-02-02 18:27:41,428 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-02-02 18:27:41,430 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-02-02 18:27:41,430 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-02-02 18:27:41,431 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 18:27:41,431 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:6, output treesize:5 [2018-02-02 18:27:41,438 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:27:41,439 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-02-02 18:27:41,445 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:27:41,446 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:27:41,446 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:27:41,446 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 18:27:41,450 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 18:27:41,450 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:20, output treesize:13 [2018-02-02 18:27:41,481 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 13 [2018-02-02 18:27:41,482 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:27:41,483 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 18:27:41,484 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 18:27:41,487 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:27:41,487 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:27, output treesize:23 [2018-02-02 18:27:41,682 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 24 treesize of output 25 [2018-02-02 18:27:41,683 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:27:41,683 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 18:27:41,686 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 18:27:41,692 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-02-02 18:27:41,692 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:37, output treesize:26 [2018-02-02 18:27:41,753 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 18 [2018-02-02 18:27:41,758 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:27:41,759 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-02-02 18:27:41,761 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-02-02 18:27:41,768 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 2 xjuncts. [2018-02-02 18:27:41,768 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:36, output treesize:37 [2018-02-02 18:27:41,811 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 18:27:41,843 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-02-02 18:27:41,844 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 27 [2018-02-02 18:27:41,844 INFO L409 AbstractCegarLoop]: Interpolant automaton has 28 states [2018-02-02 18:27:41,844 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2018-02-02 18:27:41,844 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=64, Invalid=692, Unknown=0, NotChecked=0, Total=756 [2018-02-02 18:27:41,845 INFO L87 Difference]: Start difference. First operand 73 states and 81 transitions. Second operand 28 states. [2018-02-02 18:27:42,957 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 18:27:42,957 INFO L93 Difference]: Finished difference Result 81 states and 87 transitions. [2018-02-02 18:27:42,957 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2018-02-02 18:27:42,957 INFO L78 Accepts]: Start accepts. Automaton has 28 states. Word has length 36 [2018-02-02 18:27:42,957 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 18:27:42,957 INFO L225 Difference]: With dead ends: 81 [2018-02-02 18:27:42,958 INFO L226 Difference]: Without dead ends: 81 [2018-02-02 18:27:42,958 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 66 GetRequests, 24 SyntacticMatches, 1 SemanticMatches, 41 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 197 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=200, Invalid=1606, Unknown=0, NotChecked=0, Total=1806 [2018-02-02 18:27:42,958 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 81 states. [2018-02-02 18:27:42,960 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 81 to 56. [2018-02-02 18:27:42,960 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 56 states. [2018-02-02 18:27:42,960 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 56 states to 56 states and 62 transitions. [2018-02-02 18:27:42,960 INFO L78 Accepts]: Start accepts. Automaton has 56 states and 62 transitions. Word has length 36 [2018-02-02 18:27:42,960 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 18:27:42,960 INFO L432 AbstractCegarLoop]: Abstraction has 56 states and 62 transitions. [2018-02-02 18:27:42,960 INFO L433 AbstractCegarLoop]: Interpolant automaton has 28 states. [2018-02-02 18:27:42,961 INFO L276 IsEmpty]: Start isEmpty. Operand 56 states and 62 transitions. [2018-02-02 18:27:42,961 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2018-02-02 18:27:42,961 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 18:27:42,961 INFO L351 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-02-02 18:27:42,961 INFO L371 AbstractCegarLoop]: === Iteration 21 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 18:27:42,961 INFO L82 PathProgramCache]: Analyzing trace with hash -601444785, now seen corresponding path program 1 times [2018-02-02 18:27:42,961 INFO L213 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 18:27:42,962 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 18:27:42,962 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:27:42,962 INFO L107 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-02-02 18:27:42,962 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:27:42,971 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:27:42,972 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 18:27:43,252 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 0 proven. 9 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 18:27:43,252 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-02-02 18:27:43,252 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:27:43,258 INFO L109 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 18:27:43,272 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:27:43,274 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-02-02 18:27:43,287 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-02-02 18:27:43,288 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-02-02 18:27:43,292 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:27:43,292 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 18:27:43,296 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:27:43,296 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:21, output treesize:16 [2018-02-02 18:27:43,327 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:27:43,328 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:27:43,328 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:27:43,329 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-02-02 18:27:43,337 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:27:43,337 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:27:43,338 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:27:43,338 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 18:27:43,342 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 18:27:43,342 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:30, output treesize:19 [2018-02-02 18:27:43,377 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 12 [2018-02-02 18:27:43,378 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 11 [2018-02-02 18:27:43,379 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 18:27:43,379 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 18:27:43,382 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-02-02 18:27:43,382 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:28, output treesize:24 [2018-02-02 18:27:43,568 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:27:43,570 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 24 [2018-02-02 18:27:43,572 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-02-02 18:27:43,572 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 18:27:43,575 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 18:27:43,580 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-02-02 18:27:43,580 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:41, output treesize:30 [2018-02-02 18:27:43,634 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 15 [2018-02-02 18:27:43,639 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 1 case distinctions, treesize of input 15 treesize of output 12 [2018-02-02 18:27:43,640 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-02-02 18:27:43,642 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-02-02 18:27:43,649 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: 2 dim-0 vars, and 2 xjuncts. [2018-02-02 18:27:43,649 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:44, output treesize:51 [2018-02-02 18:27:43,727 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 0 proven. 9 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 18:27:43,745 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-02-02 18:27:43,745 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 19] total 39 [2018-02-02 18:27:43,745 INFO L409 AbstractCegarLoop]: Interpolant automaton has 40 states [2018-02-02 18:27:43,746 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 40 interpolants. [2018-02-02 18:27:43,746 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=118, Invalid=1442, Unknown=0, NotChecked=0, Total=1560 [2018-02-02 18:27:43,746 INFO L87 Difference]: Start difference. First operand 56 states and 62 transitions. Second operand 40 states. [2018-02-02 18:27:45,487 WARN L146 SmtUtils]: Spent 147ms on a formula simplification. DAG size of input: 70 DAG size of output 68 [2018-02-02 18:27:45,773 WARN L146 SmtUtils]: Spent 106ms on a formula simplification. DAG size of input: 83 DAG size of output 79 [2018-02-02 18:27:45,949 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 18:27:45,949 INFO L93 Difference]: Finished difference Result 94 states and 101 transitions. [2018-02-02 18:27:45,950 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 35 states. [2018-02-02 18:27:45,950 INFO L78 Accepts]: Start accepts. Automaton has 40 states. Word has length 38 [2018-02-02 18:27:45,950 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 18:27:45,950 INFO L225 Difference]: With dead ends: 94 [2018-02-02 18:27:45,950 INFO L226 Difference]: Without dead ends: 92 [2018-02-02 18:27:45,951 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 88 GetRequests, 21 SyntacticMatches, 0 SemanticMatches, 67 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1141 ImplicationChecksByTransitivity, 2.2s TimeCoverageRelationStatistics Valid=446, Invalid=4246, Unknown=0, NotChecked=0, Total=4692 [2018-02-02 18:27:45,951 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 92 states. [2018-02-02 18:27:45,952 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 92 to 62. [2018-02-02 18:27:45,952 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 62 states. [2018-02-02 18:27:45,952 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 62 states to 62 states and 68 transitions. [2018-02-02 18:27:45,953 INFO L78 Accepts]: Start accepts. Automaton has 62 states and 68 transitions. Word has length 38 [2018-02-02 18:27:45,953 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 18:27:45,953 INFO L432 AbstractCegarLoop]: Abstraction has 62 states and 68 transitions. [2018-02-02 18:27:45,953 INFO L433 AbstractCegarLoop]: Interpolant automaton has 40 states. [2018-02-02 18:27:45,953 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states and 68 transitions. [2018-02-02 18:27:45,953 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2018-02-02 18:27:45,953 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 18:27:45,953 INFO L351 BasicCegarLoop]: trace histogram [4, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-02-02 18:27:45,953 INFO L371 AbstractCegarLoop]: === Iteration 22 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 18:27:45,954 INFO L82 PathProgramCache]: Analyzing trace with hash -28866724, now seen corresponding path program 2 times [2018-02-02 18:27:45,954 INFO L213 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 18:27:45,954 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 18:27:45,954 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:27:45,955 INFO L109 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 18:27:45,955 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:27:45,965 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:27:45,965 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 18:27:46,302 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 0 proven. 18 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 18:27:46,303 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-02-02 18:27:46,303 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 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-02-02 18:27:46,307 INFO L109 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-02-02 18:27:46,322 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-02-02 18:27:46,322 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-02-02 18:27:46,324 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-02-02 18:27:46,371 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:27:46,371 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-02-02 18:27:46,378 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:27:46,378 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 18:27:46,384 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 18:27:46,384 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:27, output treesize:25 [2018-02-02 18:27:46,449 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:27:46,450 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:27:46,450 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 21 [2018-02-02 18:27:46,450 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-02-02 18:27:46,461 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:27:46,462 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:27:46,462 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:27:46,462 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 18:27:46,469 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 18:27:46,469 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:36, output treesize:25 [2018-02-02 18:27:46,539 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 16 [2018-02-02 18:27:46,543 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 15 [2018-02-02 18:27:46,543 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 18:27:46,545 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 18:27:46,552 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:27:46,552 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:41, output treesize:37 [2018-02-02 18:27:46,597 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:27:46,601 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 32 treesize of output 33 [2018-02-02 18:27:46,603 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:27:46,603 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 18:27:46,608 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 18:27:46,617 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:27:46,617 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:52, output treesize:48 [2018-02-02 18:27:49,958 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:27:49,959 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 51 treesize of output 45 [2018-02-02 18:27:50,009 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 4 disjoint index pairs (out of 3 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 26 treesize of output 41 [2018-02-02 18:27:50,010 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-02-02 18:27:50,030 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:27:50,030 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 2 xjuncts. [2018-02-02 18:27:50,038 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-02-02 18:27:50,074 INFO L267 ElimStorePlain]: Start of recursive call 1: 6 dim-0 vars, 1 dim-2 vars, End of recursive call: 9 dim-0 vars, and 2 xjuncts. [2018-02-02 18:27:50,074 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 7 variables, input treesize:89, output treesize:227 [2018-02-02 18:27:50,291 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 0 proven. 18 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 18:27:50,322 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-02-02 18:27:50,322 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 22] total 40 [2018-02-02 18:27:50,322 INFO L409 AbstractCegarLoop]: Interpolant automaton has 41 states [2018-02-02 18:27:50,323 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 41 interpolants. [2018-02-02 18:27:50,323 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=114, Invalid=1525, Unknown=1, NotChecked=0, Total=1640 [2018-02-02 18:27:50,323 INFO L87 Difference]: Start difference. First operand 62 states and 68 transitions. Second operand 41 states. [2018-02-02 18:27:51,423 WARN L146 SmtUtils]: Spent 111ms on a formula simplification. DAG size of input: 113 DAG size of output 106 [2018-02-02 18:27:51,602 WARN L146 SmtUtils]: Spent 120ms on a formula simplification. DAG size of input: 121 DAG size of output 117 [2018-02-02 18:27:52,205 WARN L146 SmtUtils]: Spent 140ms on a formula simplification. DAG size of input: 124 DAG size of output 120 [2018-02-02 18:27:52,487 WARN L146 SmtUtils]: Spent 159ms on a formula simplification. DAG size of input: 133 DAG size of output 122 [2018-02-02 18:27:52,870 WARN L146 SmtUtils]: Spent 262ms on a formula simplification. DAG size of input: 130 DAG size of output 115 [2018-02-02 18:27:53,050 WARN L146 SmtUtils]: Spent 111ms on a formula simplification. DAG size of input: 127 DAG size of output 121 [2018-02-02 18:27:53,275 WARN L146 SmtUtils]: Spent 146ms on a formula simplification. DAG size of input: 153 DAG size of output 136 [2018-02-02 18:27:53,446 WARN L146 SmtUtils]: Spent 117ms on a formula simplification. DAG size of input: 133 DAG size of output 117 [2018-02-02 18:27:57,397 WARN L146 SmtUtils]: Spent 108ms on a formula simplification. DAG size of input: 134 DAG size of output 120 [2018-02-02 18:27:57,610 WARN L146 SmtUtils]: Spent 124ms on a formula simplification. DAG size of input: 139 DAG size of output 130 [2018-02-02 18:27:59,802 WARN L146 SmtUtils]: Spent 107ms on a formula simplification. DAG size of input: 136 DAG size of output 122 [2018-02-02 18:27:59,974 WARN L146 SmtUtils]: Spent 100ms on a formula simplification. DAG size of input: 113 DAG size of output 100 [2018-02-02 18:28:00,188 WARN L146 SmtUtils]: Spent 121ms on a formula simplification. DAG size of input: 136 DAG size of output 122 [2018-02-02 18:28:00,421 WARN L146 SmtUtils]: Spent 145ms on a formula simplification. DAG size of input: 160 DAG size of output 137 [2018-02-02 18:28:00,565 WARN L146 SmtUtils]: Spent 107ms on a formula simplification. DAG size of input: 116 DAG size of output 107 [2018-02-02 18:28:03,064 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 18:28:03,064 INFO L93 Difference]: Finished difference Result 104 states and 111 transitions. [2018-02-02 18:28:03,066 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 43 states. [2018-02-02 18:28:03,066 INFO L78 Accepts]: Start accepts. Automaton has 41 states. Word has length 38 [2018-02-02 18:28:03,066 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 18:28:03,067 INFO L225 Difference]: With dead ends: 104 [2018-02-02 18:28:03,067 INFO L226 Difference]: Without dead ends: 101 [2018-02-02 18:28:03,068 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 92 GetRequests, 17 SyntacticMatches, 1 SemanticMatches, 74 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1354 ImplicationChecksByTransitivity, 7.7s TimeCoverageRelationStatistics Valid=550, Invalid=5149, Unknown=1, NotChecked=0, Total=5700 [2018-02-02 18:28:03,068 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 101 states. [2018-02-02 18:28:03,068 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 101 to 71. [2018-02-02 18:28:03,069 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 71 states. [2018-02-02 18:28:03,069 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 78 transitions. [2018-02-02 18:28:03,069 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 78 transitions. Word has length 38 [2018-02-02 18:28:03,069 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 18:28:03,069 INFO L432 AbstractCegarLoop]: Abstraction has 71 states and 78 transitions. [2018-02-02 18:28:03,069 INFO L433 AbstractCegarLoop]: Interpolant automaton has 41 states. [2018-02-02 18:28:03,069 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 78 transitions. [2018-02-02 18:28:03,069 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2018-02-02 18:28:03,069 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 18:28:03,070 INFO L351 BasicCegarLoop]: trace histogram [3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-02-02 18:28:03,070 INFO L371 AbstractCegarLoop]: === Iteration 23 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 18:28:03,070 INFO L82 PathProgramCache]: Analyzing trace with hash 669200065, now seen corresponding path program 2 times [2018-02-02 18:28:03,070 INFO L213 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 18:28:03,070 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 18:28:03,070 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:28:03,070 INFO L107 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-02-02 18:28:03,070 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:28:03,079 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:28:03,080 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 18:28:03,766 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:28:03,766 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-02-02 18:28:03,766 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 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-02-02 18:28:03,771 INFO L109 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-02-02 18:28:03,788 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-02-02 18:28:03,789 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-02-02 18:28:03,791 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-02-02 18:28:03,793 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:28:03,794 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-02-02 18:28:03,799 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:28:03,799 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 18:28:03,803 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:28:03,804 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:24, output treesize:19 [2018-02-02 18:28:03,866 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:28:03,867 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:28:03,867 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:28:03,868 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-02-02 18:28:03,880 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:28:03,880 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:28:03,881 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 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:28:03,881 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 18:28:03,886 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 18:28:03,886 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:33, output treesize:22 [2018-02-02 18:28:03,945 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 13 [2018-02-02 18:28:03,947 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 12 [2018-02-02 18:28:03,947 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 18:28:03,948 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 18:28:03,953 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-02-02 18:28:03,953 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:35, output treesize:31 [2018-02-02 18:28:04,238 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:28:04,241 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 24 treesize of output 25 [2018-02-02 18:28:04,242 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:28:04,243 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 18:28:04,246 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 18:28:04,256 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-02-02 18:28:04,256 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:47, output treesize:36 [2018-02-02 18:28:04,459 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:28:04,464 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:28:04,464 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-02-02 18:28:04,467 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-02-02 18:28:04,477 INFO L267 ElimStorePlain]: Start of recursive call 1: 4 dim-0 vars, 1 dim-2 vars, End of recursive call: 4 dim-0 vars, and 2 xjuncts. [2018-02-02 18:28:04,477 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 5 variables, input treesize:57, output treesize:65 [2018-02-02 18:28:04,670 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:28:04,686 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-02-02 18:28:04,686 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [23, 21] total 41 [2018-02-02 18:28:04,687 INFO L409 AbstractCegarLoop]: Interpolant automaton has 42 states [2018-02-02 18:28:04,687 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 42 interpolants. [2018-02-02 18:28:04,687 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=101, Invalid=1621, Unknown=0, NotChecked=0, Total=1722 [2018-02-02 18:28:04,687 INFO L87 Difference]: Start difference. First operand 71 states and 78 transitions. Second operand 42 states. [2018-02-02 18:28:05,700 WARN L146 SmtUtils]: Spent 117ms on a formula simplification. DAG size of input: 97 DAG size of output 93 [2018-02-02 18:28:06,033 WARN L146 SmtUtils]: Spent 104ms on a formula simplification. DAG size of input: 99 DAG size of output 95 [2018-02-02 18:28:07,340 WARN L146 SmtUtils]: Spent 238ms on a formula simplification. DAG size of input: 89 DAG size of output 88 [2018-02-02 18:28:07,601 WARN L146 SmtUtils]: Spent 160ms on a formula simplification. DAG size of input: 71 DAG size of output 71 [2018-02-02 18:28:09,670 WARN L146 SmtUtils]: Spent 1649ms on a formula simplification. DAG size of input: 70 DAG size of output 69 [2018-02-02 18:28:10,252 WARN L146 SmtUtils]: Spent 187ms on a formula simplification. DAG size of input: 93 DAG size of output 92 [2018-02-02 18:28:10,514 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-02-02 18:28:10,514 INFO L93 Difference]: Finished difference Result 116 states and 124 transitions. [2018-02-02 18:28:10,514 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 41 states. [2018-02-02 18:28:10,515 INFO L78 Accepts]: Start accepts. Automaton has 42 states. Word has length 41 [2018-02-02 18:28:10,515 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-02-02 18:28:10,515 INFO L225 Difference]: With dead ends: 116 [2018-02-02 18:28:10,515 INFO L226 Difference]: Without dead ends: 115 [2018-02-02 18:28:10,516 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 94 GetRequests, 23 SyntacticMatches, 0 SemanticMatches, 71 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 995 ImplicationChecksByTransitivity, 6.0s TimeCoverageRelationStatistics Valid=402, Invalid=4854, Unknown=0, NotChecked=0, Total=5256 [2018-02-02 18:28:10,517 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 115 states. [2018-02-02 18:28:10,518 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 115 to 71. [2018-02-02 18:28:10,518 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 71 states. [2018-02-02 18:28:10,518 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 78 transitions. [2018-02-02 18:28:10,519 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 78 transitions. Word has length 41 [2018-02-02 18:28:10,519 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-02-02 18:28:10,519 INFO L432 AbstractCegarLoop]: Abstraction has 71 states and 78 transitions. [2018-02-02 18:28:10,519 INFO L433 AbstractCegarLoop]: Interpolant automaton has 42 states. [2018-02-02 18:28:10,519 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 78 transitions. [2018-02-02 18:28:10,519 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2018-02-02 18:28:10,519 INFO L343 BasicCegarLoop]: Found error trace [2018-02-02 18:28:10,519 INFO L351 BasicCegarLoop]: trace histogram [5, 5, 4, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-02-02 18:28:10,520 INFO L371 AbstractCegarLoop]: === Iteration 24 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-02-02 18:28:10,520 INFO L82 PathProgramCache]: Analyzing trace with hash -652090471, now seen corresponding path program 1 times [2018-02-02 18:28:10,520 INFO L213 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-02-02 18:28:10,520 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-02-02 18:28:10,520 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:28:10,521 INFO L107 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-02-02 18:28:10,521 INFO L125 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-02-02 18:28:10,533 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:28:10,534 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-02-02 18:28:11,290 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 0 proven. 33 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 18:28:11,290 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-02-02 18:28:11,290 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 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-02-02 18:28:11,295 INFO L109 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-02-02 18:28:11,309 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-02-02 18:28:11,311 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-02-02 18:28:11,313 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:28:11,313 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-02-02 18:28:11,318 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:28:11,318 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 18:28:11,322 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 18:28:11,322 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:24, output treesize:22 [2018-02-02 18:28:11,368 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:28:11,369 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:28:11,369 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:28:11,369 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-02-02 18:28:11,375 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:28:11,376 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 21 [2018-02-02 18:28:11,376 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 18:28:11,381 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 18:28:11,381 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:33, output treesize:22 [2018-02-02 18:28:11,429 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 16 [2018-02-02 18:28:11,430 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 15 [2018-02-02 18:28:11,430 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 18:28:11,431 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 18:28:11,436 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:28:11,436 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:38, output treesize:34 [2018-02-02 18:28:11,467 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:28:11,469 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 32 treesize of output 33 [2018-02-02 18:28:11,470 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:28:11,470 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-02-02 18:28:11,474 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-02-02 18:28:11,479 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:28:11,479 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:47, output treesize:43 [2018-02-02 18:28:12,217 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:28:12,218 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 55 treesize of output 49 [2018-02-02 18:28:12,221 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:28:12,222 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:28:12,223 INFO L700 Elim1Store]: detected not equals via solver [2018-02-02 18:28:12,228 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 4 select indices, 4 select index equivalence classes, 7 disjoint index pairs (out of 6 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 35 treesize of output 73 [2018-02-02 18:28:12,229 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-02-02 18:28:12,245 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:28:12,246 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-02-02 18:28:12,254 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-02-02 18:28:12,270 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:28:12,270 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 4 variables, input treesize:78, output treesize:126 [2018-02-02 18:28:12,712 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 0 proven. 33 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-02-02 18:28:12,731 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-02-02 18:28:12,731 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [26, 25] total 48 [2018-02-02 18:28:12,731 INFO L409 AbstractCegarLoop]: Interpolant automaton has 49 states [2018-02-02 18:28:12,731 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 49 interpolants. [2018-02-02 18:28:12,732 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=129, Invalid=2223, Unknown=0, NotChecked=0, Total=2352 [2018-02-02 18:28:12,732 INFO L87 Difference]: Start difference. First operand 71 states and 78 transitions. Second operand 49 states. [2018-02-02 18:28:13,658 WARN L146 SmtUtils]: Spent 148ms on a formula simplification. DAG size of input: 123 DAG size of output 122 Received shutdown request... [2018-02-02 18:28:15,707 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-02-02 18:28:15,707 WARN L491 AbstractCegarLoop]: Verification canceled [2018-02-02 18:28:15,711 WARN L185 ceAbstractionStarter]: Timeout [2018-02-02 18:28:15,711 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 02.02 06:28:15 BoogieIcfgContainer [2018-02-02 18:28:15,711 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-02-02 18:28:15,712 INFO L168 Benchmark]: Toolchain (without parser) took 97602.75 ms. Allocated memory was 400.0 MB in the beginning and 727.2 MB in the end (delta: 327.2 MB). Free memory was 356.9 MB in the beginning and 606.2 MB in the end (delta: -249.3 MB). Peak memory consumption was 77.8 MB. Max. memory is 5.3 GB. [2018-02-02 18:28:15,713 INFO L168 Benchmark]: CDTParser took 0.15 ms. Allocated memory is still 400.0 MB. Free memory is still 363.5 MB. There was no memory consumed. Max. memory is 5.3 GB. [2018-02-02 18:28:15,713 INFO L168 Benchmark]: CACSL2BoogieTranslator took 151.88 ms. Allocated memory is still 400.0 MB. Free memory was 356.9 MB in the beginning and 346.3 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:28:15,713 INFO L168 Benchmark]: Boogie Preprocessor took 26.51 ms. Allocated memory is still 400.0 MB. Free memory was 346.3 MB in the beginning and 345.0 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:28:15,713 INFO L168 Benchmark]: RCFGBuilder took 219.78 ms. Allocated memory is still 400.0 MB. Free memory was 345.0 MB in the beginning and 324.4 MB in the end (delta: 20.6 MB). Peak memory consumption was 20.6 MB. Max. memory is 5.3 GB. [2018-02-02 18:28:15,714 INFO L168 Benchmark]: TraceAbstraction took 97202.03 ms. Allocated memory was 400.0 MB in the beginning and 727.2 MB in the end (delta: 327.2 MB). Free memory was 323.0 MB in the beginning and 606.2 MB in the end (delta: -283.2 MB). Peak memory consumption was 44.0 MB. Max. memory is 5.3 GB. [2018-02-02 18:28:15,717 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.15 ms. Allocated memory is still 400.0 MB. Free memory is still 363.5 MB. There was no memory consumed. Max. memory is 5.3 GB. * CACSL2BoogieTranslator took 151.88 ms. Allocated memory is still 400.0 MB. Free memory was 356.9 MB in the beginning and 346.3 MB in the end (delta: 10.6 MB). Peak memory consumption was 10.6 MB. Max. memory is 5.3 GB. * Boogie Preprocessor took 26.51 ms. Allocated memory is still 400.0 MB. Free memory was 346.3 MB in the beginning and 345.0 MB in the end (delta: 1.3 MB). Peak memory consumption was 1.3 MB. Max. memory is 5.3 GB. * RCFGBuilder took 219.78 ms. Allocated memory is still 400.0 MB. Free memory was 345.0 MB in the beginning and 324.4 MB in the end (delta: 20.6 MB). Peak memory consumption was 20.6 MB. Max. memory is 5.3 GB. * TraceAbstraction took 97202.03 ms. Allocated memory was 400.0 MB in the beginning and 727.2 MB in the end (delta: 327.2 MB). Free memory was 323.0 MB in the beginning and 606.2 MB in the end (delta: -283.2 MB). Peak memory consumption was 44.0 MB. Max. memory is 5.3 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 574). Cancelled while BasicCegarLoop was constructing difference of abstraction (71states) and interpolant automaton (currently 13 states, 49 states before enhancement), while PredicateComparison was comparing new predicate (quantified with 0quantifier alternations) to 57 known predicates. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 573). Cancelled while BasicCegarLoop was constructing difference of abstraction (71states) and interpolant automaton (currently 13 states, 49 states before enhancement), while PredicateComparison was comparing new predicate (quantified with 0quantifier alternations) to 57 known predicates. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 574). Cancelled while BasicCegarLoop was constructing difference of abstraction (71states) and interpolant automaton (currently 13 states, 49 states before enhancement), while PredicateComparison was comparing new predicate (quantified with 0quantifier alternations) to 57 known predicates. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 573). Cancelled while BasicCegarLoop was constructing difference of abstraction (71states) and interpolant automaton (currently 13 states, 49 states before enhancement), while PredicateComparison was comparing new predicate (quantified with 0quantifier alternations) to 57 known predicates. - TimeoutResultAtElement [Line: 557]: Timeout (TraceAbstraction) Unable to prove that all allocated memory was freed (line 557). Cancelled while BasicCegarLoop was constructing difference of abstraction (71states) and interpolant automaton (currently 13 states, 49 states before enhancement), while PredicateComparison was comparing new predicate (quantified with 0quantifier alternations) to 57 known predicates. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 553). Cancelled while BasicCegarLoop was constructing difference of abstraction (71states) and interpolant automaton (currently 13 states, 49 states before enhancement), while PredicateComparison was comparing new predicate (quantified with 0quantifier alternations) to 57 known predicates. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 549). Cancelled while BasicCegarLoop was constructing difference of abstraction (71states) and interpolant automaton (currently 13 states, 49 states before enhancement), while PredicateComparison was comparing new predicate (quantified with 0quantifier alternations) to 57 known predicates. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 546). Cancelled while BasicCegarLoop was constructing difference of abstraction (71states) and interpolant automaton (currently 13 states, 49 states before enhancement), while PredicateComparison was comparing new predicate (quantified with 0quantifier alternations) to 57 known predicates. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 549). Cancelled while BasicCegarLoop was constructing difference of abstraction (71states) and interpolant automaton (currently 13 states, 49 states before enhancement), while PredicateComparison was comparing new predicate (quantified with 0quantifier alternations) to 57 known predicates. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 546). Cancelled while BasicCegarLoop was constructing difference of abstraction (71states) and interpolant automaton (currently 13 states, 49 states before enhancement), while PredicateComparison was comparing new predicate (quantified with 0quantifier alternations) to 57 known predicates. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 549). Cancelled while BasicCegarLoop was constructing difference of abstraction (71states) and interpolant automaton (currently 13 states, 49 states before enhancement), while PredicateComparison was comparing new predicate (quantified with 0quantifier alternations) to 57 known predicates. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 553). Cancelled while BasicCegarLoop was constructing difference of abstraction (71states) and interpolant automaton (currently 13 states, 49 states before enhancement), while PredicateComparison was comparing new predicate (quantified with 0quantifier alternations) to 57 known predicates. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 549). Cancelled while BasicCegarLoop was constructing difference of abstraction (71states) and interpolant automaton (currently 13 states, 49 states before enhancement), while PredicateComparison was comparing new predicate (quantified with 0quantifier alternations) to 57 known predicates. - StatisticsResult: Ultimate Automizer benchmark data CFG has 4 procedures, 54 locations, 13 error locations. TIMEOUT Result, 97.1s OverallTime, 24 OverallIterations, 5 TraceHistogramMax, 81.6s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 823 SDtfs, 2017 SDslu, 5597 SDs, 0 SdLazy, 8293 SolverSat, 799 SolverUnsat, 11 SolverUnknown, 0 SolverNotchecked, 34.0s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 890 GetRequests, 234 SyntacticMatches, 6 SemanticMatches, 649 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6811 ImplicationChecksByTransitivity, 58.8s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=81occurred in iteration=16, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s AbstIntTime, 0 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 0.0s AutomataMinimizationTime, 23 MinimizatonAttempts, 243 StatesRemovedByMinimization, 16 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.3s SatisfiabilityAnalysisTime, 14.4s InterpolantComputationTime, 1028 NumberOfCodeBlocks, 1028 NumberOfCodeBlocksAsserted, 39 NumberOfCheckSat, 993 ConstructedInterpolants, 143 QuantifiedInterpolants, 578636 SizeOfPredicates, 179 NumberOfNonLiveVariables, 1894 ConjunctsInSsa, 583 ConjunctsInUnsatCore, 35 InterpolantComputations, 13 PerfectInterpolantSequences, 6/242 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, ReuseStatistics: No data available RESULT: Ultimate could not prove your program: Timeout Written .csv to /home/ultimate/work/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/openbsd_cstrncat-alloca_true-valid-memsafety_true-termination.i_svcomp-DerefFreeMemtrack-32bit-Automizer_Camel.epf_AutomizerC.xml/Csv-Benchmark-0-2018-02-02_18-28-15-723.csv Written .csv to /home/ultimate/work/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/openbsd_cstrncat-alloca_true-valid-memsafety_true-termination.i_svcomp-DerefFreeMemtrack-32bit-Automizer_Camel.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-0-2018-02-02_18-28-15-723.csv Completed graceful shutdown