java -Xmx6000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data ./data --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -tc ../../../trunk/examples/toolchains/AutomizerC.xml -s ../../../trunk/examples/settings/ai/eq-bench/svcomp-DerefFreeMemtrack-32bit-Automizer_Camel+AI_EQ_SS.epf -i ../../../trunk/examples/svcomp/array-memsafety/substring-alloca_true-valid-memsafety_true-termination.i -------------------------------------------------------------------------------- This is Ultimate 0.1.23-5f7ec6e [2018-01-31 08:35:47,345 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-01-31 08:35:47,347 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-01-31 08:35:47,375 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-01-31 08:35:47,375 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-01-31 08:35:47,376 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-01-31 08:35:47,377 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-01-31 08:35:47,381 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-01-31 08:35:47,383 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-01-31 08:35:47,384 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-01-31 08:35:47,386 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-01-31 08:35:47,386 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-01-31 08:35:47,387 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-01-31 08:35:47,388 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-01-31 08:35:47,400 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-01-31 08:35:47,403 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-01-31 08:35:47,405 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-01-31 08:35:47,406 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-01-31 08:35:47,408 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-01-31 08:35:47,414 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-01-31 08:35:47,416 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-01-31 08:35:47,417 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-01-31 08:35:47,417 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-01-31 08:35:47,418 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-01-31 08:35:47,419 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-01-31 08:35:47,424 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-01-31 08:35:47,425 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-01-31 08:35:47,425 INFO L177 SettingsManager]: PEA to Boogie provides no preferences, ignoring... [2018-01-31 08:35:47,425 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-01-31 08:35:47,425 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-01-31 08:35:47,426 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-01-31 08:35:47,426 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/ai/eq-bench/svcomp-DerefFreeMemtrack-32bit-Automizer_Camel+AI_EQ_SS.epf [2018-01-31 08:35:47,442 INFO L110 SettingsManager]: Loading preferences was successful [2018-01-31 08:35:47,443 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-01-31 08:35:47,445 INFO L131 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2018-01-31 08:35:47,445 INFO L133 SettingsManager]: * to procedures, called more than once=true [2018-01-31 08:35:47,445 INFO L131 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2018-01-31 08:35:47,445 INFO L133 SettingsManager]: * Abstract domain for RCFG-of-the-future=VPDomain [2018-01-31 08:35:47,445 INFO L133 SettingsManager]: * Use the RCFG-of-the-future interface=true [2018-01-31 08:35:47,446 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-01-31 08:35:47,446 INFO L133 SettingsManager]: * sizeof long=4 [2018-01-31 08:35:47,446 INFO L133 SettingsManager]: * Check unreachability of error function in SV-COMP mode=false [2018-01-31 08:35:47,446 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-01-31 08:35:47,447 INFO L133 SettingsManager]: * sizeof POINTER=4 [2018-01-31 08:35:47,447 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-01-31 08:35:47,447 INFO L133 SettingsManager]: * Check for the main procedure if all allocated memory was freed=true [2018-01-31 08:35:47,447 INFO L133 SettingsManager]: * Bitprecise bitfields=true [2018-01-31 08:35:47,447 INFO L133 SettingsManager]: * SV-COMP memtrack compatibility mode=true [2018-01-31 08:35:47,447 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-01-31 08:35:47,448 INFO L133 SettingsManager]: * sizeof long double=12 [2018-01-31 08:35:47,448 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-01-31 08:35:47,448 INFO L133 SettingsManager]: * Size of a code block=SingleStatement [2018-01-31 08:35:47,449 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-01-31 08:35:47,449 INFO L133 SettingsManager]: * Add additional assume for each assert=false [2018-01-31 08:35:47,449 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-01-31 08:35:47,449 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-01-31 08:35:47,449 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-01-31 08:35:47,449 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-01-31 08:35:47,450 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-01-31 08:35:47,450 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-01-31 08:35:47,450 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-01-31 08:35:47,450 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-01-31 08:35:47,450 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-01-31 08:35:47,450 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-01-31 08:35:47,451 INFO L131 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2018-01-31 08:35:47,451 INFO L133 SettingsManager]: * TransformationType=HEAP_SEPARATOR [2018-01-31 08:35:47,504 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-01-31 08:35:47,518 INFO L266 ainManager$Toolchain]: [Toolchain 1]: Parser(s) successfully initialized [2018-01-31 08:35:47,522 INFO L222 ainManager$Toolchain]: [Toolchain 1]: Toolchain data selected. [2018-01-31 08:35:47,523 INFO L271 PluginConnector]: Initializing CDTParser... [2018-01-31 08:35:47,524 INFO L276 PluginConnector]: CDTParser initialized [2018-01-31 08:35:47,525 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/array-memsafety/substring-alloca_true-valid-memsafety_true-termination.i [2018-01-31 08:35:47,712 INFO L304 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-01-31 08:35:47,723 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2018-01-31 08:35:47,724 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2018-01-31 08:35:47,724 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2018-01-31 08:35:47,731 INFO L276 PluginConnector]: CACSL2BoogieTranslator initialized [2018-01-31 08:35:47,732 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 31.01 08:35:47" (1/1) ... [2018-01-31 08:35:47,736 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@4f69a0cf and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.01 08:35:47, skipping insertion in model container [2018-01-31 08:35:47,736 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 31.01 08:35:47" (1/1) ... [2018-01-31 08:35:47,756 INFO L153 Dispatcher]: Using SV-COMP mode [2018-01-31 08:35:47,817 INFO L153 Dispatcher]: Using SV-COMP mode [2018-01-31 08:35:47,995 INFO L450 PostProcessor]: Settings: Checked method=main [2018-01-31 08:35:48,022 INFO L450 PostProcessor]: Settings: Checked method=main [2018-01-31 08:35:48,036 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.01 08:35:48 WrapperNode [2018-01-31 08:35:48,036 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2018-01-31 08:35:48,038 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-01-31 08:35:48,038 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-01-31 08:35:48,038 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-01-31 08:35:48,054 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.01 08:35:48" (1/1) ... [2018-01-31 08:35:48,054 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.01 08:35:48" (1/1) ... [2018-01-31 08:35:48,065 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.01 08:35:48" (1/1) ... [2018-01-31 08:35:48,066 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.01 08:35:48" (1/1) ... [2018-01-31 08:35:48,071 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.01 08:35:48" (1/1) ... [2018-01-31 08:35:48,077 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.01 08:35:48" (1/1) ... [2018-01-31 08:35:48,080 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.01 08:35:48" (1/1) ... [2018-01-31 08:35:48,082 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-01-31 08:35:48,087 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-01-31 08:35:48,087 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-01-31 08:35:48,087 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-01-31 08:35:48,088 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.01 08:35:48" (1/1) ... No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-01-31 08:35:48,158 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2018-01-31 08:35:48,158 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-01-31 08:35:48,158 INFO L136 BoogieDeclarations]: Found implementation of procedure substring [2018-01-31 08:35:48,158 INFO L136 BoogieDeclarations]: Found implementation of procedure main [2018-01-31 08:35:48,158 INFO L128 BoogieDeclarations]: Found specification of procedure write~int [2018-01-31 08:35:48,158 INFO L128 BoogieDeclarations]: Found specification of procedure read~int [2018-01-31 08:35:48,159 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.free [2018-01-31 08:35:48,159 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2018-01-31 08:35:48,159 INFO L128 BoogieDeclarations]: Found specification of procedure #Ultimate.alloc [2018-01-31 08:35:48,159 INFO L128 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2018-01-31 08:35:48,159 INFO L128 BoogieDeclarations]: Found specification of procedure substring [2018-01-31 08:35:48,159 INFO L128 BoogieDeclarations]: Found specification of procedure main [2018-01-31 08:35:48,159 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2018-01-31 08:35:48,160 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-01-31 08:35:48,786 INFO L257 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-01-31 08:35:48,787 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 31.01 08:35:48 BoogieIcfgContainer [2018-01-31 08:35:48,787 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-01-31 08:35:48,788 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-01-31 08:35:48,788 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-01-31 08:35:48,791 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-01-31 08:35:48,792 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 31.01 08:35:47" (1/3) ... [2018-01-31 08:35:48,792 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@779e801c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 31.01 08:35:48, skipping insertion in model container [2018-01-31 08:35:48,793 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.01 08:35:48" (2/3) ... [2018-01-31 08:35:48,793 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@779e801c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 31.01 08:35:48, skipping insertion in model container [2018-01-31 08:35:48,793 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 31.01 08:35:48" (3/3) ... [2018-01-31 08:35:48,795 INFO L107 eAbstractionObserver]: Analyzing ICFG substring-alloca_true-valid-memsafety_true-termination.i [2018-01-31 08:35:48,803 INFO L128 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-01-31 08:35:48,809 INFO L140 ceAbstractionStarter]: Appying trace abstraction to program that has 15 error locations. [2018-01-31 08:35:48,864 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-31 08:35:48,864 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-31 08:35:48,864 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-31 08:35:48,864 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-31 08:35:48,865 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-31 08:35:48,865 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-31 08:35:48,865 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-31 08:35:48,865 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-01-31 08:35:48,866 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-31 08:35:48,889 INFO L276 IsEmpty]: Start isEmpty. Operand 92 states. [2018-01-31 08:35:48,899 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2018-01-31 08:35:48,899 INFO L343 BasicCegarLoop]: Found error trace [2018-01-31 08:35:48,900 INFO L351 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-31 08:35:48,900 INFO L371 AbstractCegarLoop]: === Iteration 1 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, substringErr3RequiresViolation, substringErr1RequiresViolation, substringErr7RequiresViolation, substringErr9RequiresViolation, substringErr2RequiresViolation, substringErr8RequiresViolation, substringErr4RequiresViolation, substringErr6RequiresViolation, substringErr0RequiresViolation, substringErr5RequiresViolation]=== [2018-01-31 08:35:48,905 INFO L82 PathProgramCache]: Analyzing trace with hash -997453167, now seen corresponding path program 1 times [2018-01-31 08:35:48,907 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-31 08:35:48,908 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-31 08:35:48,964 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-31 08:35:48,964 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-31 08:35:48,964 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-31 08:35:49,045 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-31 08:35:49,056 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-31 08:35:49,645 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-31 08:35:49,648 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-31 08:35:49,648 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-01-31 08:35:49,652 INFO L409 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-01-31 08:35:49,667 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-01-31 08:35:49,668 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2018-01-31 08:35:49,669 INFO L87 Difference]: Start difference. First operand 92 states. Second operand 6 states. [2018-01-31 08:35:49,962 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-31 08:35:49,962 INFO L93 Difference]: Finished difference Result 154 states and 166 transitions. [2018-01-31 08:35:49,963 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-01-31 08:35:49,964 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 19 [2018-01-31 08:35:49,965 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-31 08:35:49,975 INFO L225 Difference]: With dead ends: 154 [2018-01-31 08:35:49,976 INFO L226 Difference]: Without dead ends: 87 [2018-01-31 08:35:49,980 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=19, Invalid=23, Unknown=0, NotChecked=0, Total=42 [2018-01-31 08:35:49,996 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 87 states. [2018-01-31 08:35:50,015 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 87 to 87. [2018-01-31 08:35:50,017 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 87 states. [2018-01-31 08:35:50,019 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 87 states to 87 states and 92 transitions. [2018-01-31 08:35:50,021 INFO L78 Accepts]: Start accepts. Automaton has 87 states and 92 transitions. Word has length 19 [2018-01-31 08:35:50,024 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-31 08:35:50,024 INFO L432 AbstractCegarLoop]: Abstraction has 87 states and 92 transitions. [2018-01-31 08:35:50,024 INFO L433 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-01-31 08:35:50,024 INFO L276 IsEmpty]: Start isEmpty. Operand 87 states and 92 transitions. [2018-01-31 08:35:50,025 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2018-01-31 08:35:50,025 INFO L343 BasicCegarLoop]: Found error trace [2018-01-31 08:35:50,025 INFO L351 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-31 08:35:50,025 INFO L371 AbstractCegarLoop]: === Iteration 2 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, substringErr3RequiresViolation, substringErr1RequiresViolation, substringErr7RequiresViolation, substringErr9RequiresViolation, substringErr2RequiresViolation, substringErr8RequiresViolation, substringErr4RequiresViolation, substringErr6RequiresViolation, substringErr0RequiresViolation, substringErr5RequiresViolation]=== [2018-01-31 08:35:50,026 INFO L82 PathProgramCache]: Analyzing trace with hash -856277133, now seen corresponding path program 1 times [2018-01-31 08:35:50,026 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-31 08:35:50,026 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-31 08:35:50,027 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-31 08:35:50,027 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-31 08:35:50,028 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-31 08:35:50,044 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-31 08:35:50,045 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-31 08:35:50,111 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-31 08:35:50,111 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-31 08:35:50,111 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-01-31 08:35:50,113 INFO L409 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-01-31 08:35:50,114 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-01-31 08:35:50,114 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-01-31 08:35:50,114 INFO L87 Difference]: Start difference. First operand 87 states and 92 transitions. Second operand 4 states. [2018-01-31 08:35:50,276 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-31 08:35:50,276 INFO L93 Difference]: Finished difference Result 87 states and 92 transitions. [2018-01-31 08:35:50,277 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-01-31 08:35:50,277 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 20 [2018-01-31 08:35:50,277 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-31 08:35:50,278 INFO L225 Difference]: With dead ends: 87 [2018-01-31 08:35:50,278 INFO L226 Difference]: Without dead ends: 86 [2018-01-31 08:35:50,279 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-01-31 08:35:50,280 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 86 states. [2018-01-31 08:35:50,288 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 86 to 86. [2018-01-31 08:35:50,288 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 86 states. [2018-01-31 08:35:50,293 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 86 states to 86 states and 91 transitions. [2018-01-31 08:35:50,293 INFO L78 Accepts]: Start accepts. Automaton has 86 states and 91 transitions. Word has length 20 [2018-01-31 08:35:50,294 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-31 08:35:50,294 INFO L432 AbstractCegarLoop]: Abstraction has 86 states and 91 transitions. [2018-01-31 08:35:50,294 INFO L433 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-01-31 08:35:50,294 INFO L276 IsEmpty]: Start isEmpty. Operand 86 states and 91 transitions. [2018-01-31 08:35:50,294 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2018-01-31 08:35:50,295 INFO L343 BasicCegarLoop]: Found error trace [2018-01-31 08:35:50,295 INFO L351 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-31 08:35:50,295 INFO L371 AbstractCegarLoop]: === Iteration 3 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, substringErr3RequiresViolation, substringErr1RequiresViolation, substringErr7RequiresViolation, substringErr9RequiresViolation, substringErr2RequiresViolation, substringErr8RequiresViolation, substringErr4RequiresViolation, substringErr6RequiresViolation, substringErr0RequiresViolation, substringErr5RequiresViolation]=== [2018-01-31 08:35:50,295 INFO L82 PathProgramCache]: Analyzing trace with hash -856277132, now seen corresponding path program 1 times [2018-01-31 08:35:50,295 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-31 08:35:50,295 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-31 08:35:50,296 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-31 08:35:50,296 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-31 08:35:50,296 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-31 08:35:50,321 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-31 08:35:50,322 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-31 08:35:50,475 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-31 08:35:50,475 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-31 08:35:50,475 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-01-31 08:35:50,476 INFO L409 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-01-31 08:35:50,476 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-01-31 08:35:50,476 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-01-31 08:35:50,476 INFO L87 Difference]: Start difference. First operand 86 states and 91 transitions. Second operand 5 states. [2018-01-31 08:35:50,572 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-31 08:35:50,572 INFO L93 Difference]: Finished difference Result 86 states and 91 transitions. [2018-01-31 08:35:50,573 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-01-31 08:35:50,573 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 20 [2018-01-31 08:35:50,573 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-31 08:35:50,574 INFO L225 Difference]: With dead ends: 86 [2018-01-31 08:35:50,574 INFO L226 Difference]: Without dead ends: 85 [2018-01-31 08:35:50,575 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=14, Invalid=16, Unknown=0, NotChecked=0, Total=30 [2018-01-31 08:35:50,575 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 85 states. [2018-01-31 08:35:50,582 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 85 to 85. [2018-01-31 08:35:50,583 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 85 states. [2018-01-31 08:35:50,585 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 85 states to 85 states and 90 transitions. [2018-01-31 08:35:50,585 INFO L78 Accepts]: Start accepts. Automaton has 85 states and 90 transitions. Word has length 20 [2018-01-31 08:35:50,585 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-31 08:35:50,585 INFO L432 AbstractCegarLoop]: Abstraction has 85 states and 90 transitions. [2018-01-31 08:35:50,585 INFO L433 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-01-31 08:35:50,586 INFO L276 IsEmpty]: Start isEmpty. Operand 85 states and 90 transitions. [2018-01-31 08:35:50,590 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2018-01-31 08:35:50,590 INFO L343 BasicCegarLoop]: Found error trace [2018-01-31 08:35:50,590 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] [2018-01-31 08:35:50,590 INFO L371 AbstractCegarLoop]: === Iteration 4 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, substringErr3RequiresViolation, substringErr1RequiresViolation, substringErr7RequiresViolation, substringErr9RequiresViolation, substringErr2RequiresViolation, substringErr8RequiresViolation, substringErr4RequiresViolation, substringErr6RequiresViolation, substringErr0RequiresViolation, substringErr5RequiresViolation]=== [2018-01-31 08:35:50,590 INFO L82 PathProgramCache]: Analyzing trace with hash -680565440, now seen corresponding path program 1 times [2018-01-31 08:35:50,590 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-31 08:35:50,591 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-31 08:35:50,592 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-31 08:35:50,592 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-31 08:35:50,592 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-31 08:35:50,614 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-31 08:35:50,615 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-31 08:35:50,674 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-31 08:35:50,674 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-31 08:35:50,674 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-01-31 08:35:50,675 INFO L409 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-01-31 08:35:50,675 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-01-31 08:35:50,675 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2018-01-31 08:35:50,675 INFO L87 Difference]: Start difference. First operand 85 states and 90 transitions. Second operand 6 states. [2018-01-31 08:35:51,101 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-31 08:35:51,101 INFO L93 Difference]: Finished difference Result 89 states and 94 transitions. [2018-01-31 08:35:51,101 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-01-31 08:35:51,101 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 26 [2018-01-31 08:35:51,101 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-31 08:35:51,102 INFO L225 Difference]: With dead ends: 89 [2018-01-31 08:35:51,102 INFO L226 Difference]: Without dead ends: 88 [2018-01-31 08:35:51,103 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-01-31 08:35:51,103 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 88 states. [2018-01-31 08:35:51,109 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 88 to 87. [2018-01-31 08:35:51,109 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 87 states. [2018-01-31 08:35:51,111 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 87 states to 87 states and 93 transitions. [2018-01-31 08:35:51,112 INFO L78 Accepts]: Start accepts. Automaton has 87 states and 93 transitions. Word has length 26 [2018-01-31 08:35:51,112 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-31 08:35:51,112 INFO L432 AbstractCegarLoop]: Abstraction has 87 states and 93 transitions. [2018-01-31 08:35:51,112 INFO L433 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-01-31 08:35:51,112 INFO L276 IsEmpty]: Start isEmpty. Operand 87 states and 93 transitions. [2018-01-31 08:35:51,113 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2018-01-31 08:35:51,113 INFO L343 BasicCegarLoop]: Found error trace [2018-01-31 08:35:51,113 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] [2018-01-31 08:35:51,114 INFO L371 AbstractCegarLoop]: === Iteration 5 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, substringErr3RequiresViolation, substringErr1RequiresViolation, substringErr7RequiresViolation, substringErr9RequiresViolation, substringErr2RequiresViolation, substringErr8RequiresViolation, substringErr4RequiresViolation, substringErr6RequiresViolation, substringErr0RequiresViolation, substringErr5RequiresViolation]=== [2018-01-31 08:35:51,114 INFO L82 PathProgramCache]: Analyzing trace with hash -680565439, now seen corresponding path program 1 times [2018-01-31 08:35:51,114 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-31 08:35:51,114 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-31 08:35:51,115 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-31 08:35:51,115 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-31 08:35:51,115 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-31 08:35:51,133 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-31 08:35:51,134 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-31 08:35:51,376 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-31 08:35:51,377 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-31 08:35:51,377 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2018-01-31 08:35:51,377 INFO L409 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-01-31 08:35:51,378 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-01-31 08:35:51,378 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2018-01-31 08:35:51,379 INFO L87 Difference]: Start difference. First operand 87 states and 93 transitions. Second operand 9 states. [2018-01-31 08:35:51,825 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-31 08:35:51,826 INFO L93 Difference]: Finished difference Result 133 states and 142 transitions. [2018-01-31 08:35:51,826 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-01-31 08:35:51,826 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 26 [2018-01-31 08:35:51,827 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-31 08:35:51,830 INFO L225 Difference]: With dead ends: 133 [2018-01-31 08:35:51,831 INFO L226 Difference]: Without dead ends: 132 [2018-01-31 08:35:51,831 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 20 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=45, Invalid=137, Unknown=0, NotChecked=0, Total=182 [2018-01-31 08:35:51,832 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 132 states. [2018-01-31 08:35:51,839 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 132 to 87. [2018-01-31 08:35:51,839 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 87 states. [2018-01-31 08:35:51,840 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 87 states to 87 states and 92 transitions. [2018-01-31 08:35:51,841 INFO L78 Accepts]: Start accepts. Automaton has 87 states and 92 transitions. Word has length 26 [2018-01-31 08:35:51,850 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-31 08:35:51,850 INFO L432 AbstractCegarLoop]: Abstraction has 87 states and 92 transitions. [2018-01-31 08:35:51,850 INFO L433 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-01-31 08:35:51,851 INFO L276 IsEmpty]: Start isEmpty. Operand 87 states and 92 transitions. [2018-01-31 08:35:51,851 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2018-01-31 08:35:51,852 INFO L343 BasicCegarLoop]: Found error trace [2018-01-31 08:35:51,852 INFO L351 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-31 08:35:51,852 INFO L371 AbstractCegarLoop]: === Iteration 6 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, substringErr3RequiresViolation, substringErr1RequiresViolation, substringErr7RequiresViolation, substringErr9RequiresViolation, substringErr2RequiresViolation, substringErr8RequiresViolation, substringErr4RequiresViolation, substringErr6RequiresViolation, substringErr0RequiresViolation, substringErr5RequiresViolation]=== [2018-01-31 08:35:51,852 INFO L82 PathProgramCache]: Analyzing trace with hash -1885696604, now seen corresponding path program 1 times [2018-01-31 08:35:51,852 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-31 08:35:51,852 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-31 08:35:51,853 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-31 08:35:51,854 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-31 08:35:51,854 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-31 08:35:51,889 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-31 08:35:51,890 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-31 08:35:51,982 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-31 08:35:51,982 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-31 08:35:51,983 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-01-31 08:35:51,983 INFO L409 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-01-31 08:35:51,983 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-01-31 08:35:51,983 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2018-01-31 08:35:51,984 INFO L87 Difference]: Start difference. First operand 87 states and 92 transitions. Second operand 6 states. [2018-01-31 08:35:52,297 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-31 08:35:52,297 INFO L93 Difference]: Finished difference Result 99 states and 105 transitions. [2018-01-31 08:35:52,298 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-01-31 08:35:52,298 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 32 [2018-01-31 08:35:52,298 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-31 08:35:52,299 INFO L225 Difference]: With dead ends: 99 [2018-01-31 08:35:52,299 INFO L226 Difference]: Without dead ends: 96 [2018-01-31 08:35:52,300 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-01-31 08:35:52,300 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 96 states. [2018-01-31 08:35:52,308 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 96 to 87. [2018-01-31 08:35:52,309 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 87 states. [2018-01-31 08:35:52,310 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 87 states to 87 states and 93 transitions. [2018-01-31 08:35:52,310 INFO L78 Accepts]: Start accepts. Automaton has 87 states and 93 transitions. Word has length 32 [2018-01-31 08:35:52,310 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-31 08:35:52,310 INFO L432 AbstractCegarLoop]: Abstraction has 87 states and 93 transitions. [2018-01-31 08:35:52,310 INFO L433 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-01-31 08:35:52,311 INFO L276 IsEmpty]: Start isEmpty. Operand 87 states and 93 transitions. [2018-01-31 08:35:52,311 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2018-01-31 08:35:52,312 INFO L343 BasicCegarLoop]: Found error trace [2018-01-31 08:35:52,312 INFO L351 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-31 08:35:52,312 INFO L371 AbstractCegarLoop]: === Iteration 7 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, substringErr3RequiresViolation, substringErr1RequiresViolation, substringErr7RequiresViolation, substringErr9RequiresViolation, substringErr2RequiresViolation, substringErr8RequiresViolation, substringErr4RequiresViolation, substringErr6RequiresViolation, substringErr0RequiresViolation, substringErr5RequiresViolation]=== [2018-01-31 08:35:52,312 INFO L82 PathProgramCache]: Analyzing trace with hash -1885696603, now seen corresponding path program 1 times [2018-01-31 08:35:52,312 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-31 08:35:52,312 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-31 08:35:52,313 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-31 08:35:52,313 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-31 08:35:52,313 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-31 08:35:52,327 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-31 08:35:52,328 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-31 08:35:52,470 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-31 08:35:52,470 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-31 08:35:52,470 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2018-01-31 08:35:52,471 INFO L409 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-01-31 08:35:52,471 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-01-31 08:35:52,471 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=54, Unknown=0, NotChecked=0, Total=72 [2018-01-31 08:35:52,471 INFO L87 Difference]: Start difference. First operand 87 states and 93 transitions. Second operand 9 states. [2018-01-31 08:35:52,671 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-31 08:35:52,671 INFO L93 Difference]: Finished difference Result 128 states and 137 transitions. [2018-01-31 08:35:52,671 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-01-31 08:35:52,671 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 32 [2018-01-31 08:35:52,672 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-31 08:35:52,673 INFO L225 Difference]: With dead ends: 128 [2018-01-31 08:35:52,673 INFO L226 Difference]: Without dead ends: 125 [2018-01-31 08:35:52,674 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 17 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=34, Invalid=98, Unknown=0, NotChecked=0, Total=132 [2018-01-31 08:35:52,674 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 125 states. [2018-01-31 08:35:52,683 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 125 to 98. [2018-01-31 08:35:52,683 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 98 states. [2018-01-31 08:35:52,684 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 98 states to 98 states and 107 transitions. [2018-01-31 08:35:52,685 INFO L78 Accepts]: Start accepts. Automaton has 98 states and 107 transitions. Word has length 32 [2018-01-31 08:35:52,685 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-31 08:35:52,685 INFO L432 AbstractCegarLoop]: Abstraction has 98 states and 107 transitions. [2018-01-31 08:35:52,685 INFO L433 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-01-31 08:35:52,685 INFO L276 IsEmpty]: Start isEmpty. Operand 98 states and 107 transitions. [2018-01-31 08:35:52,686 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2018-01-31 08:35:52,687 INFO L343 BasicCegarLoop]: Found error trace [2018-01-31 08:35:52,687 INFO L351 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-31 08:35:52,687 INFO L371 AbstractCegarLoop]: === Iteration 8 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, substringErr3RequiresViolation, substringErr1RequiresViolation, substringErr7RequiresViolation, substringErr9RequiresViolation, substringErr2RequiresViolation, substringErr8RequiresViolation, substringErr4RequiresViolation, substringErr6RequiresViolation, substringErr0RequiresViolation, substringErr5RequiresViolation]=== [2018-01-31 08:35:52,687 INFO L82 PathProgramCache]: Analyzing trace with hash -22556054, now seen corresponding path program 1 times [2018-01-31 08:35:52,687 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-31 08:35:52,687 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-31 08:35:52,689 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-31 08:35:52,689 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-31 08:35:52,689 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-31 08:35:52,702 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-31 08:35:52,703 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-31 08:35:52,763 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-31 08:35:52,763 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-31 08:35:52,763 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-01-31 08:35:52,763 INFO L409 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-01-31 08:35:52,764 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-01-31 08:35:52,764 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-01-31 08:35:52,764 INFO L87 Difference]: Start difference. First operand 98 states and 107 transitions. Second operand 4 states. [2018-01-31 08:35:52,816 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-31 08:35:52,817 INFO L93 Difference]: Finished difference Result 134 states and 144 transitions. [2018-01-31 08:35:52,817 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-01-31 08:35:52,817 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 36 [2018-01-31 08:35:52,817 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-31 08:35:52,818 INFO L225 Difference]: With dead ends: 134 [2018-01-31 08:35:52,818 INFO L226 Difference]: Without dead ends: 133 [2018-01-31 08:35:52,819 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-01-31 08:35:52,819 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 133 states. [2018-01-31 08:35:52,826 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 133 to 98. [2018-01-31 08:35:52,826 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 98 states. [2018-01-31 08:35:52,827 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 98 states to 98 states and 106 transitions. [2018-01-31 08:35:52,827 INFO L78 Accepts]: Start accepts. Automaton has 98 states and 106 transitions. Word has length 36 [2018-01-31 08:35:52,828 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-31 08:35:52,828 INFO L432 AbstractCegarLoop]: Abstraction has 98 states and 106 transitions. [2018-01-31 08:35:52,828 INFO L433 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-01-31 08:35:52,828 INFO L276 IsEmpty]: Start isEmpty. Operand 98 states and 106 transitions. [2018-01-31 08:35:52,829 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2018-01-31 08:35:52,829 INFO L343 BasicCegarLoop]: Found error trace [2018-01-31 08:35:52,829 INFO L351 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-31 08:35:52,830 INFO L371 AbstractCegarLoop]: === Iteration 9 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, substringErr3RequiresViolation, substringErr1RequiresViolation, substringErr7RequiresViolation, substringErr9RequiresViolation, substringErr2RequiresViolation, substringErr8RequiresViolation, substringErr4RequiresViolation, substringErr6RequiresViolation, substringErr0RequiresViolation, substringErr5RequiresViolation]=== [2018-01-31 08:35:52,830 INFO L82 PathProgramCache]: Analyzing trace with hash -22556053, now seen corresponding path program 1 times [2018-01-31 08:35:52,830 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-31 08:35:52,830 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-31 08:35:52,831 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-31 08:35:52,831 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-31 08:35:52,831 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-31 08:35:52,844 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-31 08:35:52,845 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-31 08:35:52,991 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-31 08:35:52,991 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-31 08:35:52,991 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2018-01-31 08:35:52,992 INFO L409 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-01-31 08:35:52,992 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-01-31 08:35:52,992 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=56, Unknown=0, NotChecked=0, Total=72 [2018-01-31 08:35:52,992 INFO L87 Difference]: Start difference. First operand 98 states and 106 transitions. Second operand 9 states. [2018-01-31 08:35:53,268 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-31 08:35:53,269 INFO L93 Difference]: Finished difference Result 184 states and 200 transitions. [2018-01-31 08:35:53,295 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-01-31 08:35:53,295 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 36 [2018-01-31 08:35:53,295 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-31 08:35:53,296 INFO L225 Difference]: With dead ends: 184 [2018-01-31 08:35:53,296 INFO L226 Difference]: Without dead ends: 183 [2018-01-31 08:35:53,297 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 14 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=55, Invalid=155, Unknown=0, NotChecked=0, Total=210 [2018-01-31 08:35:53,297 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 183 states. [2018-01-31 08:35:53,306 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 183 to 108. [2018-01-31 08:35:53,306 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 108 states. [2018-01-31 08:35:53,307 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 108 states to 108 states and 118 transitions. [2018-01-31 08:35:53,307 INFO L78 Accepts]: Start accepts. Automaton has 108 states and 118 transitions. Word has length 36 [2018-01-31 08:35:53,308 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-31 08:35:53,308 INFO L432 AbstractCegarLoop]: Abstraction has 108 states and 118 transitions. [2018-01-31 08:35:53,308 INFO L433 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-01-31 08:35:53,308 INFO L276 IsEmpty]: Start isEmpty. Operand 108 states and 118 transitions. [2018-01-31 08:35:53,309 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2018-01-31 08:35:53,309 INFO L343 BasicCegarLoop]: Found error trace [2018-01-31 08:35:53,310 INFO L351 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-31 08:35:53,315 INFO L371 AbstractCegarLoop]: === Iteration 10 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, substringErr3RequiresViolation, substringErr1RequiresViolation, substringErr7RequiresViolation, substringErr9RequiresViolation, substringErr2RequiresViolation, substringErr8RequiresViolation, substringErr4RequiresViolation, substringErr6RequiresViolation, substringErr0RequiresViolation, substringErr5RequiresViolation]=== [2018-01-31 08:35:53,316 INFO L82 PathProgramCache]: Analyzing trace with hash 1946131081, now seen corresponding path program 1 times [2018-01-31 08:35:53,316 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-31 08:35:53,316 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-31 08:35:53,317 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-31 08:35:53,317 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-31 08:35:53,317 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-31 08:35:53,337 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-31 08:35:53,338 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-31 08:35:53,541 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-31 08:35:53,542 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-31 08:35:53,542 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-01-31 08:35:53,542 INFO L409 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-01-31 08:35:53,542 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-01-31 08:35:53,542 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2018-01-31 08:35:53,543 INFO L87 Difference]: Start difference. First operand 108 states and 118 transitions. Second operand 6 states. [2018-01-31 08:35:53,856 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-31 08:35:53,856 INFO L93 Difference]: Finished difference Result 108 states and 118 transitions. [2018-01-31 08:35:53,856 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-01-31 08:35:53,857 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 39 [2018-01-31 08:35:53,857 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-31 08:35:53,858 INFO L225 Difference]: With dead ends: 108 [2018-01-31 08:35:53,858 INFO L226 Difference]: Without dead ends: 93 [2018-01-31 08:35:53,858 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2018-01-31 08:35:53,858 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 93 states. [2018-01-31 08:35:53,864 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 93 to 93. [2018-01-31 08:35:53,864 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 93 states. [2018-01-31 08:35:53,864 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 101 transitions. [2018-01-31 08:35:53,864 INFO L78 Accepts]: Start accepts. Automaton has 93 states and 101 transitions. Word has length 39 [2018-01-31 08:35:53,865 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-31 08:35:53,865 INFO L432 AbstractCegarLoop]: Abstraction has 93 states and 101 transitions. [2018-01-31 08:35:53,865 INFO L433 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-01-31 08:35:53,865 INFO L276 IsEmpty]: Start isEmpty. Operand 93 states and 101 transitions. [2018-01-31 08:35:53,866 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2018-01-31 08:35:53,866 INFO L343 BasicCegarLoop]: Found error trace [2018-01-31 08:35:53,866 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-31 08:35:53,866 INFO L371 AbstractCegarLoop]: === Iteration 11 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, substringErr3RequiresViolation, substringErr1RequiresViolation, substringErr7RequiresViolation, substringErr9RequiresViolation, substringErr2RequiresViolation, substringErr8RequiresViolation, substringErr4RequiresViolation, substringErr6RequiresViolation, substringErr0RequiresViolation, substringErr5RequiresViolation]=== [2018-01-31 08:35:53,867 INFO L82 PathProgramCache]: Analyzing trace with hash 1569292953, now seen corresponding path program 1 times [2018-01-31 08:35:53,867 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-31 08:35:53,867 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-31 08:35:53,868 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-31 08:35:53,868 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-31 08:35:53,868 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-31 08:35:53,881 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-31 08:35:53,882 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-31 08:35:53,945 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-31 08:35:53,945 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-31 08:35:53,946 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-01-31 08:35:53,946 INFO L409 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-01-31 08:35:53,946 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-01-31 08:35:53,946 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-31 08:35:53,947 INFO L87 Difference]: Start difference. First operand 93 states and 101 transitions. Second operand 3 states. [2018-01-31 08:35:54,053 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-31 08:35:54,054 INFO L93 Difference]: Finished difference Result 150 states and 165 transitions. [2018-01-31 08:35:54,054 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-01-31 08:35:54,054 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 47 [2018-01-31 08:35:54,054 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-31 08:35:54,055 INFO L225 Difference]: With dead ends: 150 [2018-01-31 08:35:54,055 INFO L226 Difference]: Without dead ends: 95 [2018-01-31 08:35:54,056 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-31 08:35:54,056 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 95 states. [2018-01-31 08:35:54,062 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 95 to 95. [2018-01-31 08:35:54,062 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 95 states. [2018-01-31 08:35:54,063 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 95 states to 95 states and 103 transitions. [2018-01-31 08:35:54,063 INFO L78 Accepts]: Start accepts. Automaton has 95 states and 103 transitions. Word has length 47 [2018-01-31 08:35:54,064 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-31 08:35:54,064 INFO L432 AbstractCegarLoop]: Abstraction has 95 states and 103 transitions. [2018-01-31 08:35:54,064 INFO L433 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-01-31 08:35:54,064 INFO L276 IsEmpty]: Start isEmpty. Operand 95 states and 103 transitions. [2018-01-31 08:35:54,065 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2018-01-31 08:35:54,065 INFO L343 BasicCegarLoop]: Found error trace [2018-01-31 08:35:54,065 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-31 08:35:54,065 INFO L371 AbstractCegarLoop]: === Iteration 12 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, substringErr3RequiresViolation, substringErr1RequiresViolation, substringErr7RequiresViolation, substringErr9RequiresViolation, substringErr2RequiresViolation, substringErr8RequiresViolation, substringErr4RequiresViolation, substringErr6RequiresViolation, substringErr0RequiresViolation, substringErr5RequiresViolation]=== [2018-01-31 08:35:54,066 INFO L82 PathProgramCache]: Analyzing trace with hash -115158054, now seen corresponding path program 1 times [2018-01-31 08:35:54,066 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-31 08:35:54,066 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-31 08:35:54,067 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-31 08:35:54,067 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-31 08:35:54,067 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-31 08:35:54,078 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-31 08:35:54,079 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-31 08:35:54,236 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-31 08:35:54,236 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-31 08:35:54,236 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2018-01-31 08:35:54,236 INFO L409 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-01-31 08:35:54,237 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-01-31 08:35:54,237 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2018-01-31 08:35:54,237 INFO L87 Difference]: Start difference. First operand 95 states and 103 transitions. Second operand 6 states. [2018-01-31 08:35:54,414 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-31 08:35:54,415 INFO L93 Difference]: Finished difference Result 164 states and 177 transitions. [2018-01-31 08:35:54,415 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-01-31 08:35:54,415 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 47 [2018-01-31 08:35:54,416 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-31 08:35:54,416 INFO L225 Difference]: With dead ends: 164 [2018-01-31 08:35:54,416 INFO L226 Difference]: Without dead ends: 100 [2018-01-31 08:35:54,417 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 9 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=25, Invalid=47, Unknown=0, NotChecked=0, Total=72 [2018-01-31 08:35:54,417 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 100 states. [2018-01-31 08:35:54,423 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 100 to 99. [2018-01-31 08:35:54,423 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 99 states. [2018-01-31 08:35:54,424 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 99 states to 99 states and 105 transitions. [2018-01-31 08:35:54,425 INFO L78 Accepts]: Start accepts. Automaton has 99 states and 105 transitions. Word has length 47 [2018-01-31 08:35:54,425 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-31 08:35:54,425 INFO L432 AbstractCegarLoop]: Abstraction has 99 states and 105 transitions. [2018-01-31 08:35:54,425 INFO L433 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-01-31 08:35:54,425 INFO L276 IsEmpty]: Start isEmpty. Operand 99 states and 105 transitions. [2018-01-31 08:35:54,426 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2018-01-31 08:35:54,426 INFO L343 BasicCegarLoop]: Found error trace [2018-01-31 08:35:54,426 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-31 08:35:54,426 INFO L371 AbstractCegarLoop]: === Iteration 13 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, substringErr3RequiresViolation, substringErr1RequiresViolation, substringErr7RequiresViolation, substringErr9RequiresViolation, substringErr2RequiresViolation, substringErr8RequiresViolation, substringErr4RequiresViolation, substringErr6RequiresViolation, substringErr0RequiresViolation, substringErr5RequiresViolation]=== [2018-01-31 08:35:54,427 INFO L82 PathProgramCache]: Analyzing trace with hash 1186334525, now seen corresponding path program 1 times [2018-01-31 08:35:54,427 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-31 08:35:54,427 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-31 08:35:54,428 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-31 08:35:54,428 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-31 08:35:54,428 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-31 08:35:54,440 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-31 08:35:54,440 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-31 08:35:54,533 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-01-31 08:35:54,533 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-31 08:35:54,533 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2018-01-31 08:35:54,533 INFO L409 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-01-31 08:35:54,534 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-01-31 08:35:54,534 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2018-01-31 08:35:54,534 INFO L87 Difference]: Start difference. First operand 99 states and 105 transitions. Second operand 7 states. [2018-01-31 08:35:54,636 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-31 08:35:54,636 INFO L93 Difference]: Finished difference Result 99 states and 105 transitions. [2018-01-31 08:35:54,636 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-01-31 08:35:54,636 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 50 [2018-01-31 08:35:54,637 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-31 08:35:54,637 INFO L225 Difference]: With dead ends: 99 [2018-01-31 08:35:54,638 INFO L226 Difference]: Without dead ends: 98 [2018-01-31 08:35:54,638 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=29, Invalid=61, Unknown=0, NotChecked=0, Total=90 [2018-01-31 08:35:54,638 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 98 states. [2018-01-31 08:35:54,645 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 98 to 98. [2018-01-31 08:35:54,645 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 98 states. [2018-01-31 08:35:54,646 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 98 states to 98 states and 104 transitions. [2018-01-31 08:35:54,647 INFO L78 Accepts]: Start accepts. Automaton has 98 states and 104 transitions. Word has length 50 [2018-01-31 08:35:54,647 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-31 08:35:54,647 INFO L432 AbstractCegarLoop]: Abstraction has 98 states and 104 transitions. [2018-01-31 08:35:54,647 INFO L433 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-01-31 08:35:54,647 INFO L276 IsEmpty]: Start isEmpty. Operand 98 states and 104 transitions. [2018-01-31 08:35:54,648 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2018-01-31 08:35:54,648 INFO L343 BasicCegarLoop]: Found error trace [2018-01-31 08:35:54,648 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-31 08:35:54,648 INFO L371 AbstractCegarLoop]: === Iteration 14 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, substringErr3RequiresViolation, substringErr1RequiresViolation, substringErr7RequiresViolation, substringErr9RequiresViolation, substringErr2RequiresViolation, substringErr8RequiresViolation, substringErr4RequiresViolation, substringErr6RequiresViolation, substringErr0RequiresViolation, substringErr5RequiresViolation]=== [2018-01-31 08:35:54,649 INFO L82 PathProgramCache]: Analyzing trace with hash 1186334526, now seen corresponding path program 1 times [2018-01-31 08:35:54,649 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-31 08:35:54,649 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-31 08:35:54,649 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-31 08:35:54,650 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-31 08:35:54,650 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-31 08:35:54,670 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-31 08:35:54,671 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-31 08:35:55,135 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-31 08:35:55,135 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-31 08:35:55,135 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 2 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-31 08:35:55,142 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-31 08:35:55,180 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-31 08:35:55,192 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-31 08:35:55,266 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 11 [2018-01-31 08:35:55,280 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 10 [2018-01-31 08:35:55,280 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-31 08:35:55,298 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-31 08:35:55,306 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-31 08:35:55,306 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:25, output treesize:21 [2018-01-31 08:35:55,714 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 18 treesize of output 14 [2018-01-31 08:35:55,726 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 14 treesize of output 11 [2018-01-31 08:35:55,727 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-31 08:35:55,730 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-31 08:35:55,769 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: and 2 xjuncts. [2018-01-31 08:35:55,769 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:34, output treesize:33 [2018-01-31 08:35:56,446 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-31 08:35:56,476 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-31 08:35:56,476 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 11] total 21 [2018-01-31 08:35:56,476 INFO L409 AbstractCegarLoop]: Interpolant automaton has 22 states [2018-01-31 08:35:56,477 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2018-01-31 08:35:56,477 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=53, Invalid=409, Unknown=0, NotChecked=0, Total=462 [2018-01-31 08:35:56,477 INFO L87 Difference]: Start difference. First operand 98 states and 104 transitions. Second operand 22 states. [2018-01-31 08:35:58,271 WARN L146 SmtUtils]: Spent 140ms on a formula simplification. DAG size of input: 54 DAG size of output 46 [2018-01-31 08:35:58,901 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-31 08:35:58,901 INFO L93 Difference]: Finished difference Result 165 states and 172 transitions. [2018-01-31 08:35:58,901 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2018-01-31 08:35:58,901 INFO L78 Accepts]: Start accepts. Automaton has 22 states. Word has length 50 [2018-01-31 08:35:58,901 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-31 08:35:58,902 INFO L225 Difference]: With dead ends: 165 [2018-01-31 08:35:58,902 INFO L226 Difference]: Without dead ends: 156 [2018-01-31 08:35:58,903 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 75 GetRequests, 43 SyntacticMatches, 0 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 141 ImplicationChecksByTransitivity, 2.9s TimeCoverageRelationStatistics Valid=188, Invalid=933, Unknown=1, NotChecked=0, Total=1122 [2018-01-31 08:35:58,903 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 156 states. [2018-01-31 08:35:58,917 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 156 to 116. [2018-01-31 08:35:58,917 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 116 states. [2018-01-31 08:35:58,918 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 116 states to 116 states and 125 transitions. [2018-01-31 08:35:58,918 INFO L78 Accepts]: Start accepts. Automaton has 116 states and 125 transitions. Word has length 50 [2018-01-31 08:35:58,919 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-31 08:35:58,919 INFO L432 AbstractCegarLoop]: Abstraction has 116 states and 125 transitions. [2018-01-31 08:35:58,919 INFO L433 AbstractCegarLoop]: Interpolant automaton has 22 states. [2018-01-31 08:35:58,919 INFO L276 IsEmpty]: Start isEmpty. Operand 116 states and 125 transitions. [2018-01-31 08:35:58,920 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2018-01-31 08:35:58,920 INFO L343 BasicCegarLoop]: Found error trace [2018-01-31 08:35:58,920 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-31 08:35:58,920 INFO L371 AbstractCegarLoop]: === Iteration 15 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, substringErr3RequiresViolation, substringErr1RequiresViolation, substringErr7RequiresViolation, substringErr9RequiresViolation, substringErr2RequiresViolation, substringErr8RequiresViolation, substringErr4RequiresViolation, substringErr6RequiresViolation, substringErr0RequiresViolation, substringErr5RequiresViolation]=== [2018-01-31 08:35:58,920 INFO L82 PathProgramCache]: Analyzing trace with hash -498116482, now seen corresponding path program 1 times [2018-01-31 08:35:58,920 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-31 08:35:58,920 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-31 08:35:58,921 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-31 08:35:58,921 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-31 08:35:58,922 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-31 08:35:58,939 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-31 08:35:58,940 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-31 08:35:58,982 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-31 08:35:58,983 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-31 08:35:58,983 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-01-31 08:35:58,983 INFO L409 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-01-31 08:35:58,983 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-01-31 08:35:58,983 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-01-31 08:35:58,984 INFO L87 Difference]: Start difference. First operand 116 states and 125 transitions. Second operand 4 states. [2018-01-31 08:35:59,125 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-31 08:35:59,125 INFO L93 Difference]: Finished difference Result 116 states and 125 transitions. [2018-01-31 08:35:59,126 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-01-31 08:35:59,126 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 50 [2018-01-31 08:35:59,127 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-31 08:35:59,127 INFO L225 Difference]: With dead ends: 116 [2018-01-31 08:35:59,127 INFO L226 Difference]: Without dead ends: 115 [2018-01-31 08:35:59,128 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-01-31 08:35:59,128 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 115 states. [2018-01-31 08:35:59,141 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 115 to 115. [2018-01-31 08:35:59,141 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 115 states. [2018-01-31 08:35:59,142 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 115 states to 115 states and 124 transitions. [2018-01-31 08:35:59,142 INFO L78 Accepts]: Start accepts. Automaton has 115 states and 124 transitions. Word has length 50 [2018-01-31 08:35:59,142 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-31 08:35:59,142 INFO L432 AbstractCegarLoop]: Abstraction has 115 states and 124 transitions. [2018-01-31 08:35:59,142 INFO L433 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-01-31 08:35:59,142 INFO L276 IsEmpty]: Start isEmpty. Operand 115 states and 124 transitions. [2018-01-31 08:35:59,143 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2018-01-31 08:35:59,143 INFO L343 BasicCegarLoop]: Found error trace [2018-01-31 08:35:59,143 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-31 08:35:59,143 INFO L371 AbstractCegarLoop]: === Iteration 16 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, substringErr3RequiresViolation, substringErr1RequiresViolation, substringErr7RequiresViolation, substringErr9RequiresViolation, substringErr2RequiresViolation, substringErr8RequiresViolation, substringErr4RequiresViolation, substringErr6RequiresViolation, substringErr0RequiresViolation, substringErr5RequiresViolation]=== [2018-01-31 08:35:59,143 INFO L82 PathProgramCache]: Analyzing trace with hash -498116481, now seen corresponding path program 1 times [2018-01-31 08:35:59,144 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-31 08:35:59,144 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-31 08:35:59,144 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-31 08:35:59,144 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-31 08:35:59,145 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-31 08:35:59,171 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-31 08:35:59,172 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-31 08:35:59,777 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-31 08:35:59,778 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-31 08:35:59,778 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-31 08:35:59,785 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-31 08:35:59,829 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-31 08:35:59,834 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-31 08:35:59,850 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-31 08:35:59,850 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-31 08:35:59,940 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-31 08:35:59,941 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:13, output treesize:12 [2018-01-31 08:36:00,160 INFO L700 Elim1Store]: detected not equals via solver [2018-01-31 08:36:00,161 INFO L700 Elim1Store]: detected not equals via solver [2018-01-31 08:36:00,163 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 4 [2018-01-31 08:36:00,163 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-31 08:36:00,166 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-31 08:36:00,166 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:17, output treesize:11 [2018-01-31 08:36:00,203 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 11 [2018-01-31 08:36:00,205 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 10 [2018-01-31 08:36:00,205 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-31 08:36:00,206 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-31 08:36:00,213 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-31 08:36:00,213 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:32, output treesize:28 [2018-01-31 08:36:00,242 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 25 treesize of output 26 [2018-01-31 08:36:00,244 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 10 [2018-01-31 08:36:00,245 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-31 08:36:00,249 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-31 08:36:00,257 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 1 xjuncts. [2018-01-31 08:36:00,257 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 5 variables, input treesize:42, output treesize:38 [2018-01-31 08:36:00,513 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 28 treesize of output 26 [2018-01-31 08:36:00,515 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2018-01-31 08:36:00,516 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-31 08:36:00,526 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 1 case distinctions, treesize of input 14 treesize of output 11 [2018-01-31 08:36:00,526 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 2 xjuncts. [2018-01-31 08:36:00,529 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-31 08:36:00,541 INFO L267 ElimStorePlain]: Start of recursive call 1: 5 dim-0 vars, 1 dim-2 vars, End of recursive call: and 2 xjuncts. [2018-01-31 08:36:00,542 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 6 variables, input treesize:51, output treesize:39 [2018-01-31 08:36:00,666 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-31 08:36:00,686 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-31 08:36:00,686 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 16] total 26 [2018-01-31 08:36:00,686 INFO L409 AbstractCegarLoop]: Interpolant automaton has 27 states [2018-01-31 08:36:00,686 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2018-01-31 08:36:00,687 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=69, Invalid=633, Unknown=0, NotChecked=0, Total=702 [2018-01-31 08:36:00,687 INFO L87 Difference]: Start difference. First operand 115 states and 124 transitions. Second operand 27 states. [2018-01-31 08:36:02,634 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-31 08:36:02,634 INFO L93 Difference]: Finished difference Result 264 states and 286 transitions. [2018-01-31 08:36:02,634 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2018-01-31 08:36:02,634 INFO L78 Accepts]: Start accepts. Automaton has 27 states. Word has length 50 [2018-01-31 08:36:02,634 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-31 08:36:02,635 INFO L225 Difference]: With dead ends: 264 [2018-01-31 08:36:02,635 INFO L226 Difference]: Without dead ends: 263 [2018-01-31 08:36:02,637 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 80 GetRequests, 36 SyntacticMatches, 4 SemanticMatches, 40 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 364 ImplicationChecksByTransitivity, 2.6s TimeCoverageRelationStatistics Valid=258, Invalid=1464, Unknown=0, NotChecked=0, Total=1722 [2018-01-31 08:36:02,637 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 263 states. [2018-01-31 08:36:02,654 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 263 to 170. [2018-01-31 08:36:02,654 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 170 states. [2018-01-31 08:36:02,655 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 170 states to 170 states and 190 transitions. [2018-01-31 08:36:02,655 INFO L78 Accepts]: Start accepts. Automaton has 170 states and 190 transitions. Word has length 50 [2018-01-31 08:36:02,656 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-31 08:36:02,656 INFO L432 AbstractCegarLoop]: Abstraction has 170 states and 190 transitions. [2018-01-31 08:36:02,656 INFO L433 AbstractCegarLoop]: Interpolant automaton has 27 states. [2018-01-31 08:36:02,656 INFO L276 IsEmpty]: Start isEmpty. Operand 170 states and 190 transitions. [2018-01-31 08:36:02,657 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2018-01-31 08:36:02,657 INFO L343 BasicCegarLoop]: Found error trace [2018-01-31 08:36:02,657 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-31 08:36:02,657 INFO L371 AbstractCegarLoop]: === Iteration 17 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, substringErr3RequiresViolation, substringErr1RequiresViolation, substringErr7RequiresViolation, substringErr9RequiresViolation, substringErr2RequiresViolation, substringErr8RequiresViolation, substringErr4RequiresViolation, substringErr6RequiresViolation, substringErr0RequiresViolation, substringErr5RequiresViolation]=== [2018-01-31 08:36:02,657 INFO L82 PathProgramCache]: Analyzing trace with hash 1640683395, now seen corresponding path program 1 times [2018-01-31 08:36:02,658 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-31 08:36:02,658 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-31 08:36:02,658 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-31 08:36:02,659 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-31 08:36:02,659 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-31 08:36:02,673 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-31 08:36:02,674 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-31 08:36:02,922 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-01-31 08:36:02,922 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-31 08:36:02,923 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-01-31 08:36:02,923 INFO L409 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-01-31 08:36:02,923 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-01-31 08:36:02,923 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-01-31 08:36:02,923 INFO L87 Difference]: Start difference. First operand 170 states and 190 transitions. Second operand 5 states. [2018-01-31 08:36:03,380 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-31 08:36:03,381 INFO L93 Difference]: Finished difference Result 170 states and 190 transitions. [2018-01-31 08:36:03,381 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-01-31 08:36:03,381 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 54 [2018-01-31 08:36:03,381 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-31 08:36:03,383 INFO L225 Difference]: With dead ends: 170 [2018-01-31 08:36:03,383 INFO L226 Difference]: Without dead ends: 169 [2018-01-31 08:36:03,384 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=17, Invalid=25, Unknown=0, NotChecked=0, Total=42 [2018-01-31 08:36:03,384 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 169 states. [2018-01-31 08:36:03,403 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 169 to 169. [2018-01-31 08:36:03,404 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 169 states. [2018-01-31 08:36:03,405 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 169 states to 169 states and 186 transitions. [2018-01-31 08:36:03,405 INFO L78 Accepts]: Start accepts. Automaton has 169 states and 186 transitions. Word has length 54 [2018-01-31 08:36:03,405 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-31 08:36:03,405 INFO L432 AbstractCegarLoop]: Abstraction has 169 states and 186 transitions. [2018-01-31 08:36:03,405 INFO L433 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-01-31 08:36:03,406 INFO L276 IsEmpty]: Start isEmpty. Operand 169 states and 186 transitions. [2018-01-31 08:36:03,406 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2018-01-31 08:36:03,406 INFO L343 BasicCegarLoop]: Found error trace [2018-01-31 08:36:03,406 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-31 08:36:03,406 INFO L371 AbstractCegarLoop]: === Iteration 18 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, substringErr3RequiresViolation, substringErr1RequiresViolation, substringErr7RequiresViolation, substringErr9RequiresViolation, substringErr2RequiresViolation, substringErr8RequiresViolation, substringErr4RequiresViolation, substringErr6RequiresViolation, substringErr0RequiresViolation, substringErr5RequiresViolation]=== [2018-01-31 08:36:03,407 INFO L82 PathProgramCache]: Analyzing trace with hash 1640683396, now seen corresponding path program 1 times [2018-01-31 08:36:03,407 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-31 08:36:03,407 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-31 08:36:03,408 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-31 08:36:03,408 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-31 08:36:03,408 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-31 08:36:03,423 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-31 08:36:03,424 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-31 08:36:04,095 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-31 08:36:04,096 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-31 08:36:04,106 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-31 08:36:04,113 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-31 08:36:04,134 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-31 08:36:04,138 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-31 08:36:04,158 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-31 08:36:04,158 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-31 08:36:04,227 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-31 08:36:04,227 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:10, output treesize:9 [2018-01-31 08:36:04,392 INFO L700 Elim1Store]: detected not equals via solver [2018-01-31 08:36:04,393 INFO L700 Elim1Store]: detected not equals via solver [2018-01-31 08:36:04,393 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 4 [2018-01-31 08:36:04,394 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-31 08:36:04,398 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-31 08:36:04,398 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:14, output treesize:8 [2018-01-31 08:36:04,438 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 11 [2018-01-31 08:36:04,444 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 10 [2018-01-31 08:36:04,444 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-31 08:36:04,446 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-31 08:36:04,451 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-31 08:36:04,451 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:29, output treesize:25 [2018-01-31 08:36:04,483 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 25 treesize of output 26 [2018-01-31 08:36:04,485 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 10 [2018-01-31 08:36:04,485 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-31 08:36:04,490 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-31 08:36:04,497 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 1 xjuncts. [2018-01-31 08:36:04,497 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 5 variables, input treesize:39, output treesize:35 [2018-01-31 08:36:05,633 WARN L143 SmtUtils]: Spent 609ms on a formula simplification that was a NOOP. DAG size: 42 [2018-01-31 08:36:06,070 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 2 case distinctions, treesize of input 43 treesize of output 53 [2018-01-31 08:36:06,080 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 41 treesize of output 39 [2018-01-31 08:36:06,080 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-31 08:36:06,154 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 0 new quantified variables, introduced 3 case distinctions, treesize of input 33 treesize of output 49 [2018-01-31 08:36:06,155 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 4 xjuncts. [2018-01-31 08:36:06,244 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 27 treesize of output 19 [2018-01-31 08:36:06,245 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-31 08:36:06,256 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 31 treesize of output 23 [2018-01-31 08:36:06,257 INFO L267 ElimStorePlain]: Start of recursive call 6: End of recursive call: and 1 xjuncts. [2018-01-31 08:36:06,326 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 37 treesize of output 29 [2018-01-31 08:36:06,326 INFO L267 ElimStorePlain]: Start of recursive call 7: End of recursive call: and 1 xjuncts. [2018-01-31 08:36:06,404 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 2 disjoint index pairs (out of 3 index pairs), introduced 0 new quantified variables, introduced 2 case distinctions, treesize of input 29 treesize of output 35 [2018-01-31 08:36:06,405 INFO L267 ElimStorePlain]: Start of recursive call 8: End of recursive call: and 4 xjuncts. [2018-01-31 08:36:06,477 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 41 treesize of output 39 [2018-01-31 08:36:06,477 INFO L267 ElimStorePlain]: Start of recursive call 9: End of recursive call: and 2 xjuncts. [2018-01-31 08:36:06,537 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 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 35 treesize of output 28 [2018-01-31 08:36:06,538 INFO L267 ElimStorePlain]: Start of recursive call 10: End of recursive call: and 1 xjuncts. [2018-01-31 08:36:06,539 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 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 31 treesize of output 24 [2018-01-31 08:36:06,540 INFO L267 ElimStorePlain]: Start of recursive call 11: End of recursive call: and 1 xjuncts. [2018-01-31 08:36:06,593 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 24 treesize of output 16 [2018-01-31 08:36:06,594 INFO L267 ElimStorePlain]: Start of recursive call 12: End of recursive call: and 1 xjuncts. [2018-01-31 08:36:06,596 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 28 treesize of output 20 [2018-01-31 08:36:06,596 INFO L267 ElimStorePlain]: Start of recursive call 13: End of recursive call: and 1 xjuncts. [2018-01-31 08:36:06,644 INFO L267 ElimStorePlain]: Start of recursive call 2: 8 dim-1 vars, End of recursive call: and 7 xjuncts. [2018-01-31 08:36:06,705 INFO L267 ElimStorePlain]: Start of recursive call 1: 7 dim-0 vars, 1 dim-2 vars, End of recursive call: and 3 xjuncts. [2018-01-31 08:36:06,705 INFO L202 ElimStorePlain]: Needed 13 recursive calls to eliminate 8 variables, input treesize:63, output treesize:66 [2018-01-31 08:36:06,935 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-31 08:36:06,954 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-31 08:36:06,955 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 21] total 38 [2018-01-31 08:36:06,955 INFO L409 AbstractCegarLoop]: Interpolant automaton has 39 states [2018-01-31 08:36:06,955 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 39 interpolants. [2018-01-31 08:36:06,955 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=103, Invalid=1379, Unknown=0, NotChecked=0, Total=1482 [2018-01-31 08:36:06,956 INFO L87 Difference]: Start difference. First operand 169 states and 186 transitions. Second operand 39 states. [2018-01-31 08:36:07,635 WARN L146 SmtUtils]: Spent 131ms on a formula simplification. DAG size of input: 76 DAG size of output 55 [2018-01-31 08:36:10,164 WARN L146 SmtUtils]: Spent 1663ms on a formula simplification. DAG size of input: 112 DAG size of output 79 [2018-01-31 08:36:10,956 WARN L146 SmtUtils]: Spent 280ms on a formula simplification. DAG size of input: 119 DAG size of output 79 [2018-01-31 08:36:12,633 WARN L146 SmtUtils]: Spent 109ms on a formula simplification. DAG size of input: 133 DAG size of output 85 [2018-01-31 08:36:12,948 WARN L146 SmtUtils]: Spent 104ms on a formula simplification. DAG size of input: 134 DAG size of output 87 [2018-01-31 08:36:16,930 WARN L146 SmtUtils]: Spent 110ms on a formula simplification. DAG size of input: 121 DAG size of output 81 [2018-01-31 08:36:17,676 WARN L146 SmtUtils]: Spent 110ms on a formula simplification. DAG size of input: 103 DAG size of output 75 [2018-01-31 08:36:20,099 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-31 08:36:20,099 INFO L93 Difference]: Finished difference Result 214 states and 226 transitions. [2018-01-31 08:36:20,099 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2018-01-31 08:36:20,099 INFO L78 Accepts]: Start accepts. Automaton has 39 states. Word has length 54 [2018-01-31 08:36:20,099 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-31 08:36:20,100 INFO L225 Difference]: With dead ends: 214 [2018-01-31 08:36:20,101 INFO L226 Difference]: Without dead ends: 213 [2018-01-31 08:36:20,102 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 103 GetRequests, 36 SyntacticMatches, 1 SemanticMatches, 66 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 966 ImplicationChecksByTransitivity, 14.5s TimeCoverageRelationStatistics Valid=661, Invalid=3895, Unknown=0, NotChecked=0, Total=4556 [2018-01-31 08:36:20,102 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 213 states. [2018-01-31 08:36:20,117 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 213 to 169. [2018-01-31 08:36:20,118 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 169 states. [2018-01-31 08:36:20,119 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 169 states to 169 states and 185 transitions. [2018-01-31 08:36:20,119 INFO L78 Accepts]: Start accepts. Automaton has 169 states and 185 transitions. Word has length 54 [2018-01-31 08:36:20,119 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-31 08:36:20,120 INFO L432 AbstractCegarLoop]: Abstraction has 169 states and 185 transitions. [2018-01-31 08:36:20,120 INFO L433 AbstractCegarLoop]: Interpolant automaton has 39 states. [2018-01-31 08:36:20,120 INFO L276 IsEmpty]: Start isEmpty. Operand 169 states and 185 transitions. [2018-01-31 08:36:20,121 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 61 [2018-01-31 08:36:20,121 INFO L343 BasicCegarLoop]: Found error trace [2018-01-31 08:36:20,121 INFO L351 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-31 08:36:20,121 INFO L371 AbstractCegarLoop]: === Iteration 19 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, substringErr3RequiresViolation, substringErr1RequiresViolation, substringErr7RequiresViolation, substringErr9RequiresViolation, substringErr2RequiresViolation, substringErr8RequiresViolation, substringErr4RequiresViolation, substringErr6RequiresViolation, substringErr0RequiresViolation, substringErr5RequiresViolation]=== [2018-01-31 08:36:20,121 INFO L82 PathProgramCache]: Analyzing trace with hash 1675055145, now seen corresponding path program 1 times [2018-01-31 08:36:20,121 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-31 08:36:20,121 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-31 08:36:20,122 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-31 08:36:20,122 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-31 08:36:20,122 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-31 08:36:20,135 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-31 08:36:20,136 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-31 08:36:20,449 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 12 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-31 08:36:20,449 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-31 08:36:20,449 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-31 08:36:20,458 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-31 08:36:20,483 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-31 08:36:20,486 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-31 08:36:20,606 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 5 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-31 08:36:20,625 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-31 08:36:20,625 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 6] total 12 [2018-01-31 08:36:20,626 INFO L409 AbstractCegarLoop]: Interpolant automaton has 13 states [2018-01-31 08:36:20,626 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2018-01-31 08:36:20,626 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=28, Invalid=128, Unknown=0, NotChecked=0, Total=156 [2018-01-31 08:36:20,626 INFO L87 Difference]: Start difference. First operand 169 states and 185 transitions. Second operand 13 states. [2018-01-31 08:36:20,882 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-31 08:36:20,882 INFO L93 Difference]: Finished difference Result 196 states and 207 transitions. [2018-01-31 08:36:20,882 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2018-01-31 08:36:20,882 INFO L78 Accepts]: Start accepts. Automaton has 13 states. Word has length 60 [2018-01-31 08:36:20,883 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-31 08:36:20,883 INFO L225 Difference]: With dead ends: 196 [2018-01-31 08:36:20,883 INFO L226 Difference]: Without dead ends: 195 [2018-01-31 08:36:20,884 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 85 GetRequests, 61 SyntacticMatches, 0 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 65 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=151, Invalid=499, Unknown=0, NotChecked=0, Total=650 [2018-01-31 08:36:20,884 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 195 states. [2018-01-31 08:36:20,897 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 195 to 169. [2018-01-31 08:36:20,897 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 169 states. [2018-01-31 08:36:20,898 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 169 states to 169 states and 184 transitions. [2018-01-31 08:36:20,898 INFO L78 Accepts]: Start accepts. Automaton has 169 states and 184 transitions. Word has length 60 [2018-01-31 08:36:20,898 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-31 08:36:20,898 INFO L432 AbstractCegarLoop]: Abstraction has 169 states and 184 transitions. [2018-01-31 08:36:20,898 INFO L433 AbstractCegarLoop]: Interpolant automaton has 13 states. [2018-01-31 08:36:20,898 INFO L276 IsEmpty]: Start isEmpty. Operand 169 states and 184 transitions. [2018-01-31 08:36:20,899 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 69 [2018-01-31 08:36:20,899 INFO L343 BasicCegarLoop]: Found error trace [2018-01-31 08:36:20,899 INFO L351 BasicCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-31 08:36:20,899 INFO L371 AbstractCegarLoop]: === Iteration 20 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, substringErr3RequiresViolation, substringErr1RequiresViolation, substringErr7RequiresViolation, substringErr9RequiresViolation, substringErr2RequiresViolation, substringErr8RequiresViolation, substringErr4RequiresViolation, substringErr6RequiresViolation, substringErr0RequiresViolation, substringErr5RequiresViolation]=== [2018-01-31 08:36:20,899 INFO L82 PathProgramCache]: Analyzing trace with hash 1682583, now seen corresponding path program 2 times [2018-01-31 08:36:20,899 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-31 08:36:20,899 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-31 08:36:20,900 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-31 08:36:20,900 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-31 08:36:20,900 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-31 08:36:20,923 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-31 08:36:20,924 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-31 08:36:21,373 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 0 proven. 22 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-31 08:36:21,373 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-31 08:36:21,373 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-31 08:36:21,378 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-01-31 08:36:21,396 INFO L201 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-31 08:36:21,404 INFO L214 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-31 08:36:21,407 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-31 08:36:21,411 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-31 08:36:21,490 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 11 [2018-01-31 08:36:21,493 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 10 [2018-01-31 08:36:21,493 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-31 08:36:21,495 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-31 08:36:21,500 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-31 08:36:21,500 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:28, output treesize:24 [2018-01-31 08:36:21,982 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 28 treesize of output 22 [2018-01-31 08:36:21,986 INFO L700 Elim1Store]: detected not equals via solver [2018-01-31 08:36:21,990 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 22 treesize of output 31 [2018-01-31 08:36:21,991 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-31 08:36:22,000 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-31 08:36:22,012 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 2 xjuncts. [2018-01-31 08:36:22,012 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:43, output treesize:43 [2018-01-31 08:36:22,149 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 2 proven. 20 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-31 08:36:22,182 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-31 08:36:22,182 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 18] total 28 [2018-01-31 08:36:22,183 INFO L409 AbstractCegarLoop]: Interpolant automaton has 29 states [2018-01-31 08:36:22,183 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2018-01-31 08:36:22,183 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=67, Invalid=745, Unknown=0, NotChecked=0, Total=812 [2018-01-31 08:36:22,184 INFO L87 Difference]: Start difference. First operand 169 states and 184 transitions. Second operand 29 states. [2018-01-31 08:36:23,361 WARN L146 SmtUtils]: Spent 854ms on a formula simplification. DAG size of input: 45 DAG size of output 43 [2018-01-31 08:36:23,675 WARN L146 SmtUtils]: Spent 269ms on a formula simplification. DAG size of input: 63 DAG size of output 60 [2018-01-31 08:36:23,887 WARN L146 SmtUtils]: Spent 147ms on a formula simplification. DAG size of input: 66 DAG size of output 63 [2018-01-31 08:36:24,198 WARN L146 SmtUtils]: Spent 158ms on a formula simplification. DAG size of input: 73 DAG size of output 70 [2018-01-31 08:36:24,727 WARN L146 SmtUtils]: Spent 491ms on a formula simplification. DAG size of input: 73 DAG size of output 62 [2018-01-31 08:36:26,333 WARN L146 SmtUtils]: Spent 1361ms on a formula simplification. DAG size of input: 66 DAG size of output 58 [2018-01-31 08:36:26,593 WARN L146 SmtUtils]: Spent 212ms on a formula simplification. DAG size of input: 87 DAG size of output 73 [2018-01-31 08:36:27,432 WARN L146 SmtUtils]: Spent 446ms on a formula simplification. DAG size of input: 93 DAG size of output 81 [2018-01-31 08:36:28,248 WARN L146 SmtUtils]: Spent 780ms on a formula simplification. DAG size of input: 72 DAG size of output 66 [2018-01-31 08:36:30,446 WARN L146 SmtUtils]: Spent 2152ms on a formula simplification. DAG size of input: 86 DAG size of output 75 [2018-01-31 08:36:33,682 WARN L146 SmtUtils]: Spent 3187ms on a formula simplification. DAG size of input: 96 DAG size of output 82 [2018-01-31 08:36:35,495 WARN L146 SmtUtils]: Spent 1763ms on a formula simplification. DAG size of input: 83 DAG size of output 67 [2018-01-31 08:36:37,709 WARN L146 SmtUtils]: Spent 1621ms on a formula simplification. DAG size of input: 78 DAG size of output 72 [2018-01-31 08:36:42,598 WARN L146 SmtUtils]: Spent 3125ms on a formula simplification. DAG size of input: 81 DAG size of output 72 [2018-01-31 08:36:45,752 WARN L146 SmtUtils]: Spent 2635ms on a formula simplification. DAG size of input: 76 DAG size of output 70 [2018-01-31 08:36:49,910 WARN L146 SmtUtils]: Spent 3949ms on a formula simplification. DAG size of input: 94 DAG size of output 85 [2018-01-31 08:36:52,317 WARN L146 SmtUtils]: Spent 355ms on a formula simplification. DAG size of input: 85 DAG size of output 77 [2018-01-31 08:36:52,636 WARN L146 SmtUtils]: Spent 288ms on a formula simplification. DAG size of input: 67 DAG size of output 62 [2018-01-31 08:36:55,163 WARN L146 SmtUtils]: Spent 2381ms on a formula simplification. DAG size of input: 83 DAG size of output 65 [2018-01-31 08:36:57,200 WARN L146 SmtUtils]: Spent 1596ms on a formula simplification. DAG size of input: 92 DAG size of output 78 [2018-01-31 08:37:00,813 WARN L146 SmtUtils]: Spent 3559ms on a formula simplification. DAG size of input: 86 DAG size of output 75 [2018-01-31 08:37:02,660 WARN L146 SmtUtils]: Spent 1792ms on a formula simplification. DAG size of input: 87 DAG size of output 76 [2018-01-31 08:37:04,581 WARN L146 SmtUtils]: Spent 1856ms on a formula simplification. DAG size of input: 81 DAG size of output 73 [2018-01-31 08:37:08,278 WARN L146 SmtUtils]: Spent 3647ms on a formula simplification. DAG size of input: 84 DAG size of output 73 [2018-01-31 08:37:09,797 WARN L146 SmtUtils]: Spent 1483ms on a formula simplification. DAG size of input: 79 DAG size of output 71 [2018-01-31 08:37:10,653 WARN L146 SmtUtils]: Spent 795ms on a formula simplification. DAG size of input: 97 DAG size of output 80 [2018-01-31 08:37:12,787 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-31 08:37:12,788 INFO L93 Difference]: Finished difference Result 230 states and 244 transitions. [2018-01-31 08:37:12,788 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 35 states. [2018-01-31 08:37:12,788 INFO L78 Accepts]: Start accepts. Automaton has 29 states. Word has length 68 [2018-01-31 08:37:12,788 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-31 08:37:12,789 INFO L225 Difference]: With dead ends: 230 [2018-01-31 08:37:12,789 INFO L226 Difference]: Without dead ends: 221 [2018-01-31 08:37:12,790 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 114 GetRequests, 54 SyntacticMatches, 1 SemanticMatches, 59 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 568 ImplicationChecksByTransitivity, 45.7s TimeCoverageRelationStatistics Valid=577, Invalid=3080, Unknown=3, NotChecked=0, Total=3660 [2018-01-31 08:37:12,790 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 221 states. [2018-01-31 08:37:12,807 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 221 to 128. [2018-01-31 08:37:12,808 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 128 states. [2018-01-31 08:37:12,809 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 128 states to 128 states and 134 transitions. [2018-01-31 08:37:12,809 INFO L78 Accepts]: Start accepts. Automaton has 128 states and 134 transitions. Word has length 68 [2018-01-31 08:37:12,809 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-31 08:37:12,809 INFO L432 AbstractCegarLoop]: Abstraction has 128 states and 134 transitions. [2018-01-31 08:37:12,809 INFO L433 AbstractCegarLoop]: Interpolant automaton has 29 states. [2018-01-31 08:37:12,809 INFO L276 IsEmpty]: Start isEmpty. Operand 128 states and 134 transitions. [2018-01-31 08:37:12,810 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 73 [2018-01-31 08:37:12,810 INFO L343 BasicCegarLoop]: Found error trace [2018-01-31 08:37:12,810 INFO L351 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-31 08:37:12,810 INFO L371 AbstractCegarLoop]: === Iteration 21 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, substringErr3RequiresViolation, substringErr1RequiresViolation, substringErr7RequiresViolation, substringErr9RequiresViolation, substringErr2RequiresViolation, substringErr8RequiresViolation, substringErr4RequiresViolation, substringErr6RequiresViolation, substringErr0RequiresViolation, substringErr5RequiresViolation]=== [2018-01-31 08:37:12,811 INFO L82 PathProgramCache]: Analyzing trace with hash -876992419, now seen corresponding path program 2 times [2018-01-31 08:37:12,811 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-31 08:37:12,811 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-31 08:37:12,812 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-31 08:37:12,812 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-01-31 08:37:12,812 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-31 08:37:12,828 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-31 08:37:12,830 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-31 08:37:13,447 WARN L146 SmtUtils]: Spent 275ms on a formula simplification. DAG size of input: 23 DAG size of output 17 [2018-01-31 08:37:14,081 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 0 proven. 30 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-31 08:37:14,081 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-31 08:37:14,081 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-31 08:37:14,087 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-01-31 08:37:14,102 INFO L201 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-31 08:37:14,111 INFO L214 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-31 08:37:14,113 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-31 08:37:14,118 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-31 08:37:14,139 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-31 08:37:14,139 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-31 08:37:14,143 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-31 08:37:14,143 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:13, output treesize:12 [2018-01-31 08:37:14,190 INFO L700 Elim1Store]: detected not equals via solver [2018-01-31 08:37:14,191 INFO L700 Elim1Store]: detected not equals via solver [2018-01-31 08:37:14,191 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 4 [2018-01-31 08:37:14,192 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-31 08:37:14,195 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-31 08:37:14,195 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:17, output treesize:11 [2018-01-31 08:37:14,246 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 11 [2018-01-31 08:37:14,248 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 10 [2018-01-31 08:37:14,248 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-31 08:37:14,250 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-31 08:37:14,256 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-31 08:37:14,256 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:32, output treesize:28 [2018-01-31 08:37:14,294 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 25 treesize of output 26 [2018-01-31 08:37:14,296 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 10 [2018-01-31 08:37:14,296 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-31 08:37:14,300 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-31 08:37:14,309 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 1 xjuncts. [2018-01-31 08:37:14,309 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 5 variables, input treesize:42, output treesize:38 [2018-01-31 08:37:15,928 WARN L143 SmtUtils]: Spent 655ms on a formula simplification that was a NOOP. DAG size: 47 [2018-01-31 08:37:16,245 INFO L303 Elim1Store]: Index analysis took 140 ms [2018-01-31 08:37:16,412 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 2 case distinctions, treesize of input 53 treesize of output 61 [2018-01-31 08:37:16,432 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 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 53 treesize of output 46 [2018-01-31 08:37:16,432 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-31 08:37:17,456 INFO L700 Elim1Store]: detected not equals via solver [2018-01-31 08:37:17,469 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 4 select indices, 4 select index equivalence classes, 5 disjoint index pairs (out of 6 index pairs), introduced 1 new quantified variables, introduced 3 case distinctions, treesize of input 45 treesize of output 72 [2018-01-31 08:37:17,471 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 8 xjuncts. [2018-01-31 08:37:17,562 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 43 treesize of output 35 [2018-01-31 08:37:17,563 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-01-31 08:37:17,564 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 40 treesize of output 32 [2018-01-31 08:37:17,565 INFO L267 ElimStorePlain]: Start of recursive call 6: End of recursive call: and 1 xjuncts. [2018-01-31 08:37:17,568 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 44 treesize of output 36 [2018-01-31 08:37:17,568 INFO L267 ElimStorePlain]: Start of recursive call 7: End of recursive call: and 1 xjuncts. [2018-01-31 08:37:17,634 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 45 treesize of output 37 [2018-01-31 08:37:17,634 INFO L267 ElimStorePlain]: Start of recursive call 8: End of recursive call: and 1 xjuncts. [2018-01-31 08:37:17,710 INFO L700 Elim1Store]: detected not equals via solver [2018-01-31 08:37:17,716 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 37 treesize of output 46 [2018-01-31 08:37:17,716 INFO L267 ElimStorePlain]: Start of recursive call 9: End of recursive call: and 2 xjuncts. [2018-01-31 08:37:17,786 INFO L700 Elim1Store]: detected not equals via solver [2018-01-31 08:37:17,791 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 42 treesize of output 51 [2018-01-31 08:37:17,792 INFO L267 ElimStorePlain]: Start of recursive call 10: End of recursive call: and 2 xjuncts. [2018-01-31 08:37:17,920 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 33 treesize of output 25 [2018-01-31 08:37:17,921 INFO L267 ElimStorePlain]: Start of recursive call 11: End of recursive call: and 1 xjuncts. [2018-01-31 08:37:17,922 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 37 treesize of output 29 [2018-01-31 08:37:17,922 INFO L267 ElimStorePlain]: Start of recursive call 12: End of recursive call: and 1 xjuncts. [2018-01-31 08:37:17,978 INFO L267 ElimStorePlain]: Start of recursive call 2: 8 dim-1 vars, End of recursive call: and 7 xjuncts. [2018-01-31 08:37:18,042 INFO L267 ElimStorePlain]: Start of recursive call 1: 6 dim-0 vars, 1 dim-2 vars, End of recursive call: and 3 xjuncts. [2018-01-31 08:37:18,043 INFO L202 ElimStorePlain]: Needed 12 recursive calls to eliminate 7 variables, input treesize:72, output treesize:81 [2018-01-31 08:37:18,287 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 0 proven. 29 refuted. 1 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-31 08:37:18,306 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-31 08:37:18,307 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 25] total 44 [2018-01-31 08:37:18,307 INFO L409 AbstractCegarLoop]: Interpolant automaton has 45 states [2018-01-31 08:37:18,307 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 45 interpolants. [2018-01-31 08:37:18,308 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=112, Invalid=1867, Unknown=1, NotChecked=0, Total=1980 [2018-01-31 08:37:18,308 INFO L87 Difference]: Start difference. First operand 128 states and 134 transitions. Second operand 45 states. [2018-01-31 08:37:19,269 WARN L146 SmtUtils]: Spent 108ms on a formula simplification. DAG size of input: 85 DAG size of output 74 [2018-01-31 08:37:21,802 WARN L146 SmtUtils]: Spent 2117ms on a formula simplification. DAG size of input: 110 DAG size of output 84 [2018-01-31 08:37:22,193 WARN L146 SmtUtils]: Spent 197ms on a formula simplification. DAG size of input: 135 DAG size of output 99 [2018-01-31 08:37:26,491 WARN L146 SmtUtils]: Spent 4020ms on a formula simplification. DAG size of input: 138 DAG size of output 102 [2018-01-31 08:37:28,644 WARN L146 SmtUtils]: Spent 2066ms on a formula simplification. DAG size of input: 85 DAG size of output 69 [2018-01-31 08:37:28,867 WARN L146 SmtUtils]: Spent 122ms on a formula simplification. DAG size of input: 113 DAG size of output 87 [2018-01-31 08:37:29,105 WARN L146 SmtUtils]: Spent 144ms on a formula simplification. DAG size of input: 120 DAG size of output 93 [2018-01-31 08:37:31,407 WARN L146 SmtUtils]: Spent 2171ms on a formula simplification. DAG size of input: 130 DAG size of output 100 [2018-01-31 08:37:33,674 WARN L146 SmtUtils]: Spent 2176ms on a formula simplification. DAG size of input: 130 DAG size of output 96 [2018-01-31 08:37:35,625 WARN L146 SmtUtils]: Spent 1839ms on a formula simplification. DAG size of input: 137 DAG size of output 100 [2018-01-31 08:37:35,955 WARN L146 SmtUtils]: Spent 227ms on a formula simplification. DAG size of input: 151 DAG size of output 106 [2018-01-31 08:37:36,635 WARN L146 SmtUtils]: Spent 537ms on a formula simplification. DAG size of input: 152 DAG size of output 109 [2018-01-31 08:37:37,442 WARN L146 SmtUtils]: Spent 264ms on a formula simplification. DAG size of input: 138 DAG size of output 101 [2018-01-31 08:37:39,782 WARN L146 SmtUtils]: Spent 2234ms on a formula simplification. DAG size of input: 136 DAG size of output 99 [2018-01-31 08:37:40,116 WARN L146 SmtUtils]: Spent 182ms on a formula simplification. DAG size of input: 149 DAG size of output 107 [2018-01-31 08:37:40,424 WARN L146 SmtUtils]: Spent 167ms on a formula simplification. DAG size of input: 120 DAG size of output 96 [2018-01-31 08:37:40,975 WARN L146 SmtUtils]: Spent 223ms on a formula simplification. DAG size of input: 133 DAG size of output 97 [2018-01-31 08:37:43,339 WARN L146 SmtUtils]: Spent 151ms on a formula simplification. DAG size of input: 115 DAG size of output 94 [2018-01-31 08:37:44,143 WARN L146 SmtUtils]: Spent 174ms on a formula simplification. DAG size of input: 122 DAG size of output 93 [2018-01-31 08:37:44,835 WARN L146 SmtUtils]: Spent 244ms on a formula simplification. DAG size of input: 109 DAG size of output 88 [2018-01-31 08:37:45,360 WARN L146 SmtUtils]: Spent 446ms on a formula simplification. DAG size of input: 114 DAG size of output 93 [2018-01-31 08:37:46,128 WARN L146 SmtUtils]: Spent 175ms on a formula simplification. DAG size of input: 97 DAG size of output 78 [2018-01-31 08:37:46,588 WARN L146 SmtUtils]: Spent 111ms on a formula simplification. DAG size of input: 100 DAG size of output 82 [2018-01-31 08:37:46,975 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-31 08:37:46,975 INFO L93 Difference]: Finished difference Result 204 states and 211 transitions. [2018-01-31 08:37:46,975 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 40 states. [2018-01-31 08:37:46,975 INFO L78 Accepts]: Start accepts. Automaton has 45 states. Word has length 72 [2018-01-31 08:37:46,976 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-31 08:37:46,976 INFO L225 Difference]: With dead ends: 204 [2018-01-31 08:37:46,977 INFO L226 Difference]: Without dead ends: 203 [2018-01-31 08:37:46,978 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 130 GetRequests, 49 SyntacticMatches, 1 SemanticMatches, 80 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1135 ImplicationChecksByTransitivity, 29.8s TimeCoverageRelationStatistics Valid=819, Invalid=5821, Unknown=2, NotChecked=0, Total=6642 [2018-01-31 08:37:46,979 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 203 states. [2018-01-31 08:37:46,996 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 203 to 146. [2018-01-31 08:37:46,997 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 146 states. [2018-01-31 08:37:46,998 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 146 states to 146 states and 153 transitions. [2018-01-31 08:37:46,998 INFO L78 Accepts]: Start accepts. Automaton has 146 states and 153 transitions. Word has length 72 [2018-01-31 08:37:46,998 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-31 08:37:46,998 INFO L432 AbstractCegarLoop]: Abstraction has 146 states and 153 transitions. [2018-01-31 08:37:46,998 INFO L433 AbstractCegarLoop]: Interpolant automaton has 45 states. [2018-01-31 08:37:46,998 INFO L276 IsEmpty]: Start isEmpty. Operand 146 states and 153 transitions. [2018-01-31 08:37:46,999 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2018-01-31 08:37:46,999 INFO L343 BasicCegarLoop]: Found error trace [2018-01-31 08:37:46,999 INFO L351 BasicCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-31 08:37:47,000 INFO L371 AbstractCegarLoop]: === Iteration 22 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, substringErr3RequiresViolation, substringErr1RequiresViolation, substringErr7RequiresViolation, substringErr9RequiresViolation, substringErr2RequiresViolation, substringErr8RequiresViolation, substringErr4RequiresViolation, substringErr6RequiresViolation, substringErr0RequiresViolation, substringErr5RequiresViolation]=== [2018-01-31 08:37:47,000 INFO L82 PathProgramCache]: Analyzing trace with hash -587664963, now seen corresponding path program 2 times [2018-01-31 08:37:47,000 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-31 08:37:47,000 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-31 08:37:47,001 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-31 08:37:47,001 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-01-31 08:37:47,001 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-31 08:37:47,025 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-31 08:37:47,027 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-31 08:37:47,523 WARN L146 SmtUtils]: Spent 202ms on a formula simplification. DAG size of input: 19 DAG size of output 12 [2018-01-31 08:37:47,796 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-31 08:37:47,797 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-31 08:37:47,797 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-31 08:37:47,801 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-01-31 08:37:47,814 INFO L201 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-31 08:37:47,823 INFO L214 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-31 08:37:47,826 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-31 08:37:47,829 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-31 08:37:47,839 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-31 08:37:47,840 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-31 08:37:47,845 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-31 08:37:47,845 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-31 08:37:47,848 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-31 08:37:47,849 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:16, output treesize:14 [2018-01-31 08:37:48,184 INFO L700 Elim1Store]: detected not equals via solver [2018-01-31 08:37:48,185 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 15 [2018-01-31 08:37:48,185 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-31 08:37:48,194 INFO L700 Elim1Store]: detected not equals via solver [2018-01-31 08:37:48,194 INFO L700 Elim1Store]: detected not equals via solver [2018-01-31 08:37:48,195 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 4 [2018-01-31 08:37:48,195 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-31 08:37:48,199 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-31 08:37:48,200 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:25, output treesize:18 [2018-01-31 08:37:48,241 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 13 [2018-01-31 08:37:48,243 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 12 [2018-01-31 08:37:48,243 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-31 08:37:48,269 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-31 08:37:48,278 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-31 08:37:48,278 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:32, output treesize:28 [2018-01-31 08:37:48,307 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 29 treesize of output 30 [2018-01-31 08:37:48,310 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 12 [2018-01-31 08:37:48,310 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-31 08:37:48,319 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-31 08:37:48,326 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: 2 dim-0 vars, and 1 xjuncts. [2018-01-31 08:37:48,326 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:39, output treesize:35 [2018-01-31 08:37:48,698 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 32 treesize of output 30 [2018-01-31 08:37:48,737 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 1 case distinctions, treesize of input 16 treesize of output 13 [2018-01-31 08:37:48,737 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-31 08:37:48,744 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 1 [2018-01-31 08:37:48,745 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-31 08:37:48,748 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-31 08:37:48,757 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-2 vars, End of recursive call: and 2 xjuncts. [2018-01-31 08:37:48,758 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 4 variables, input treesize:54, output treesize:49 [2018-01-31 08:37:48,909 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 2 proven. 26 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-31 08:37:48,929 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-31 08:37:48,929 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 31 [2018-01-31 08:37:48,929 INFO L409 AbstractCegarLoop]: Interpolant automaton has 32 states [2018-01-31 08:37:48,929 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2018-01-31 08:37:48,930 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=82, Invalid=910, Unknown=0, NotChecked=0, Total=992 [2018-01-31 08:37:48,930 INFO L87 Difference]: Start difference. First operand 146 states and 153 transitions. Second operand 32 states. [2018-01-31 08:37:49,959 WARN L146 SmtUtils]: Spent 177ms on a formula simplification. DAG size of input: 97 DAG size of output 63 [2018-01-31 08:37:50,228 WARN L146 SmtUtils]: Spent 189ms on a formula simplification. DAG size of input: 98 DAG size of output 65 [2018-01-31 08:37:51,173 WARN L146 SmtUtils]: Spent 112ms on a formula simplification. DAG size of input: 92 DAG size of output 70 [2018-01-31 08:37:51,385 WARN L146 SmtUtils]: Spent 138ms on a formula simplification. DAG size of input: 92 DAG size of output 70 [2018-01-31 08:37:51,638 WARN L146 SmtUtils]: Spent 195ms on a formula simplification. DAG size of input: 76 DAG size of output 57 [2018-01-31 08:37:51,802 WARN L146 SmtUtils]: Spent 111ms on a formula simplification. DAG size of input: 84 DAG size of output 63 [2018-01-31 08:37:52,002 WARN L146 SmtUtils]: Spent 104ms on a formula simplification. DAG size of input: 79 DAG size of output 57 [2018-01-31 08:37:52,979 WARN L146 SmtUtils]: Spent 186ms on a formula simplification. DAG size of input: 90 DAG size of output 68 [2018-01-31 08:37:59,561 WARN L146 SmtUtils]: Spent 105ms on a formula simplification. DAG size of input: 93 DAG size of output 70 [2018-01-31 08:37:59,994 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-31 08:37:59,994 INFO L93 Difference]: Finished difference Result 248 states and 258 transitions. [2018-01-31 08:37:59,997 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 31 states. [2018-01-31 08:37:59,998 INFO L78 Accepts]: Start accepts. Automaton has 32 states. Word has length 74 [2018-01-31 08:37:59,998 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-31 08:37:59,999 INFO L225 Difference]: With dead ends: 248 [2018-01-31 08:37:59,999 INFO L226 Difference]: Without dead ends: 247 [2018-01-31 08:38:00,000 INFO L554 BasicCegarLoop]: 0 DeclaredPredicates, 120 GetRequests, 59 SyntacticMatches, 3 SemanticMatches, 58 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 570 ImplicationChecksByTransitivity, 5.2s TimeCoverageRelationStatistics Valid=478, Invalid=3062, Unknown=0, NotChecked=0, Total=3540 [2018-01-31 08:38:00,001 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 247 states. [2018-01-31 08:38:00,020 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 247 to 109. [2018-01-31 08:38:00,020 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 109 states. [2018-01-31 08:38:00,021 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 109 states to 109 states and 114 transitions. [2018-01-31 08:38:00,021 INFO L78 Accepts]: Start accepts. Automaton has 109 states and 114 transitions. Word has length 74 [2018-01-31 08:38:00,021 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-31 08:38:00,021 INFO L432 AbstractCegarLoop]: Abstraction has 109 states and 114 transitions. [2018-01-31 08:38:00,021 INFO L433 AbstractCegarLoop]: Interpolant automaton has 32 states. [2018-01-31 08:38:00,022 INFO L276 IsEmpty]: Start isEmpty. Operand 109 states and 114 transitions. [2018-01-31 08:38:00,022 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 79 [2018-01-31 08:38:00,022 INFO L343 BasicCegarLoop]: Found error trace [2018-01-31 08:38:00,023 INFO L351 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-31 08:38:00,023 INFO L371 AbstractCegarLoop]: === Iteration 23 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, substringErr3RequiresViolation, substringErr1RequiresViolation, substringErr7RequiresViolation, substringErr9RequiresViolation, substringErr2RequiresViolation, substringErr8RequiresViolation, substringErr4RequiresViolation, substringErr6RequiresViolation, substringErr0RequiresViolation, substringErr5RequiresViolation]=== [2018-01-31 08:38:00,023 INFO L82 PathProgramCache]: Analyzing trace with hash 1332322754, now seen corresponding path program 1 times [2018-01-31 08:38:00,023 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-31 08:38:00,023 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-31 08:38:00,024 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-31 08:38:00,024 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-01-31 08:38:00,025 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-31 08:38:00,038 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-31 08:38:00,039 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-31 08:38:00,944 WARN L146 SmtUtils]: Spent 247ms on a formula simplification. DAG size of input: 18 DAG size of output 16 [2018-01-31 08:38:01,421 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-31 08:38:01,421 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-31 08:38:01,421 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-31 08:38:01,426 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-31 08:38:01,451 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-31 08:38:01,456 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-31 08:38:01,459 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-31 08:38:01,459 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-31 08:38:01,464 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-31 08:38:01,464 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-31 08:38:01,467 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-31 08:38:01,467 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:16, output treesize:14 [2018-01-31 08:38:01,524 INFO L700 Elim1Store]: detected not equals via solver [2018-01-31 08:38:01,525 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 15 [2018-01-31 08:38:01,525 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-31 08:38:01,533 INFO L700 Elim1Store]: detected not equals via solver [2018-01-31 08:38:01,534 INFO L700 Elim1Store]: detected not equals via solver [2018-01-31 08:38:01,534 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 4 [2018-01-31 08:38:01,534 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-31 08:38:01,539 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-31 08:38:01,539 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:25, output treesize:18 [2018-01-31 08:38:01,594 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 13 [2018-01-31 08:38:01,595 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 12 [2018-01-31 08:38:01,596 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-31 08:38:01,597 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-31 08:38:01,603 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-31 08:38:01,603 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:32, output treesize:28 [2018-01-31 08:38:01,641 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 29 treesize of output 30 [2018-01-31 08:38:01,642 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 12 [2018-01-31 08:38:01,642 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-31 08:38:01,646 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-31 08:38:01,653 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-2 vars, End of recursive call: 3 dim-0 vars, and 1 xjuncts. [2018-01-31 08:38:01,653 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:39, output treesize:35 [2018-01-31 08:38:04,391 WARN L143 SmtUtils]: Spent 2028ms on a formula simplification that was a NOOP. DAG size: 42 [2018-01-31 08:38:04,590 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 2 case distinctions, treesize of input 47 treesize of output 57 [2018-01-31 08:38:04,883 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 4 select indices, 4 select index equivalence classes, 3 disjoint index pairs (out of 6 index pairs), introduced 0 new quantified variables, introduced 3 case distinctions, treesize of input 41 treesize of output 61 [2018-01-31 08:38:04,884 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 4 xjuncts. [2018-01-31 08:38:05,791 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 41 treesize of output 31 [2018-01-31 08:38:05,792 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-31 08:38:05,860 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 41 treesize of output 39 [2018-01-31 08:38:05,861 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 2 xjuncts. [2018-01-31 08:38:05,939 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 45 treesize of output 43 [2018-01-31 08:38:05,940 INFO L267 ElimStorePlain]: Start of recursive call 6: End of recursive call: and 2 xjuncts. [2018-01-31 08:38:06,023 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 21 [2018-01-31 08:38:06,024 INFO L267 ElimStorePlain]: Start of recursive call 7: End of recursive call: and 1 xjuncts. [2018-01-31 08:38:06,026 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 35 treesize of output 27 [2018-01-31 08:38:06,027 INFO L267 ElimStorePlain]: Start of recursive call 8: End of recursive call: and 1 xjuncts. [2018-01-31 08:38:06,104 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 33 treesize of output 23 [2018-01-31 08:38:06,104 INFO L267 ElimStorePlain]: Start of recursive call 9: End of recursive call: and 1 xjuncts. [2018-01-31 08:38:06,106 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 39 treesize of output 29 [2018-01-31 08:38:06,106 INFO L267 ElimStorePlain]: Start of recursive call 10: End of recursive call: and 1 xjuncts. [2018-01-31 08:38:06,186 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 2 disjoint index pairs (out of 3 index pairs), introduced 0 new quantified variables, introduced 2 case distinctions, treesize of input 31 treesize of output 39 [2018-01-31 08:38:06,187 INFO L267 ElimStorePlain]: Start of recursive call 11: End of recursive call: and 4 xjuncts. [2018-01-31 08:38:06,251 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 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 23 treesize of output 16 [2018-01-31 08:38:06,251 INFO L267 ElimStorePlain]: Start of recursive call 12: End of recursive call: and 1 xjuncts. [2018-01-31 08:38:06,253 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 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 29 treesize of output 22 [2018-01-31 08:38:06,253 INFO L267 ElimStorePlain]: Start of recursive call 13: End of recursive call: and 1 xjuncts. [2018-01-31 08:38:06,300 INFO L267 ElimStorePlain]: Start of recursive call 2: 8 dim-1 vars, End of recursive call: and 7 xjuncts. [2018-01-31 08:38:06,354 INFO L267 ElimStorePlain]: Start of recursive call 1: 5 dim-0 vars, 1 dim-2 vars, End of recursive call: and 3 xjuncts. [2018-01-31 08:38:06,354 INFO L202 ElimStorePlain]: Needed 13 recursive calls to eliminate 6 variables, input treesize:67, output treesize:78 [2018-01-31 08:38:06,637 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 5 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-31 08:38:06,657 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-31 08:38:06,657 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [23, 24] total 46 [2018-01-31 08:38:06,658 INFO L409 AbstractCegarLoop]: Interpolant automaton has 47 states [2018-01-31 08:38:06,658 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 47 interpolants. [2018-01-31 08:38:06,659 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=125, Invalid=2037, Unknown=0, NotChecked=0, Total=2162 [2018-01-31 08:38:06,659 INFO L87 Difference]: Start difference. First operand 109 states and 114 transitions. Second operand 47 states. [2018-01-31 08:38:08,019 WARN L146 SmtUtils]: Spent 104ms on a formula simplification. DAG size of input: 91 DAG size of output 70 [2018-01-31 08:38:11,613 WARN L146 SmtUtils]: Spent 2096ms on a formula simplification. DAG size of input: 87 DAG size of output 67 [2018-01-31 08:38:11,823 WARN L146 SmtUtils]: Spent 141ms on a formula simplification. DAG size of input: 108 DAG size of output 83 [2018-01-31 08:38:12,084 WARN L146 SmtUtils]: Spent 156ms on a formula simplification. DAG size of input: 101 DAG size of output 77 [2018-01-31 08:38:12,573 WARN L146 SmtUtils]: Spent 123ms on a formula simplification. DAG size of input: 104 DAG size of output 81 [2018-01-31 08:38:12,827 WARN L146 SmtUtils]: Spent 153ms on a formula simplification. DAG size of input: 111 DAG size of output 88 [2018-01-31 08:38:13,255 WARN L146 SmtUtils]: Spent 179ms on a formula simplification. DAG size of input: 113 DAG size of output 90 [2018-01-31 08:38:13,716 WARN L146 SmtUtils]: Spent 371ms on a formula simplification. DAG size of input: 120 DAG size of output 97 [2018-01-31 08:38:14,031 WARN L146 SmtUtils]: Spent 219ms on a formula simplification. DAG size of input: 120 DAG size of output 93 [2018-01-31 08:38:14,352 WARN L146 SmtUtils]: Spent 214ms on a formula simplification. DAG size of input: 127 DAG size of output 101 [2018-01-31 08:38:15,735 WARN L146 SmtUtils]: Spent 1294ms on a formula simplification. DAG size of input: 139 DAG size of output 104 [2018-01-31 08:38:16,171 WARN L146 SmtUtils]: Spent 224ms on a formula simplification. DAG size of input: 140 DAG size of output 106 [2018-01-31 08:38:18,509 WARN L146 SmtUtils]: Spent 2168ms on a formula simplification. DAG size of input: 126 DAG size of output 86 Received shutdown request... [2018-01-31 08:38:18,777 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2018-01-31 08:38:18,777 WARN L491 AbstractCegarLoop]: Verification canceled [2018-01-31 08:38:18,783 WARN L185 ceAbstractionStarter]: Timeout [2018-01-31 08:38:18,783 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 31.01 08:38:18 BoogieIcfgContainer [2018-01-31 08:38:18,783 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-01-31 08:38:18,784 INFO L168 Benchmark]: Toolchain (without parser) took 151071.63 ms. Allocated memory was 307.2 MB in the beginning and 598.7 MB in the end (delta: 291.5 MB). Free memory was 266.0 MB in the beginning and 340.3 MB in the end (delta: -74.3 MB). Peak memory consumption was 217.2 MB. Max. memory is 5.3 GB. [2018-01-31 08:38:18,787 INFO L168 Benchmark]: CDTParser took 0.17 ms. Allocated memory is still 307.2 MB. Free memory is still 271.9 MB. There was no memory consumed. Max. memory is 5.3 GB. [2018-01-31 08:38:18,787 INFO L168 Benchmark]: CACSL2BoogieTranslator took 313.90 ms. Allocated memory is still 307.2 MB. Free memory was 266.0 MB in the beginning and 256.0 MB in the end (delta: 10.0 MB). Peak memory consumption was 10.0 MB. Max. memory is 5.3 GB. [2018-01-31 08:38:18,788 INFO L168 Benchmark]: Boogie Preprocessor took 43.87 ms. Allocated memory is still 307.2 MB. Free memory was 256.0 MB in the beginning and 254.0 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 5.3 GB. [2018-01-31 08:38:18,788 INFO L168 Benchmark]: RCFGBuilder took 700.06 ms. Allocated memory is still 307.2 MB. Free memory was 254.0 MB in the beginning and 231.1 MB in the end (delta: 22.9 MB). Peak memory consumption was 22.9 MB. Max. memory is 5.3 GB. [2018-01-31 08:38:18,788 INFO L168 Benchmark]: TraceAbstraction took 149995.07 ms. Allocated memory was 307.2 MB in the beginning and 598.7 MB in the end (delta: 291.5 MB). Free memory was 231.1 MB in the beginning and 340.3 MB in the end (delta: -109.2 MB). Peak memory consumption was 182.3 MB. Max. memory is 5.3 GB. [2018-01-31 08:38:18,790 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.17 ms. Allocated memory is still 307.2 MB. Free memory is still 271.9 MB. There was no memory consumed. Max. memory is 5.3 GB. * CACSL2BoogieTranslator took 313.90 ms. Allocated memory is still 307.2 MB. Free memory was 266.0 MB in the beginning and 256.0 MB in the end (delta: 10.0 MB). Peak memory consumption was 10.0 MB. Max. memory is 5.3 GB. * Boogie Preprocessor took 43.87 ms. Allocated memory is still 307.2 MB. Free memory was 256.0 MB in the beginning and 254.0 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 5.3 GB. * RCFGBuilder took 700.06 ms. Allocated memory is still 307.2 MB. Free memory was 254.0 MB in the beginning and 231.1 MB in the end (delta: 22.9 MB). Peak memory consumption was 22.9 MB. Max. memory is 5.3 GB. * TraceAbstraction took 149995.07 ms. Allocated memory was 307.2 MB in the beginning and 598.7 MB in the end (delta: 291.5 MB). Free memory was 231.1 MB in the beginning and 340.3 MB in the end (delta: -109.2 MB). Peak memory consumption was 182.3 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 567). Cancelled while BasicCegarLoop was constructing difference of abstraction (109states) and interpolant automaton (currently 30 states, 47 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 124. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 566). Cancelled while BasicCegarLoop was constructing difference of abstraction (109states) and interpolant automaton (currently 30 states, 47 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 124. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 567). Cancelled while BasicCegarLoop was constructing difference of abstraction (109states) and interpolant automaton (currently 30 states, 47 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 124. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 566). Cancelled while BasicCegarLoop was constructing difference of abstraction (109states) and interpolant automaton (currently 30 states, 47 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 124. - TimeoutResultAtElement [Line: 555]: Timeout (TraceAbstraction) Unable to prove that all allocated memory was freed (line 555). Cancelled while BasicCegarLoop was constructing difference of abstraction (109states) and interpolant automaton (currently 30 states, 47 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 124. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 546). Cancelled while BasicCegarLoop was constructing difference of abstraction (109states) and interpolant automaton (currently 30 states, 47 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 124. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 543). Cancelled while BasicCegarLoop was constructing difference of abstraction (109states) and interpolant automaton (currently 30 states, 47 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 124. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 546). Cancelled while BasicCegarLoop was constructing difference of abstraction (109states) and interpolant automaton (currently 30 states, 47 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 124. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 550). Cancelled while BasicCegarLoop was constructing difference of abstraction (109states) and interpolant automaton (currently 30 states, 47 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 124. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 546). Cancelled while BasicCegarLoop was constructing difference of abstraction (109states) and interpolant automaton (currently 30 states, 47 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 124. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 550). Cancelled while BasicCegarLoop was constructing difference of abstraction (109states) and interpolant automaton (currently 30 states, 47 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 124. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 546). Cancelled while BasicCegarLoop was constructing difference of abstraction (109states) and interpolant automaton (currently 30 states, 47 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 124. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 546). Cancelled while BasicCegarLoop was constructing difference of abstraction (109states) and interpolant automaton (currently 30 states, 47 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 124. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 543). Cancelled while BasicCegarLoop was constructing difference of abstraction (109states) and interpolant automaton (currently 30 states, 47 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 124. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 546). Cancelled while BasicCegarLoop was constructing difference of abstraction (109states) and interpolant automaton (currently 30 states, 47 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 124. - StatisticsResult: Ultimate Automizer benchmark data CFG has 4 procedures, 92 locations, 15 error locations. TIMEOUT Result, 149.9s OverallTime, 23 OverallIterations, 3 TraceHistogramMax, 123.9s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 1774 SDtfs, 8199 SDslu, 12330 SDs, 0 SdLazy, 6462 SolverSat, 331 SolverUnsat, 8 SolverUnknown, 0 SolverNotchecked, 19.8s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 950 GetRequests, 414 SyntacticMatches, 12 SemanticMatches, 523 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4706 ImplicationChecksByTransitivity, 119.1s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=170occurred 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.2s AutomataMinimizationTime, 22 MinimizatonAttempts, 684 StatesRemovedByMinimization, 14 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.1s SsaConstructionTime, 0.5s SatisfiabilityAnalysisTime, 24.3s InterpolantComputationTime, 1546 NumberOfCodeBlocks, 1546 NumberOfCodeBlocksAsserted, 34 NumberOfCheckSat, 1515 ConstructedInterpolants, 172 QuantifiedInterpolants, 1130299 SizeOfPredicates, 163 NumberOfNonLiveVariables, 1538 ConjunctsInSsa, 329 ConjunctsInUnsatCore, 31 InterpolantComputations, 15 PerfectInterpolantSequences, 28/270 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, ReuseStatistics: No data available RESULT: Ultimate could not prove your program: Timeout Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/substring-alloca_true-valid-memsafety_true-termination.i_svcomp-DerefFreeMemtrack-32bit-Automizer_Camel+AI_EQ_SS.epf_AutomizerC.xml/Csv-Benchmark-0-2018-01-31_08-38-18-798.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/substring-alloca_true-valid-memsafety_true-termination.i_svcomp-DerefFreeMemtrack-32bit-Automizer_Camel+AI_EQ_SS.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-0-2018-01-31_08-38-18-798.csv Completed graceful shutdown