/usr/bin/java -Xmx8000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata ./data -tc config/AutomizerReach.xml -s config/svcomp-Reach-64bit-Automizer_Default.epf -i ../sv-benchmarks/c/loops-crafted-1/nested_delay_nd.c -------------------------------------------------------------------------------- This is Ultimate 0.2.1-bitabs-dcfa08f [2020-12-23 07:10:31,809 INFO L177 SettingsManager]: Resetting all preferences to default values... [2020-12-23 07:10:31,813 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2020-12-23 07:10:31,849 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2020-12-23 07:10:31,850 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2020-12-23 07:10:31,852 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2020-12-23 07:10:31,853 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2020-12-23 07:10:31,856 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2020-12-23 07:10:31,859 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2020-12-23 07:10:31,860 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2020-12-23 07:10:31,861 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2020-12-23 07:10:31,863 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2020-12-23 07:10:31,864 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2020-12-23 07:10:31,865 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2020-12-23 07:10:31,866 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2020-12-23 07:10:31,868 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2020-12-23 07:10:31,879 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2020-12-23 07:10:31,881 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2020-12-23 07:10:31,883 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2020-12-23 07:10:31,886 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2020-12-23 07:10:31,888 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2020-12-23 07:10:31,889 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2020-12-23 07:10:31,891 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2020-12-23 07:10:31,892 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2020-12-23 07:10:31,895 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2020-12-23 07:10:31,896 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2020-12-23 07:10:31,896 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2020-12-23 07:10:31,897 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2020-12-23 07:10:31,898 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2020-12-23 07:10:31,903 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2020-12-23 07:10:31,903 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2020-12-23 07:10:31,907 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2020-12-23 07:10:31,909 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2020-12-23 07:10:31,912 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2020-12-23 07:10:31,914 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2020-12-23 07:10:31,914 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2020-12-23 07:10:31,918 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2020-12-23 07:10:31,918 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2020-12-23 07:10:31,918 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2020-12-23 07:10:31,919 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2020-12-23 07:10:31,921 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2020-12-23 07:10:31,922 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate-bitabs/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-64bit-Automizer_Default.epf [2020-12-23 07:10:31,982 INFO L113 SettingsManager]: Loading preferences was successful [2020-12-23 07:10:31,983 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2020-12-23 07:10:31,985 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2020-12-23 07:10:31,985 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2020-12-23 07:10:31,986 INFO L138 SettingsManager]: * Use SBE=true [2020-12-23 07:10:31,988 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2020-12-23 07:10:31,988 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2020-12-23 07:10:31,989 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2020-12-23 07:10:31,989 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2020-12-23 07:10:31,989 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2020-12-23 07:10:31,991 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2020-12-23 07:10:31,991 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2020-12-23 07:10:31,991 INFO L138 SettingsManager]: * Use constant arrays=true [2020-12-23 07:10:31,992 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2020-12-23 07:10:31,992 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2020-12-23 07:10:31,992 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2020-12-23 07:10:31,993 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2020-12-23 07:10:31,993 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2020-12-23 07:10:31,993 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2020-12-23 07:10:31,993 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2020-12-23 07:10:31,994 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2020-12-23 07:10:31,994 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2020-12-23 07:10:31,994 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2020-12-23 07:10:31,995 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2020-12-23 07:10:31,995 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2020-12-23 07:10:31,995 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate-bitabs/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release [2020-12-23 07:10:32,418 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2020-12-23 07:10:32,448 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2020-12-23 07:10:32,451 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2020-12-23 07:10:32,453 INFO L271 PluginConnector]: Initializing CDTParser... [2020-12-23 07:10:32,453 INFO L275 PluginConnector]: CDTParser initialized [2020-12-23 07:10:32,455 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate-bitabs/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/loops-crafted-1/nested_delay_nd.c [2020-12-23 07:10:32,546 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate-bitabs/releaseScripts/default/UAutomizer-linux/data/0de0aca9c/e94fe13fdd3a4f13bc7ea7962173f74d/FLAG676f3e464 [2020-12-23 07:10:33,085 INFO L306 CDTParser]: Found 1 translation units. [2020-12-23 07:10:33,086 INFO L160 CDTParser]: Scanning /storage/repos/ultimate-bitabs/releaseScripts/default/sv-benchmarks/c/loops-crafted-1/nested_delay_nd.c [2020-12-23 07:10:33,093 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate-bitabs/releaseScripts/default/UAutomizer-linux/data/0de0aca9c/e94fe13fdd3a4f13bc7ea7962173f74d/FLAG676f3e464 [2020-12-23 07:10:33,445 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate-bitabs/releaseScripts/default/UAutomizer-linux/data/0de0aca9c/e94fe13fdd3a4f13bc7ea7962173f74d [2020-12-23 07:10:33,454 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2020-12-23 07:10:33,457 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2020-12-23 07:10:33,461 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2020-12-23 07:10:33,461 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2020-12-23 07:10:33,465 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2020-12-23 07:10:33,466 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 23.12 07:10:33" (1/1) ... [2020-12-23 07:10:33,469 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@4557f0e1 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.12 07:10:33, skipping insertion in model container [2020-12-23 07:10:33,469 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 23.12 07:10:33" (1/1) ... [2020-12-23 07:10:33,479 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2020-12-23 07:10:33,498 INFO L178 MainTranslator]: Built tables and reachable declarations [2020-12-23 07:10:33,646 WARN L226 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate-bitabs/releaseScripts/default/sv-benchmarks/c/loops-crafted-1/nested_delay_nd.c[465,478] left hand side expression in assignment: lhs: VariableLHS[~last~0,GLOBAL] left hand side expression in assignment: lhs: VariableLHS[~st~0,] left hand side expression in assignment: lhs: VariableLHS[~c~0,] left hand side expression in assignment: lhs: VariableLHS[~st~0,] left hand side expression in assignment: lhs: VariableLHS[~a~0,] left hand side expression in assignment: lhs: VariableLHS[~a~0,] left hand side expression in assignment: lhs: VariableLHS[~b~0,] [2020-12-23 07:10:33,666 INFO L206 PostProcessor]: Analyzing one entry point: main [2020-12-23 07:10:33,677 INFO L203 MainTranslator]: Completed pre-run [2020-12-23 07:10:33,693 WARN L226 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate-bitabs/releaseScripts/default/sv-benchmarks/c/loops-crafted-1/nested_delay_nd.c[465,478] left hand side expression in assignment: lhs: VariableLHS[~last~0,GLOBAL] left hand side expression in assignment: lhs: VariableLHS[~st~0,] left hand side expression in assignment: lhs: VariableLHS[~c~0,] left hand side expression in assignment: lhs: VariableLHS[~st~0,] left hand side expression in assignment: lhs: VariableLHS[~a~0,] left hand side expression in assignment: lhs: VariableLHS[~a~0,] left hand side expression in assignment: lhs: VariableLHS[~b~0,] [2020-12-23 07:10:33,700 INFO L206 PostProcessor]: Analyzing one entry point: main [2020-12-23 07:10:33,718 INFO L208 MainTranslator]: Completed translation [2020-12-23 07:10:33,718 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.12 07:10:33 WrapperNode [2020-12-23 07:10:33,719 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2020-12-23 07:10:33,720 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2020-12-23 07:10:33,720 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2020-12-23 07:10:33,720 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2020-12-23 07:10:33,729 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.12 07:10:33" (1/1) ... [2020-12-23 07:10:33,738 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.12 07:10:33" (1/1) ... [2020-12-23 07:10:33,760 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2020-12-23 07:10:33,761 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2020-12-23 07:10:33,762 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2020-12-23 07:10:33,762 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2020-12-23 07:10:33,771 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.12 07:10:33" (1/1) ... [2020-12-23 07:10:33,772 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.12 07:10:33" (1/1) ... [2020-12-23 07:10:33,773 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.12 07:10:33" (1/1) ... [2020-12-23 07:10:33,774 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.12 07:10:33" (1/1) ... [2020-12-23 07:10:33,778 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.12 07:10:33" (1/1) ... [2020-12-23 07:10:33,782 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.12 07:10:33" (1/1) ... [2020-12-23 07:10:33,784 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.12 07:10:33" (1/1) ... [2020-12-23 07:10:33,786 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2020-12-23 07:10:33,787 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2020-12-23 07:10:33,787 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2020-12-23 07:10:33,787 INFO L275 PluginConnector]: RCFGBuilder initialized [2020-12-23 07:10:33,788 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.12 07:10:33" (1/1) ... No working directory specified, using /storage/repos/ultimate-bitabs/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 [2020-12-23 07:10:33,894 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2020-12-23 07:10:33,894 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2020-12-23 07:10:33,894 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2020-12-23 07:10:33,894 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2020-12-23 07:10:34,367 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2020-12-23 07:10:34,371 INFO L299 CfgBuilder]: Removed 10 assume(true) statements. [2020-12-23 07:10:34,373 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 23.12 07:10:34 BoogieIcfgContainer [2020-12-23 07:10:34,373 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2020-12-23 07:10:34,375 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2020-12-23 07:10:34,375 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2020-12-23 07:10:34,384 INFO L275 PluginConnector]: TraceAbstraction initialized [2020-12-23 07:10:34,384 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 23.12 07:10:33" (1/3) ... [2020-12-23 07:10:34,388 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4c203d69 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 23.12 07:10:34, skipping insertion in model container [2020-12-23 07:10:34,389 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.12 07:10:33" (2/3) ... [2020-12-23 07:10:34,389 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4c203d69 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 23.12 07:10:34, skipping insertion in model container [2020-12-23 07:10:34,389 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 23.12 07:10:34" (3/3) ... [2020-12-23 07:10:34,391 INFO L111 eAbstractionObserver]: Analyzing ICFG nested_delay_nd.c [2020-12-23 07:10:34,404 INFO L153 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2020-12-23 07:10:34,409 INFO L165 ceAbstractionStarter]: Appying trace abstraction to program that has 1 error locations. [2020-12-23 07:10:34,433 INFO L253 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2020-12-23 07:10:34,480 INFO L377 AbstractCegarLoop]: Interprodecural is true [2020-12-23 07:10:34,480 INFO L378 AbstractCegarLoop]: Hoare is true [2020-12-23 07:10:34,480 INFO L379 AbstractCegarLoop]: Compute interpolants for FPandBP [2020-12-23 07:10:34,480 INFO L380 AbstractCegarLoop]: Backedges is STRAIGHT_LINE [2020-12-23 07:10:34,482 INFO L381 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2020-12-23 07:10:34,482 INFO L382 AbstractCegarLoop]: Difference is false [2020-12-23 07:10:34,483 INFO L383 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2020-12-23 07:10:34,483 INFO L387 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2020-12-23 07:10:34,500 INFO L276 IsEmpty]: Start isEmpty. Operand 20 states. [2020-12-23 07:10:34,511 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2020-12-23 07:10:34,511 INFO L414 BasicCegarLoop]: Found error trace [2020-12-23 07:10:34,512 INFO L422 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2020-12-23 07:10:34,512 INFO L429 AbstractCegarLoop]: === Iteration 1 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-12-23 07:10:34,519 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-12-23 07:10:34,520 INFO L82 PathProgramCache]: Analyzing trace with hash -493598204, now seen corresponding path program 1 times [2020-12-23 07:10:34,531 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-12-23 07:10:34,532 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [282234168] [2020-12-23 07:10:34,533 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-12-23 07:10:34,699 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-12-23 07:10:34,785 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2020-12-23 07:10:34,786 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [282234168] [2020-12-23 07:10:34,788 INFO L219 FreeRefinementEngine]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2020-12-23 07:10:34,788 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2020-12-23 07:10:34,789 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2115148853] [2020-12-23 07:10:34,796 INFO L461 AbstractCegarLoop]: Interpolant automaton has 2 states [2020-12-23 07:10:34,796 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-12-23 07:10:34,816 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2020-12-23 07:10:34,818 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2020-12-23 07:10:34,821 INFO L87 Difference]: Start difference. First operand 20 states. Second operand 2 states. [2020-12-23 07:10:34,845 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-12-23 07:10:34,846 INFO L93 Difference]: Finished difference Result 33 states and 53 transitions. [2020-12-23 07:10:34,846 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2020-12-23 07:10:34,847 INFO L78 Accepts]: Start accepts. Automaton has 2 states. Word has length 12 [2020-12-23 07:10:34,848 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-12-23 07:10:34,868 INFO L225 Difference]: With dead ends: 33 [2020-12-23 07:10:34,872 INFO L226 Difference]: Without dead ends: 16 [2020-12-23 07:10:34,875 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2020-12-23 07:10:34,898 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 16 states. [2020-12-23 07:10:34,918 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 16 to 16. [2020-12-23 07:10:34,920 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 16 states. [2020-12-23 07:10:34,922 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 16 states to 16 states and 22 transitions. [2020-12-23 07:10:34,924 INFO L78 Accepts]: Start accepts. Automaton has 16 states and 22 transitions. Word has length 12 [2020-12-23 07:10:34,925 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-12-23 07:10:34,925 INFO L481 AbstractCegarLoop]: Abstraction has 16 states and 22 transitions. [2020-12-23 07:10:34,925 INFO L482 AbstractCegarLoop]: Interpolant automaton has 2 states. [2020-12-23 07:10:34,925 INFO L276 IsEmpty]: Start isEmpty. Operand 16 states and 22 transitions. [2020-12-23 07:10:34,926 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2020-12-23 07:10:34,926 INFO L414 BasicCegarLoop]: Found error trace [2020-12-23 07:10:34,926 INFO L422 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2020-12-23 07:10:34,928 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2020-12-23 07:10:34,928 INFO L429 AbstractCegarLoop]: === Iteration 2 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-12-23 07:10:34,930 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-12-23 07:10:34,931 INFO L82 PathProgramCache]: Analyzing trace with hash -2059231113, now seen corresponding path program 1 times [2020-12-23 07:10:34,932 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-12-23 07:10:34,932 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1913715044] [2020-12-23 07:10:34,933 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-12-23 07:10:34,973 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-12-23 07:10:35,070 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2020-12-23 07:10:35,071 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1913715044] [2020-12-23 07:10:35,071 INFO L219 FreeRefinementEngine]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2020-12-23 07:10:35,071 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2020-12-23 07:10:35,072 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [324902762] [2020-12-23 07:10:35,075 INFO L461 AbstractCegarLoop]: Interpolant automaton has 4 states [2020-12-23 07:10:35,076 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-12-23 07:10:35,080 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2020-12-23 07:10:35,081 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2020-12-23 07:10:35,081 INFO L87 Difference]: Start difference. First operand 16 states and 22 transitions. Second operand 4 states. [2020-12-23 07:10:35,170 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-12-23 07:10:35,170 INFO L93 Difference]: Finished difference Result 32 states and 46 transitions. [2020-12-23 07:10:35,171 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2020-12-23 07:10:35,171 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 12 [2020-12-23 07:10:35,171 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-12-23 07:10:35,172 INFO L225 Difference]: With dead ends: 32 [2020-12-23 07:10:35,172 INFO L226 Difference]: Without dead ends: 20 [2020-12-23 07:10:35,173 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2020-12-23 07:10:35,174 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 20 states. [2020-12-23 07:10:35,177 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 20 to 17. [2020-12-23 07:10:35,178 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 17 states. [2020-12-23 07:10:35,179 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 17 states to 17 states and 23 transitions. [2020-12-23 07:10:35,179 INFO L78 Accepts]: Start accepts. Automaton has 17 states and 23 transitions. Word has length 12 [2020-12-23 07:10:35,179 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-12-23 07:10:35,179 INFO L481 AbstractCegarLoop]: Abstraction has 17 states and 23 transitions. [2020-12-23 07:10:35,179 INFO L482 AbstractCegarLoop]: Interpolant automaton has 4 states. [2020-12-23 07:10:35,180 INFO L276 IsEmpty]: Start isEmpty. Operand 17 states and 23 transitions. [2020-12-23 07:10:35,180 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2020-12-23 07:10:35,180 INFO L414 BasicCegarLoop]: Found error trace [2020-12-23 07:10:35,180 INFO L422 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2020-12-23 07:10:35,181 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2020-12-23 07:10:35,181 INFO L429 AbstractCegarLoop]: === Iteration 3 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-12-23 07:10:35,182 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-12-23 07:10:35,182 INFO L82 PathProgramCache]: Analyzing trace with hash 573171571, now seen corresponding path program 1 times [2020-12-23 07:10:35,182 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-12-23 07:10:35,182 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1170997189] [2020-12-23 07:10:35,183 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-12-23 07:10:35,204 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-12-23 07:10:35,236 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2020-12-23 07:10:35,237 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1170997189] [2020-12-23 07:10:35,237 INFO L219 FreeRefinementEngine]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2020-12-23 07:10:35,237 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2020-12-23 07:10:35,238 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1892651731] [2020-12-23 07:10:35,238 INFO L461 AbstractCegarLoop]: Interpolant automaton has 3 states [2020-12-23 07:10:35,239 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-12-23 07:10:35,239 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2020-12-23 07:10:35,239 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2020-12-23 07:10:35,240 INFO L87 Difference]: Start difference. First operand 17 states and 23 transitions. Second operand 3 states. [2020-12-23 07:10:35,300 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-12-23 07:10:35,300 INFO L93 Difference]: Finished difference Result 38 states and 53 transitions. [2020-12-23 07:10:35,301 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2020-12-23 07:10:35,301 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 15 [2020-12-23 07:10:35,302 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-12-23 07:10:35,302 INFO L225 Difference]: With dead ends: 38 [2020-12-23 07:10:35,302 INFO L226 Difference]: Without dead ends: 25 [2020-12-23 07:10:35,303 INFO L677 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 [2020-12-23 07:10:35,304 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 25 states. [2020-12-23 07:10:35,307 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 25 to 18. [2020-12-23 07:10:35,308 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 18 states. [2020-12-23 07:10:35,308 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 18 states to 18 states and 24 transitions. [2020-12-23 07:10:35,309 INFO L78 Accepts]: Start accepts. Automaton has 18 states and 24 transitions. Word has length 15 [2020-12-23 07:10:35,309 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-12-23 07:10:35,309 INFO L481 AbstractCegarLoop]: Abstraction has 18 states and 24 transitions. [2020-12-23 07:10:35,309 INFO L482 AbstractCegarLoop]: Interpolant automaton has 3 states. [2020-12-23 07:10:35,309 INFO L276 IsEmpty]: Start isEmpty. Operand 18 states and 24 transitions. [2020-12-23 07:10:35,310 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2020-12-23 07:10:35,310 INFO L414 BasicCegarLoop]: Found error trace [2020-12-23 07:10:35,310 INFO L422 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2020-12-23 07:10:35,311 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2020-12-23 07:10:35,311 INFO L429 AbstractCegarLoop]: === Iteration 4 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-12-23 07:10:35,311 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-12-23 07:10:35,311 INFO L82 PathProgramCache]: Analyzing trace with hash 630429873, now seen corresponding path program 1 times [2020-12-23 07:10:35,312 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-12-23 07:10:35,312 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [563103489] [2020-12-23 07:10:35,312 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-12-23 07:10:35,334 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-12-23 07:10:35,428 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2020-12-23 07:10:35,429 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [563103489] [2020-12-23 07:10:35,429 INFO L219 FreeRefinementEngine]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2020-12-23 07:10:35,429 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2020-12-23 07:10:35,429 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [986421764] [2020-12-23 07:10:35,430 INFO L461 AbstractCegarLoop]: Interpolant automaton has 4 states [2020-12-23 07:10:35,430 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-12-23 07:10:35,431 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2020-12-23 07:10:35,431 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2020-12-23 07:10:35,431 INFO L87 Difference]: Start difference. First operand 18 states and 24 transitions. Second operand 4 states. [2020-12-23 07:10:35,482 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-12-23 07:10:35,482 INFO L93 Difference]: Finished difference Result 46 states and 64 transitions. [2020-12-23 07:10:35,483 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2020-12-23 07:10:35,484 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 15 [2020-12-23 07:10:35,484 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-12-23 07:10:35,486 INFO L225 Difference]: With dead ends: 46 [2020-12-23 07:10:35,487 INFO L226 Difference]: Without dead ends: 32 [2020-12-23 07:10:35,487 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2020-12-23 07:10:35,488 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2020-12-23 07:10:35,496 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 30. [2020-12-23 07:10:35,496 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 30 states. [2020-12-23 07:10:35,497 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 42 transitions. [2020-12-23 07:10:35,498 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 42 transitions. Word has length 15 [2020-12-23 07:10:35,498 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-12-23 07:10:35,498 INFO L481 AbstractCegarLoop]: Abstraction has 30 states and 42 transitions. [2020-12-23 07:10:35,498 INFO L482 AbstractCegarLoop]: Interpolant automaton has 4 states. [2020-12-23 07:10:35,499 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 42 transitions. [2020-12-23 07:10:35,499 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2020-12-23 07:10:35,499 INFO L414 BasicCegarLoop]: Found error trace [2020-12-23 07:10:35,500 INFO L422 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2020-12-23 07:10:35,500 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2020-12-23 07:10:35,500 INFO L429 AbstractCegarLoop]: === Iteration 5 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-12-23 07:10:35,501 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-12-23 07:10:35,501 INFO L82 PathProgramCache]: Analyzing trace with hash 630489455, now seen corresponding path program 1 times [2020-12-23 07:10:35,501 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-12-23 07:10:35,501 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2076071811] [2020-12-23 07:10:35,502 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-12-23 07:10:35,521 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-12-23 07:10:35,577 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2020-12-23 07:10:35,578 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2076071811] [2020-12-23 07:10:35,578 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [999286438] [2020-12-23 07:10:35,578 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate-bitabs/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 2 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-12-23 07:10:35,664 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-12-23 07:10:35,666 INFO L263 TraceCheckSpWp]: Trace formula consists of 84 conjuncts, 4 conjunts are in the unsatisfiable core [2020-12-23 07:10:35,672 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2020-12-23 07:10:35,784 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2020-12-23 07:10:35,785 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2020-12-23 07:10:35,785 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 6 [2020-12-23 07:10:35,785 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1804089124] [2020-12-23 07:10:35,786 INFO L461 AbstractCegarLoop]: Interpolant automaton has 7 states [2020-12-23 07:10:35,786 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-12-23 07:10:35,787 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2020-12-23 07:10:35,787 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=22, Unknown=0, NotChecked=0, Total=42 [2020-12-23 07:10:35,787 INFO L87 Difference]: Start difference. First operand 30 states and 42 transitions. Second operand 7 states. [2020-12-23 07:10:35,928 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-12-23 07:10:35,928 INFO L93 Difference]: Finished difference Result 67 states and 97 transitions. [2020-12-23 07:10:35,929 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2020-12-23 07:10:35,929 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 15 [2020-12-23 07:10:35,929 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-12-23 07:10:35,930 INFO L225 Difference]: With dead ends: 67 [2020-12-23 07:10:35,930 INFO L226 Difference]: Without dead ends: 41 [2020-12-23 07:10:35,931 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 18 GetRequests, 13 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=20, Invalid=22, Unknown=0, NotChecked=0, Total=42 [2020-12-23 07:10:35,932 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2020-12-23 07:10:35,938 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 36. [2020-12-23 07:10:35,938 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 36 states. [2020-12-23 07:10:35,940 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 50 transitions. [2020-12-23 07:10:35,940 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 50 transitions. Word has length 15 [2020-12-23 07:10:35,940 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-12-23 07:10:35,940 INFO L481 AbstractCegarLoop]: Abstraction has 36 states and 50 transitions. [2020-12-23 07:10:35,941 INFO L482 AbstractCegarLoop]: Interpolant automaton has 7 states. [2020-12-23 07:10:35,941 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 50 transitions. [2020-12-23 07:10:35,941 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2020-12-23 07:10:35,942 INFO L414 BasicCegarLoop]: Found error trace [2020-12-23 07:10:35,942 INFO L422 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2020-12-23 07:10:36,155 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,2 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-12-23 07:10:36,156 INFO L429 AbstractCegarLoop]: === Iteration 6 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-12-23 07:10:36,158 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-12-23 07:10:36,158 INFO L82 PathProgramCache]: Analyzing trace with hash 730990835, now seen corresponding path program 2 times [2020-12-23 07:10:36,159 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-12-23 07:10:36,159 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [64558816] [2020-12-23 07:10:36,160 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-12-23 07:10:36,185 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-12-23 07:10:36,299 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 5 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2020-12-23 07:10:36,300 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [64558816] [2020-12-23 07:10:36,300 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1330386237] [2020-12-23 07:10:36,300 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate-bitabs/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-12-23 07:10:36,373 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2020-12-23 07:10:36,374 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2020-12-23 07:10:36,375 INFO L263 TraceCheckSpWp]: Trace formula consists of 90 conjuncts, 5 conjunts are in the unsatisfiable core [2020-12-23 07:10:36,377 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2020-12-23 07:10:36,503 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2020-12-23 07:10:36,503 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2020-12-23 07:10:36,503 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 8 [2020-12-23 07:10:36,504 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1469791600] [2020-12-23 07:10:36,505 INFO L461 AbstractCegarLoop]: Interpolant automaton has 9 states [2020-12-23 07:10:36,506 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-12-23 07:10:36,506 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2020-12-23 07:10:36,507 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=24, Invalid=48, Unknown=0, NotChecked=0, Total=72 [2020-12-23 07:10:36,507 INFO L87 Difference]: Start difference. First operand 36 states and 50 transitions. Second operand 9 states. [2020-12-23 07:10:36,864 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-12-23 07:10:36,864 INFO L93 Difference]: Finished difference Result 123 states and 179 transitions. [2020-12-23 07:10:36,865 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2020-12-23 07:10:36,865 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 18 [2020-12-23 07:10:36,865 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-12-23 07:10:36,867 INFO L225 Difference]: With dead ends: 123 [2020-12-23 07:10:36,867 INFO L226 Difference]: Without dead ends: 91 [2020-12-23 07:10:36,868 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 15 SyntacticMatches, 0 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 40 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=82, Invalid=158, Unknown=0, NotChecked=0, Total=240 [2020-12-23 07:10:36,869 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 91 states. [2020-12-23 07:10:36,882 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 91 to 76. [2020-12-23 07:10:36,882 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 76 states. [2020-12-23 07:10:36,884 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 76 states to 76 states and 103 transitions. [2020-12-23 07:10:36,884 INFO L78 Accepts]: Start accepts. Automaton has 76 states and 103 transitions. Word has length 18 [2020-12-23 07:10:36,884 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-12-23 07:10:36,884 INFO L481 AbstractCegarLoop]: Abstraction has 76 states and 103 transitions. [2020-12-23 07:10:36,885 INFO L482 AbstractCegarLoop]: Interpolant automaton has 9 states. [2020-12-23 07:10:36,885 INFO L276 IsEmpty]: Start isEmpty. Operand 76 states and 103 transitions. [2020-12-23 07:10:36,886 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2020-12-23 07:10:36,886 INFO L414 BasicCegarLoop]: Found error trace [2020-12-23 07:10:36,886 INFO L422 BasicCegarLoop]: trace histogram [3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2020-12-23 07:10:37,099 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,3 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-12-23 07:10:37,100 INFO L429 AbstractCegarLoop]: === Iteration 7 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-12-23 07:10:37,101 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-12-23 07:10:37,101 INFO L82 PathProgramCache]: Analyzing trace with hash -104466575, now seen corresponding path program 1 times [2020-12-23 07:10:37,102 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-12-23 07:10:37,102 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [445318234] [2020-12-23 07:10:37,102 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-12-23 07:10:37,119 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-12-23 07:10:37,168 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 12 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2020-12-23 07:10:37,168 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [445318234] [2020-12-23 07:10:37,169 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1379504905] [2020-12-23 07:10:37,169 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate-bitabs/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-12-23 07:10:37,224 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-12-23 07:10:37,225 INFO L263 TraceCheckSpWp]: Trace formula consists of 94 conjuncts, 6 conjunts are in the unsatisfiable core [2020-12-23 07:10:37,227 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2020-12-23 07:10:37,320 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 12 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2020-12-23 07:10:37,321 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2020-12-23 07:10:37,321 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 10 [2020-12-23 07:10:37,321 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [893813092] [2020-12-23 07:10:37,322 INFO L461 AbstractCegarLoop]: Interpolant automaton has 11 states [2020-12-23 07:10:37,322 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-12-23 07:10:37,323 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2020-12-23 07:10:37,323 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=49, Invalid=61, Unknown=0, NotChecked=0, Total=110 [2020-12-23 07:10:37,323 INFO L87 Difference]: Start difference. First operand 76 states and 103 transitions. Second operand 11 states. [2020-12-23 07:10:37,468 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-12-23 07:10:37,468 INFO L93 Difference]: Finished difference Result 199 states and 271 transitions. [2020-12-23 07:10:37,468 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2020-12-23 07:10:37,469 INFO L78 Accepts]: Start accepts. Automaton has 11 states. Word has length 21 [2020-12-23 07:10:37,469 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-12-23 07:10:37,471 INFO L225 Difference]: With dead ends: 199 [2020-12-23 07:10:37,471 INFO L226 Difference]: Without dead ends: 127 [2020-12-23 07:10:37,472 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 26 GetRequests, 17 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 21 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=49, Invalid=61, Unknown=0, NotChecked=0, Total=110 [2020-12-23 07:10:37,473 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 127 states. [2020-12-23 07:10:37,487 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 127 to 88. [2020-12-23 07:10:37,488 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 88 states. [2020-12-23 07:10:37,489 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 88 states to 88 states and 119 transitions. [2020-12-23 07:10:37,489 INFO L78 Accepts]: Start accepts. Automaton has 88 states and 119 transitions. Word has length 21 [2020-12-23 07:10:37,490 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-12-23 07:10:37,490 INFO L481 AbstractCegarLoop]: Abstraction has 88 states and 119 transitions. [2020-12-23 07:10:37,490 INFO L482 AbstractCegarLoop]: Interpolant automaton has 11 states. [2020-12-23 07:10:37,490 INFO L276 IsEmpty]: Start isEmpty. Operand 88 states and 119 transitions. [2020-12-23 07:10:37,491 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2020-12-23 07:10:37,491 INFO L414 BasicCegarLoop]: Found error trace [2020-12-23 07:10:37,492 INFO L422 BasicCegarLoop]: trace histogram [4, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2020-12-23 07:10:37,692 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,4 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-12-23 07:10:37,693 INFO L429 AbstractCegarLoop]: === Iteration 8 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-12-23 07:10:37,694 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-12-23 07:10:37,694 INFO L82 PathProgramCache]: Analyzing trace with hash 1399176113, now seen corresponding path program 2 times [2020-12-23 07:10:37,695 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-12-23 07:10:37,696 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1616270407] [2020-12-23 07:10:37,696 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-12-23 07:10:37,713 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-12-23 07:10:37,787 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 0 proven. 22 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2020-12-23 07:10:37,787 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1616270407] [2020-12-23 07:10:37,788 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [8955558] [2020-12-23 07:10:37,788 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate-bitabs/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-12-23 07:10:37,842 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2020-12-23 07:10:37,842 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2020-12-23 07:10:37,843 INFO L263 TraceCheckSpWp]: Trace formula consists of 100 conjuncts, 6 conjunts are in the unsatisfiable core [2020-12-23 07:10:37,845 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2020-12-23 07:10:37,941 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2020-12-23 07:10:37,942 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2020-12-23 07:10:37,942 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 6] total 11 [2020-12-23 07:10:37,942 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [319157709] [2020-12-23 07:10:37,942 INFO L461 AbstractCegarLoop]: Interpolant automaton has 12 states [2020-12-23 07:10:37,943 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-12-23 07:10:37,943 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2020-12-23 07:10:37,944 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=46, Invalid=86, Unknown=0, NotChecked=0, Total=132 [2020-12-23 07:10:37,944 INFO L87 Difference]: Start difference. First operand 88 states and 119 transitions. Second operand 12 states. [2020-12-23 07:10:38,233 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-12-23 07:10:38,233 INFO L93 Difference]: Finished difference Result 291 states and 407 transitions. [2020-12-23 07:10:38,234 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2020-12-23 07:10:38,234 INFO L78 Accepts]: Start accepts. Automaton has 12 states. Word has length 24 [2020-12-23 07:10:38,234 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-12-23 07:10:38,236 INFO L225 Difference]: With dead ends: 291 [2020-12-23 07:10:38,236 INFO L226 Difference]: Without dead ends: 207 [2020-12-23 07:10:38,237 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 40 GetRequests, 20 SyntacticMatches, 0 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 104 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=156, Invalid=306, Unknown=0, NotChecked=0, Total=462 [2020-12-23 07:10:38,238 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 207 states. [2020-12-23 07:10:38,259 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 207 to 146. [2020-12-23 07:10:38,259 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 146 states. [2020-12-23 07:10:38,261 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 146 states to 146 states and 198 transitions. [2020-12-23 07:10:38,261 INFO L78 Accepts]: Start accepts. Automaton has 146 states and 198 transitions. Word has length 24 [2020-12-23 07:10:38,261 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-12-23 07:10:38,261 INFO L481 AbstractCegarLoop]: Abstraction has 146 states and 198 transitions. [2020-12-23 07:10:38,261 INFO L482 AbstractCegarLoop]: Interpolant automaton has 12 states. [2020-12-23 07:10:38,261 INFO L276 IsEmpty]: Start isEmpty. Operand 146 states and 198 transitions. [2020-12-23 07:10:38,266 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2020-12-23 07:10:38,266 INFO L414 BasicCegarLoop]: Found error trace [2020-12-23 07:10:38,266 INFO L422 BasicCegarLoop]: trace histogram [5, 5, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2020-12-23 07:10:38,467 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,5 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-12-23 07:10:38,467 INFO L429 AbstractCegarLoop]: === Iteration 9 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-12-23 07:10:38,468 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-12-23 07:10:38,469 INFO L82 PathProgramCache]: Analyzing trace with hash -2084547665, now seen corresponding path program 3 times [2020-12-23 07:10:38,469 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-12-23 07:10:38,469 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [509505362] [2020-12-23 07:10:38,469 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-12-23 07:10:38,492 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-12-23 07:10:38,596 INFO L134 CoverageAnalysis]: Checked inductivity of 35 backedges. 0 proven. 35 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2020-12-23 07:10:38,597 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [509505362] [2020-12-23 07:10:38,597 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1360056515] [2020-12-23 07:10:38,597 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 No working directory specified, using /storage/repos/ultimate-bitabs/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-12-23 07:10:38,660 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 2 check-sat command(s) [2020-12-23 07:10:38,660 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2020-12-23 07:10:38,661 INFO L263 TraceCheckSpWp]: Trace formula consists of 84 conjuncts, 3 conjunts are in the unsatisfiable core [2020-12-23 07:10:38,668 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2020-12-23 07:10:38,734 INFO L134 CoverageAnalysis]: Checked inductivity of 35 backedges. 9 proven. 0 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2020-12-23 07:10:38,735 INFO L219 FreeRefinementEngine]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2020-12-23 07:10:38,735 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [8] total 11 [2020-12-23 07:10:38,735 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1890645573] [2020-12-23 07:10:38,735 INFO L461 AbstractCegarLoop]: Interpolant automaton has 4 states [2020-12-23 07:10:38,736 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-12-23 07:10:38,738 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2020-12-23 07:10:38,738 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=36, Invalid=74, Unknown=0, NotChecked=0, Total=110 [2020-12-23 07:10:38,738 INFO L87 Difference]: Start difference. First operand 146 states and 198 transitions. Second operand 4 states. [2020-12-23 07:10:38,801 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-12-23 07:10:38,801 INFO L93 Difference]: Finished difference Result 334 states and 454 transitions. [2020-12-23 07:10:38,801 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2020-12-23 07:10:38,801 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 27 [2020-12-23 07:10:38,802 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-12-23 07:10:38,804 INFO L225 Difference]: With dead ends: 334 [2020-12-23 07:10:38,804 INFO L226 Difference]: Without dead ends: 192 [2020-12-23 07:10:38,809 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 34 GetRequests, 25 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 17 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=36, Invalid=74, Unknown=0, NotChecked=0, Total=110 [2020-12-23 07:10:38,809 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 192 states. [2020-12-23 07:10:38,846 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 192 to 164. [2020-12-23 07:10:38,847 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 164 states. [2020-12-23 07:10:38,850 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 164 states to 164 states and 206 transitions. [2020-12-23 07:10:38,850 INFO L78 Accepts]: Start accepts. Automaton has 164 states and 206 transitions. Word has length 27 [2020-12-23 07:10:38,850 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-12-23 07:10:38,851 INFO L481 AbstractCegarLoop]: Abstraction has 164 states and 206 transitions. [2020-12-23 07:10:38,851 INFO L482 AbstractCegarLoop]: Interpolant automaton has 4 states. [2020-12-23 07:10:38,851 INFO L276 IsEmpty]: Start isEmpty. Operand 164 states and 206 transitions. [2020-12-23 07:10:38,852 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2020-12-23 07:10:38,852 INFO L414 BasicCegarLoop]: Found error trace [2020-12-23 07:10:38,853 INFO L422 BasicCegarLoop]: trace histogram [5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2020-12-23 07:10:39,066 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,6 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-12-23 07:10:39,067 INFO L429 AbstractCegarLoop]: === Iteration 10 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-12-23 07:10:39,068 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-12-23 07:10:39,068 INFO L82 PathProgramCache]: Analyzing trace with hash 1868779761, now seen corresponding path program 1 times [2020-12-23 07:10:39,069 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-12-23 07:10:39,069 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1217539720] [2020-12-23 07:10:39,070 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-12-23 07:10:39,080 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-12-23 07:10:39,099 INFO L134 CoverageAnalysis]: Checked inductivity of 35 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 35 trivial. 0 not checked. [2020-12-23 07:10:39,099 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1217539720] [2020-12-23 07:10:39,100 INFO L219 FreeRefinementEngine]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2020-12-23 07:10:39,100 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2020-12-23 07:10:39,100 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [601223758] [2020-12-23 07:10:39,100 INFO L461 AbstractCegarLoop]: Interpolant automaton has 3 states [2020-12-23 07:10:39,100 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-12-23 07:10:39,101 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2020-12-23 07:10:39,101 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2020-12-23 07:10:39,101 INFO L87 Difference]: Start difference. First operand 164 states and 206 transitions. Second operand 3 states. [2020-12-23 07:10:39,128 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-12-23 07:10:39,128 INFO L93 Difference]: Finished difference Result 344 states and 436 transitions. [2020-12-23 07:10:39,129 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2020-12-23 07:10:39,129 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 27 [2020-12-23 07:10:39,129 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-12-23 07:10:39,130 INFO L225 Difference]: With dead ends: 344 [2020-12-23 07:10:39,131 INFO L226 Difference]: Without dead ends: 184 [2020-12-23 07:10:39,133 INFO L677 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 [2020-12-23 07:10:39,133 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 184 states. [2020-12-23 07:10:39,145 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 184 to 162. [2020-12-23 07:10:39,146 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 162 states. [2020-12-23 07:10:39,146 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 162 states to 162 states and 200 transitions. [2020-12-23 07:10:39,147 INFO L78 Accepts]: Start accepts. Automaton has 162 states and 200 transitions. Word has length 27 [2020-12-23 07:10:39,147 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-12-23 07:10:39,147 INFO L481 AbstractCegarLoop]: Abstraction has 162 states and 200 transitions. [2020-12-23 07:10:39,147 INFO L482 AbstractCegarLoop]: Interpolant automaton has 3 states. [2020-12-23 07:10:39,147 INFO L276 IsEmpty]: Start isEmpty. Operand 162 states and 200 transitions. [2020-12-23 07:10:39,148 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2020-12-23 07:10:39,149 INFO L414 BasicCegarLoop]: Found error trace [2020-12-23 07:10:39,149 INFO L422 BasicCegarLoop]: trace histogram [5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2020-12-23 07:10:39,149 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9 [2020-12-23 07:10:39,149 INFO L429 AbstractCegarLoop]: === Iteration 11 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-12-23 07:10:39,150 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-12-23 07:10:39,150 INFO L82 PathProgramCache]: Analyzing trace with hash 1323368939, now seen corresponding path program 1 times [2020-12-23 07:10:39,150 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-12-23 07:10:39,150 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2071061441] [2020-12-23 07:10:39,150 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-12-23 07:10:39,161 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-12-23 07:10:39,178 INFO L134 CoverageAnalysis]: Checked inductivity of 35 backedges. 9 proven. 0 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2020-12-23 07:10:39,178 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2071061441] [2020-12-23 07:10:39,178 INFO L219 FreeRefinementEngine]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2020-12-23 07:10:39,179 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2020-12-23 07:10:39,179 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [45814717] [2020-12-23 07:10:39,179 INFO L461 AbstractCegarLoop]: Interpolant automaton has 3 states [2020-12-23 07:10:39,179 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-12-23 07:10:39,180 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2020-12-23 07:10:39,180 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2020-12-23 07:10:39,180 INFO L87 Difference]: Start difference. First operand 162 states and 200 transitions. Second operand 3 states. [2020-12-23 07:10:39,205 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-12-23 07:10:39,205 INFO L93 Difference]: Finished difference Result 256 states and 318 transitions. [2020-12-23 07:10:39,206 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2020-12-23 07:10:39,206 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 28 [2020-12-23 07:10:39,206 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-12-23 07:10:39,207 INFO L225 Difference]: With dead ends: 256 [2020-12-23 07:10:39,207 INFO L226 Difference]: Without dead ends: 176 [2020-12-23 07:10:39,208 INFO L677 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 [2020-12-23 07:10:39,208 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 176 states. [2020-12-23 07:10:39,220 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 176 to 166. [2020-12-23 07:10:39,221 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 166 states. [2020-12-23 07:10:39,221 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 166 states to 166 states and 200 transitions. [2020-12-23 07:10:39,222 INFO L78 Accepts]: Start accepts. Automaton has 166 states and 200 transitions. Word has length 28 [2020-12-23 07:10:39,222 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-12-23 07:10:39,222 INFO L481 AbstractCegarLoop]: Abstraction has 166 states and 200 transitions. [2020-12-23 07:10:39,222 INFO L482 AbstractCegarLoop]: Interpolant automaton has 3 states. [2020-12-23 07:10:39,222 INFO L276 IsEmpty]: Start isEmpty. Operand 166 states and 200 transitions. [2020-12-23 07:10:39,223 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2020-12-23 07:10:39,223 INFO L414 BasicCegarLoop]: Found error trace [2020-12-23 07:10:39,224 INFO L422 BasicCegarLoop]: trace histogram [5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2020-12-23 07:10:39,224 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10 [2020-12-23 07:10:39,224 INFO L429 AbstractCegarLoop]: === Iteration 12 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-12-23 07:10:39,224 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-12-23 07:10:39,224 INFO L82 PathProgramCache]: Analyzing trace with hash 1325275563, now seen corresponding path program 1 times [2020-12-23 07:10:39,225 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-12-23 07:10:39,225 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [372522751] [2020-12-23 07:10:39,225 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-12-23 07:10:39,237 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-12-23 07:10:39,311 INFO L134 CoverageAnalysis]: Checked inductivity of 35 backedges. 0 proven. 35 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2020-12-23 07:10:39,311 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [372522751] [2020-12-23 07:10:39,312 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [119834703] [2020-12-23 07:10:39,312 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate-bitabs/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-12-23 07:10:39,362 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-12-23 07:10:39,363 INFO L263 TraceCheckSpWp]: Trace formula consists of 104 conjuncts, 8 conjunts are in the unsatisfiable core [2020-12-23 07:10:39,364 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2020-12-23 07:10:39,495 INFO L134 CoverageAnalysis]: Checked inductivity of 35 backedges. 0 proven. 35 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2020-12-23 07:10:39,495 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2020-12-23 07:10:39,495 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 14 [2020-12-23 07:10:39,496 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1750604270] [2020-12-23 07:10:39,496 INFO L461 AbstractCegarLoop]: Interpolant automaton has 15 states [2020-12-23 07:10:39,496 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-12-23 07:10:39,497 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2020-12-23 07:10:39,497 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=90, Invalid=120, Unknown=0, NotChecked=0, Total=210 [2020-12-23 07:10:39,497 INFO L87 Difference]: Start difference. First operand 166 states and 200 transitions. Second operand 15 states. [2020-12-23 07:10:39,658 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-12-23 07:10:39,658 INFO L93 Difference]: Finished difference Result 457 states and 547 transitions. [2020-12-23 07:10:39,658 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2020-12-23 07:10:39,658 INFO L78 Accepts]: Start accepts. Automaton has 15 states. Word has length 28 [2020-12-23 07:10:39,659 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-12-23 07:10:39,660 INFO L225 Difference]: With dead ends: 457 [2020-12-23 07:10:39,661 INFO L226 Difference]: Without dead ends: 295 [2020-12-23 07:10:39,661 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 35 GetRequests, 22 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 57 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=90, Invalid=120, Unknown=0, NotChecked=0, Total=210 [2020-12-23 07:10:39,662 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 295 states. [2020-12-23 07:10:39,674 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 295 to 196. [2020-12-23 07:10:39,675 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 196 states. [2020-12-23 07:10:39,676 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 196 states to 196 states and 234 transitions. [2020-12-23 07:10:39,676 INFO L78 Accepts]: Start accepts. Automaton has 196 states and 234 transitions. Word has length 28 [2020-12-23 07:10:39,676 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-12-23 07:10:39,676 INFO L481 AbstractCegarLoop]: Abstraction has 196 states and 234 transitions. [2020-12-23 07:10:39,676 INFO L482 AbstractCegarLoop]: Interpolant automaton has 15 states. [2020-12-23 07:10:39,676 INFO L276 IsEmpty]: Start isEmpty. Operand 196 states and 234 transitions. [2020-12-23 07:10:39,677 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2020-12-23 07:10:39,677 INFO L414 BasicCegarLoop]: Found error trace [2020-12-23 07:10:39,677 INFO L422 BasicCegarLoop]: trace histogram [6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2020-12-23 07:10:39,891 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,7 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-12-23 07:10:39,892 INFO L429 AbstractCegarLoop]: === Iteration 13 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-12-23 07:10:39,893 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-12-23 07:10:39,893 INFO L82 PathProgramCache]: Analyzing trace with hash 399501479, now seen corresponding path program 2 times [2020-12-23 07:10:39,894 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-12-23 07:10:39,894 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [794915369] [2020-12-23 07:10:39,895 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-12-23 07:10:39,909 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-12-23 07:10:39,983 INFO L134 CoverageAnalysis]: Checked inductivity of 51 backedges. 0 proven. 51 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2020-12-23 07:10:39,983 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [794915369] [2020-12-23 07:10:39,984 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [606063068] [2020-12-23 07:10:39,984 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate-bitabs/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-12-23 07:10:40,030 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2020-12-23 07:10:40,030 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2020-12-23 07:10:40,031 INFO L263 TraceCheckSpWp]: Trace formula consists of 110 conjuncts, 9 conjunts are in the unsatisfiable core [2020-12-23 07:10:40,033 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2020-12-23 07:10:40,171 INFO L134 CoverageAnalysis]: Checked inductivity of 51 backedges. 0 proven. 51 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2020-12-23 07:10:40,172 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2020-12-23 07:10:40,172 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 16 [2020-12-23 07:10:40,172 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1225797739] [2020-12-23 07:10:40,173 INFO L461 AbstractCegarLoop]: Interpolant automaton has 17 states [2020-12-23 07:10:40,173 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-12-23 07:10:40,173 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2020-12-23 07:10:40,174 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=115, Invalid=157, Unknown=0, NotChecked=0, Total=272 [2020-12-23 07:10:40,174 INFO L87 Difference]: Start difference. First operand 196 states and 234 transitions. Second operand 17 states. [2020-12-23 07:10:40,309 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-12-23 07:10:40,309 INFO L93 Difference]: Finished difference Result 517 states and 615 transitions. [2020-12-23 07:10:40,309 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2020-12-23 07:10:40,310 INFO L78 Accepts]: Start accepts. Automaton has 17 states. Word has length 31 [2020-12-23 07:10:40,310 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-12-23 07:10:40,312 INFO L225 Difference]: With dead ends: 517 [2020-12-23 07:10:40,312 INFO L226 Difference]: Without dead ends: 325 [2020-12-23 07:10:40,313 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 39 GetRequests, 24 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 81 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=115, Invalid=157, Unknown=0, NotChecked=0, Total=272 [2020-12-23 07:10:40,313 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 325 states. [2020-12-23 07:10:40,328 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 325 to 226. [2020-12-23 07:10:40,328 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 226 states. [2020-12-23 07:10:40,329 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 226 states to 226 states and 268 transitions. [2020-12-23 07:10:40,329 INFO L78 Accepts]: Start accepts. Automaton has 226 states and 268 transitions. Word has length 31 [2020-12-23 07:10:40,330 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-12-23 07:10:40,330 INFO L481 AbstractCegarLoop]: Abstraction has 226 states and 268 transitions. [2020-12-23 07:10:40,330 INFO L482 AbstractCegarLoop]: Interpolant automaton has 17 states. [2020-12-23 07:10:40,330 INFO L276 IsEmpty]: Start isEmpty. Operand 226 states and 268 transitions. [2020-12-23 07:10:40,331 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2020-12-23 07:10:40,331 INFO L414 BasicCegarLoop]: Found error trace [2020-12-23 07:10:40,331 INFO L422 BasicCegarLoop]: trace histogram [7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2020-12-23 07:10:40,545 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable12,8 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-12-23 07:10:40,546 INFO L429 AbstractCegarLoop]: === Iteration 14 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-12-23 07:10:40,547 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-12-23 07:10:40,547 INFO L82 PathProgramCache]: Analyzing trace with hash -1351227349, now seen corresponding path program 3 times [2020-12-23 07:10:40,547 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-12-23 07:10:40,548 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1801641946] [2020-12-23 07:10:40,548 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-12-23 07:10:40,564 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-12-23 07:10:40,675 INFO L134 CoverageAnalysis]: Checked inductivity of 70 backedges. 0 proven. 70 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2020-12-23 07:10:40,675 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1801641946] [2020-12-23 07:10:40,675 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [17846258] [2020-12-23 07:10:40,675 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 No working directory specified, using /storage/repos/ultimate-bitabs/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-12-23 07:10:40,743 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2020-12-23 07:10:40,743 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2020-12-23 07:10:40,744 INFO L263 TraceCheckSpWp]: Trace formula consists of 86 conjuncts, 7 conjunts are in the unsatisfiable core [2020-12-23 07:10:40,746 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2020-12-23 07:10:40,812 INFO L134 CoverageAnalysis]: Checked inductivity of 70 backedges. 13 proven. 0 refuted. 0 times theorem prover too weak. 57 trivial. 0 not checked. [2020-12-23 07:10:40,812 INFO L219 FreeRefinementEngine]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2020-12-23 07:10:40,812 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [10] total 14 [2020-12-23 07:10:40,813 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [361651149] [2020-12-23 07:10:40,813 INFO L461 AbstractCegarLoop]: Interpolant automaton has 5 states [2020-12-23 07:10:40,813 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-12-23 07:10:40,814 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2020-12-23 07:10:40,814 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=55, Invalid=127, Unknown=0, NotChecked=0, Total=182 [2020-12-23 07:10:40,814 INFO L87 Difference]: Start difference. First operand 226 states and 268 transitions. Second operand 5 states. [2020-12-23 07:10:40,898 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-12-23 07:10:40,899 INFO L93 Difference]: Finished difference Result 229 states and 270 transitions. [2020-12-23 07:10:40,899 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2020-12-23 07:10:40,899 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 34 [2020-12-23 07:10:40,899 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-12-23 07:10:40,900 INFO L225 Difference]: With dead ends: 229 [2020-12-23 07:10:40,900 INFO L226 Difference]: Without dead ends: 169 [2020-12-23 07:10:40,901 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 45 GetRequests, 31 SyntacticMatches, 0 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 33 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=65, Invalid=175, Unknown=0, NotChecked=0, Total=240 [2020-12-23 07:10:40,901 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 169 states. [2020-12-23 07:10:40,913 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 169 to 168. [2020-12-23 07:10:40,913 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 168 states. [2020-12-23 07:10:40,914 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 168 states to 168 states and 201 transitions. [2020-12-23 07:10:40,914 INFO L78 Accepts]: Start accepts. Automaton has 168 states and 201 transitions. Word has length 34 [2020-12-23 07:10:40,915 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-12-23 07:10:40,915 INFO L481 AbstractCegarLoop]: Abstraction has 168 states and 201 transitions. [2020-12-23 07:10:40,915 INFO L482 AbstractCegarLoop]: Interpolant automaton has 5 states. [2020-12-23 07:10:40,915 INFO L276 IsEmpty]: Start isEmpty. Operand 168 states and 201 transitions. [2020-12-23 07:10:40,915 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2020-12-23 07:10:40,915 INFO L414 BasicCegarLoop]: Found error trace [2020-12-23 07:10:40,916 INFO L422 BasicCegarLoop]: trace histogram [7, 7, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2020-12-23 07:10:41,128 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2020-12-23 07:10:41,129 INFO L429 AbstractCegarLoop]: === Iteration 15 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-12-23 07:10:41,130 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-12-23 07:10:41,130 INFO L82 PathProgramCache]: Analyzing trace with hash -1860700439, now seen corresponding path program 1 times [2020-12-23 07:10:41,131 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-12-23 07:10:41,131 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2124863283] [2020-12-23 07:10:41,131 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-12-23 07:10:41,143 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-12-23 07:10:41,227 INFO L134 CoverageAnalysis]: Checked inductivity of 70 backedges. 0 proven. 70 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2020-12-23 07:10:41,227 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2124863283] [2020-12-23 07:10:41,227 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [927047523] [2020-12-23 07:10:41,227 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate-bitabs/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-12-23 07:10:41,279 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-12-23 07:10:41,280 INFO L263 TraceCheckSpWp]: Trace formula consists of 114 conjuncts, 10 conjunts are in the unsatisfiable core [2020-12-23 07:10:41,282 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2020-12-23 07:10:41,442 INFO L134 CoverageAnalysis]: Checked inductivity of 70 backedges. 0 proven. 70 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2020-12-23 07:10:41,442 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2020-12-23 07:10:41,442 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 18 [2020-12-23 07:10:41,443 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [69441826] [2020-12-23 07:10:41,443 INFO L461 AbstractCegarLoop]: Interpolant automaton has 19 states [2020-12-23 07:10:41,443 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-12-23 07:10:41,444 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2020-12-23 07:10:41,444 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=143, Invalid=199, Unknown=0, NotChecked=0, Total=342 [2020-12-23 07:10:41,444 INFO L87 Difference]: Start difference. First operand 168 states and 201 transitions. Second operand 19 states. [2020-12-23 07:10:41,638 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-12-23 07:10:41,638 INFO L93 Difference]: Finished difference Result 451 states and 537 transitions. [2020-12-23 07:10:41,639 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2020-12-23 07:10:41,639 INFO L78 Accepts]: Start accepts. Automaton has 19 states. Word has length 34 [2020-12-23 07:10:41,639 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-12-23 07:10:41,641 INFO L225 Difference]: With dead ends: 451 [2020-12-23 07:10:41,641 INFO L226 Difference]: Without dead ends: 287 [2020-12-23 07:10:41,642 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 43 GetRequests, 26 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 109 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=143, Invalid=199, Unknown=0, NotChecked=0, Total=342 [2020-12-23 07:10:41,643 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 287 states. [2020-12-23 07:10:41,658 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 287 to 192. [2020-12-23 07:10:41,659 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 192 states. [2020-12-23 07:10:41,660 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 192 states to 192 states and 229 transitions. [2020-12-23 07:10:41,660 INFO L78 Accepts]: Start accepts. Automaton has 192 states and 229 transitions. Word has length 34 [2020-12-23 07:10:41,660 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-12-23 07:10:41,660 INFO L481 AbstractCegarLoop]: Abstraction has 192 states and 229 transitions. [2020-12-23 07:10:41,660 INFO L482 AbstractCegarLoop]: Interpolant automaton has 19 states. [2020-12-23 07:10:41,661 INFO L276 IsEmpty]: Start isEmpty. Operand 192 states and 229 transitions. [2020-12-23 07:10:41,661 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2020-12-23 07:10:41,661 INFO L414 BasicCegarLoop]: Found error trace [2020-12-23 07:10:41,661 INFO L422 BasicCegarLoop]: trace histogram [8, 8, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2020-12-23 07:10:41,874 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2020-12-23 07:10:41,875 INFO L429 AbstractCegarLoop]: === Iteration 16 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-12-23 07:10:41,876 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-12-23 07:10:41,877 INFO L82 PathProgramCache]: Analyzing trace with hash 1470700201, now seen corresponding path program 2 times [2020-12-23 07:10:41,877 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-12-23 07:10:41,878 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1404776559] [2020-12-23 07:10:41,878 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-12-23 07:10:41,890 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-12-23 07:10:42,011 INFO L134 CoverageAnalysis]: Checked inductivity of 92 backedges. 0 proven. 92 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2020-12-23 07:10:42,012 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1404776559] [2020-12-23 07:10:42,012 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1013277951] [2020-12-23 07:10:42,012 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate-bitabs/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-12-23 07:10:42,064 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2020-12-23 07:10:42,064 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2020-12-23 07:10:42,065 INFO L263 TraceCheckSpWp]: Trace formula consists of 120 conjuncts, 11 conjunts are in the unsatisfiable core [2020-12-23 07:10:42,067 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2020-12-23 07:10:42,275 INFO L134 CoverageAnalysis]: Checked inductivity of 92 backedges. 0 proven. 92 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2020-12-23 07:10:42,275 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2020-12-23 07:10:42,275 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11] total 20 [2020-12-23 07:10:42,276 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [80716169] [2020-12-23 07:10:42,277 INFO L461 AbstractCegarLoop]: Interpolant automaton has 21 states [2020-12-23 07:10:42,278 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-12-23 07:10:42,280 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2020-12-23 07:10:42,280 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=174, Invalid=246, Unknown=0, NotChecked=0, Total=420 [2020-12-23 07:10:42,280 INFO L87 Difference]: Start difference. First operand 192 states and 229 transitions. Second operand 21 states. [2020-12-23 07:10:42,447 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-12-23 07:10:42,447 INFO L93 Difference]: Finished difference Result 499 states and 593 transitions. [2020-12-23 07:10:42,447 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2020-12-23 07:10:42,447 INFO L78 Accepts]: Start accepts. Automaton has 21 states. Word has length 37 [2020-12-23 07:10:42,448 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-12-23 07:10:42,449 INFO L225 Difference]: With dead ends: 499 [2020-12-23 07:10:42,450 INFO L226 Difference]: Without dead ends: 311 [2020-12-23 07:10:42,450 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 47 GetRequests, 28 SyntacticMatches, 0 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 141 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=174, Invalid=246, Unknown=0, NotChecked=0, Total=420 [2020-12-23 07:10:42,451 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 311 states. [2020-12-23 07:10:42,465 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 311 to 216. [2020-12-23 07:10:42,466 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 216 states. [2020-12-23 07:10:42,467 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 216 states to 216 states and 257 transitions. [2020-12-23 07:10:42,467 INFO L78 Accepts]: Start accepts. Automaton has 216 states and 257 transitions. Word has length 37 [2020-12-23 07:10:42,467 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-12-23 07:10:42,467 INFO L481 AbstractCegarLoop]: Abstraction has 216 states and 257 transitions. [2020-12-23 07:10:42,467 INFO L482 AbstractCegarLoop]: Interpolant automaton has 21 states. [2020-12-23 07:10:42,467 INFO L276 IsEmpty]: Start isEmpty. Operand 216 states and 257 transitions. [2020-12-23 07:10:42,468 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2020-12-23 07:10:42,468 INFO L414 BasicCegarLoop]: Found error trace [2020-12-23 07:10:42,468 INFO L422 BasicCegarLoop]: trace histogram [9, 9, 8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2020-12-23 07:10:42,681 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2020-12-23 07:10:42,682 INFO L429 AbstractCegarLoop]: === Iteration 17 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-12-23 07:10:42,683 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-12-23 07:10:42,683 INFO L82 PathProgramCache]: Analyzing trace with hash -877109527, now seen corresponding path program 3 times [2020-12-23 07:10:42,684 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-12-23 07:10:42,684 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [861630668] [2020-12-23 07:10:42,685 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-12-23 07:10:42,707 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-12-23 07:10:42,868 INFO L134 CoverageAnalysis]: Checked inductivity of 117 backedges. 0 proven. 117 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2020-12-23 07:10:42,868 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [861630668] [2020-12-23 07:10:42,868 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [523305326] [2020-12-23 07:10:42,869 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 No working directory specified, using /storage/repos/ultimate-bitabs/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-12-23 07:10:42,908 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2020-12-23 07:10:42,909 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2020-12-23 07:10:42,910 INFO L263 TraceCheckSpWp]: Trace formula consists of 84 conjuncts, 14 conjunts are in the unsatisfiable core [2020-12-23 07:10:42,912 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2020-12-23 07:10:43,052 INFO L639 QuantifierPusher]: Distributing 2 conjuncts over 3 disjuncts [2020-12-23 07:10:43,077 INFO L134 CoverageAnalysis]: Checked inductivity of 117 backedges. 25 proven. 0 refuted. 0 times theorem prover too weak. 92 trivial. 0 not checked. [2020-12-23 07:10:43,077 INFO L219 FreeRefinementEngine]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2020-12-23 07:10:43,077 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [12] total 19 [2020-12-23 07:10:43,080 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [212478522] [2020-12-23 07:10:43,080 INFO L461 AbstractCegarLoop]: Interpolant automaton has 8 states [2020-12-23 07:10:43,081 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-12-23 07:10:43,081 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2020-12-23 07:10:43,082 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=86, Invalid=256, Unknown=0, NotChecked=0, Total=342 [2020-12-23 07:10:43,082 INFO L87 Difference]: Start difference. First operand 216 states and 257 transitions. Second operand 8 states. [2020-12-23 07:10:43,231 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-12-23 07:10:43,231 INFO L93 Difference]: Finished difference Result 496 states and 586 transitions. [2020-12-23 07:10:43,231 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2020-12-23 07:10:43,231 INFO L78 Accepts]: Start accepts. Automaton has 8 states. Word has length 40 [2020-12-23 07:10:43,232 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-12-23 07:10:43,234 INFO L225 Difference]: With dead ends: 496 [2020-12-23 07:10:43,234 INFO L226 Difference]: Without dead ends: 494 [2020-12-23 07:10:43,235 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 52 GetRequests, 34 SyntacticMatches, 0 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 82 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=90, Invalid=290, Unknown=0, NotChecked=0, Total=380 [2020-12-23 07:10:43,236 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 494 states. [2020-12-23 07:10:43,258 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 494 to 306. [2020-12-23 07:10:43,258 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 306 states. [2020-12-23 07:10:43,260 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 306 states to 306 states and 361 transitions. [2020-12-23 07:10:43,260 INFO L78 Accepts]: Start accepts. Automaton has 306 states and 361 transitions. Word has length 40 [2020-12-23 07:10:43,260 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-12-23 07:10:43,260 INFO L481 AbstractCegarLoop]: Abstraction has 306 states and 361 transitions. [2020-12-23 07:10:43,260 INFO L482 AbstractCegarLoop]: Interpolant automaton has 8 states. [2020-12-23 07:10:43,260 INFO L276 IsEmpty]: Start isEmpty. Operand 306 states and 361 transitions. [2020-12-23 07:10:43,261 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2020-12-23 07:10:43,261 INFO L414 BasicCegarLoop]: Found error trace [2020-12-23 07:10:43,261 INFO L422 BasicCegarLoop]: trace histogram [9, 9, 7, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2020-12-23 07:10:43,474 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2020-12-23 07:10:43,475 INFO L429 AbstractCegarLoop]: === Iteration 18 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-12-23 07:10:43,475 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-12-23 07:10:43,476 INFO L82 PathProgramCache]: Analyzing trace with hash -1950517015, now seen corresponding path program 1 times [2020-12-23 07:10:43,476 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-12-23 07:10:43,476 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [829277682] [2020-12-23 07:10:43,477 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-12-23 07:10:43,488 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-12-23 07:10:43,598 INFO L134 CoverageAnalysis]: Checked inductivity of 117 backedges. 0 proven. 117 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2020-12-23 07:10:43,599 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [829277682] [2020-12-23 07:10:43,599 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1659988975] [2020-12-23 07:10:43,599 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate-bitabs/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-12-23 07:10:43,652 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-12-23 07:10:43,653 INFO L263 TraceCheckSpWp]: Trace formula consists of 127 conjuncts, 12 conjunts are in the unsatisfiable core [2020-12-23 07:10:43,655 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2020-12-23 07:10:43,870 INFO L134 CoverageAnalysis]: Checked inductivity of 117 backedges. 0 proven. 117 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2020-12-23 07:10:43,871 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2020-12-23 07:10:43,871 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 22 [2020-12-23 07:10:43,871 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [445622150] [2020-12-23 07:10:43,871 INFO L461 AbstractCegarLoop]: Interpolant automaton has 23 states [2020-12-23 07:10:43,871 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-12-23 07:10:43,872 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2020-12-23 07:10:43,873 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=208, Invalid=298, Unknown=0, NotChecked=0, Total=506 [2020-12-23 07:10:43,873 INFO L87 Difference]: Start difference. First operand 306 states and 361 transitions. Second operand 23 states. [2020-12-23 07:10:44,066 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-12-23 07:10:44,067 INFO L93 Difference]: Finished difference Result 669 states and 793 transitions. [2020-12-23 07:10:44,067 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2020-12-23 07:10:44,067 INFO L78 Accepts]: Start accepts. Automaton has 23 states. Word has length 40 [2020-12-23 07:10:44,068 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-12-23 07:10:44,070 INFO L225 Difference]: With dead ends: 669 [2020-12-23 07:10:44,070 INFO L226 Difference]: Without dead ends: 439 [2020-12-23 07:10:44,071 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 51 GetRequests, 30 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 177 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=208, Invalid=298, Unknown=0, NotChecked=0, Total=506 [2020-12-23 07:10:44,072 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 439 states. [2020-12-23 07:10:44,095 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 439 to 339. [2020-12-23 07:10:44,095 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 339 states. [2020-12-23 07:10:44,096 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 339 states to 339 states and 399 transitions. [2020-12-23 07:10:44,097 INFO L78 Accepts]: Start accepts. Automaton has 339 states and 399 transitions. Word has length 40 [2020-12-23 07:10:44,097 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-12-23 07:10:44,097 INFO L481 AbstractCegarLoop]: Abstraction has 339 states and 399 transitions. [2020-12-23 07:10:44,097 INFO L482 AbstractCegarLoop]: Interpolant automaton has 23 states. [2020-12-23 07:10:44,097 INFO L276 IsEmpty]: Start isEmpty. Operand 339 states and 399 transitions. [2020-12-23 07:10:44,098 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2020-12-23 07:10:44,098 INFO L414 BasicCegarLoop]: Found error trace [2020-12-23 07:10:44,098 INFO L422 BasicCegarLoop]: trace histogram [10, 10, 8, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2020-12-23 07:10:44,311 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2020-12-23 07:10:44,312 INFO L429 AbstractCegarLoop]: === Iteration 19 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-12-23 07:10:44,313 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-12-23 07:10:44,315 INFO L82 PathProgramCache]: Analyzing trace with hash -658324379, now seen corresponding path program 2 times [2020-12-23 07:10:44,315 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-12-23 07:10:44,316 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [588843910] [2020-12-23 07:10:44,316 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-12-23 07:10:44,327 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-12-23 07:10:44,450 INFO L134 CoverageAnalysis]: Checked inductivity of 145 backedges. 0 proven. 145 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2020-12-23 07:10:44,451 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [588843910] [2020-12-23 07:10:44,451 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [866992895] [2020-12-23 07:10:44,451 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate-bitabs/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-12-23 07:10:44,496 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2020-12-23 07:10:44,497 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2020-12-23 07:10:44,497 INFO L263 TraceCheckSpWp]: Trace formula consists of 133 conjuncts, 7 conjunts are in the unsatisfiable core [2020-12-23 07:10:44,499 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2020-12-23 07:10:44,624 INFO L134 CoverageAnalysis]: Checked inductivity of 145 backedges. 0 proven. 68 refuted. 0 times theorem prover too weak. 77 trivial. 0 not checked. [2020-12-23 07:10:44,625 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2020-12-23 07:10:44,625 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 7] total 18 [2020-12-23 07:10:44,625 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2030830429] [2020-12-23 07:10:44,627 INFO L461 AbstractCegarLoop]: Interpolant automaton has 19 states [2020-12-23 07:10:44,627 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-12-23 07:10:44,627 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2020-12-23 07:10:44,628 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=130, Invalid=212, Unknown=0, NotChecked=0, Total=342 [2020-12-23 07:10:44,628 INFO L87 Difference]: Start difference. First operand 339 states and 399 transitions. Second operand 19 states. [2020-12-23 07:10:45,164 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-12-23 07:10:45,165 INFO L93 Difference]: Finished difference Result 1075 states and 1251 transitions. [2020-12-23 07:10:45,165 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2020-12-23 07:10:45,165 INFO L78 Accepts]: Start accepts. Automaton has 19 states. Word has length 43 [2020-12-23 07:10:45,166 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-12-23 07:10:45,170 INFO L225 Difference]: With dead ends: 1075 [2020-12-23 07:10:45,170 INFO L226 Difference]: Without dead ends: 821 [2020-12-23 07:10:45,171 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 75 GetRequests, 38 SyntacticMatches, 0 SemanticMatches, 37 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 349 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=486, Invalid=996, Unknown=0, NotChecked=0, Total=1482 [2020-12-23 07:10:45,173 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 821 states. [2020-12-23 07:10:45,223 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 821 to 333. [2020-12-23 07:10:45,223 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 333 states. [2020-12-23 07:10:45,224 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 333 states to 333 states and 388 transitions. [2020-12-23 07:10:45,225 INFO L78 Accepts]: Start accepts. Automaton has 333 states and 388 transitions. Word has length 43 [2020-12-23 07:10:45,225 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-12-23 07:10:45,225 INFO L481 AbstractCegarLoop]: Abstraction has 333 states and 388 transitions. [2020-12-23 07:10:45,225 INFO L482 AbstractCegarLoop]: Interpolant automaton has 19 states. [2020-12-23 07:10:45,225 INFO L276 IsEmpty]: Start isEmpty. Operand 333 states and 388 transitions. [2020-12-23 07:10:45,226 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2020-12-23 07:10:45,226 INFO L414 BasicCegarLoop]: Found error trace [2020-12-23 07:10:45,226 INFO L422 BasicCegarLoop]: trace histogram [11, 11, 8, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2020-12-23 07:10:45,438 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,14 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-12-23 07:10:45,438 INFO L429 AbstractCegarLoop]: === Iteration 20 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-12-23 07:10:45,439 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-12-23 07:10:45,439 INFO L82 PathProgramCache]: Analyzing trace with hash 1311604647, now seen corresponding path program 3 times [2020-12-23 07:10:45,439 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-12-23 07:10:45,440 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2016391358] [2020-12-23 07:10:45,440 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-12-23 07:10:45,454 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-12-23 07:10:45,604 INFO L134 CoverageAnalysis]: Checked inductivity of 176 backedges. 0 proven. 176 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2020-12-23 07:10:45,604 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2016391358] [2020-12-23 07:10:45,604 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1004646317] [2020-12-23 07:10:45,604 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 No working directory specified, using /storage/repos/ultimate-bitabs/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 15 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 15 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-12-23 07:10:45,657 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2020-12-23 07:10:45,657 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2020-12-23 07:10:45,658 INFO L263 TraceCheckSpWp]: Trace formula consists of 87 conjuncts, 15 conjunts are in the unsatisfiable core [2020-12-23 07:10:45,660 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2020-12-23 07:10:45,802 INFO L639 QuantifierPusher]: Distributing 2 conjuncts over 3 disjuncts [2020-12-23 07:10:45,826 INFO L134 CoverageAnalysis]: Checked inductivity of 176 backedges. 31 proven. 0 refuted. 0 times theorem prover too weak. 145 trivial. 0 not checked. [2020-12-23 07:10:45,826 INFO L219 FreeRefinementEngine]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2020-12-23 07:10:45,826 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [14] total 21 [2020-12-23 07:10:45,826 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [354296141] [2020-12-23 07:10:45,827 INFO L461 AbstractCegarLoop]: Interpolant automaton has 8 states [2020-12-23 07:10:45,827 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-12-23 07:10:45,827 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2020-12-23 07:10:45,828 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=110, Invalid=310, Unknown=0, NotChecked=0, Total=420 [2020-12-23 07:10:45,828 INFO L87 Difference]: Start difference. First operand 333 states and 388 transitions. Second operand 8 states. [2020-12-23 07:10:45,982 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-12-23 07:10:45,982 INFO L93 Difference]: Finished difference Result 442 states and 513 transitions. [2020-12-23 07:10:45,982 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2020-12-23 07:10:45,982 INFO L78 Accepts]: Start accepts. Automaton has 8 states. Word has length 46 [2020-12-23 07:10:45,983 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-12-23 07:10:45,985 INFO L225 Difference]: With dead ends: 442 [2020-12-23 07:10:45,985 INFO L226 Difference]: Without dead ends: 440 [2020-12-23 07:10:45,986 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 61 GetRequests, 40 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 95 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=119, Invalid=387, Unknown=0, NotChecked=0, Total=506 [2020-12-23 07:10:45,986 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 440 states. [2020-12-23 07:10:46,014 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 440 to 333. [2020-12-23 07:10:46,014 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 333 states. [2020-12-23 07:10:46,016 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 333 states to 333 states and 388 transitions. [2020-12-23 07:10:46,016 INFO L78 Accepts]: Start accepts. Automaton has 333 states and 388 transitions. Word has length 46 [2020-12-23 07:10:46,016 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-12-23 07:10:46,016 INFO L481 AbstractCegarLoop]: Abstraction has 333 states and 388 transitions. [2020-12-23 07:10:46,016 INFO L482 AbstractCegarLoop]: Interpolant automaton has 8 states. [2020-12-23 07:10:46,016 INFO L276 IsEmpty]: Start isEmpty. Operand 333 states and 388 transitions. [2020-12-23 07:10:46,017 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2020-12-23 07:10:46,017 INFO L414 BasicCegarLoop]: Found error trace [2020-12-23 07:10:46,017 INFO L422 BasicCegarLoop]: trace histogram [11, 11, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2020-12-23 07:10:46,231 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19,15 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-12-23 07:10:46,232 INFO L429 AbstractCegarLoop]: === Iteration 21 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-12-23 07:10:46,232 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-12-23 07:10:46,232 INFO L82 PathProgramCache]: Analyzing trace with hash -53609623, now seen corresponding path program 1 times [2020-12-23 07:10:46,232 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-12-23 07:10:46,233 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [130348926] [2020-12-23 07:10:46,233 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-12-23 07:10:46,243 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-12-23 07:10:46,292 INFO L134 CoverageAnalysis]: Checked inductivity of 176 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 176 trivial. 0 not checked. [2020-12-23 07:10:46,292 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [130348926] [2020-12-23 07:10:46,293 INFO L219 FreeRefinementEngine]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2020-12-23 07:10:46,293 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2020-12-23 07:10:46,293 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2082229986] [2020-12-23 07:10:46,293 INFO L461 AbstractCegarLoop]: Interpolant automaton has 5 states [2020-12-23 07:10:46,293 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-12-23 07:10:46,294 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2020-12-23 07:10:46,294 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2020-12-23 07:10:46,294 INFO L87 Difference]: Start difference. First operand 333 states and 388 transitions. Second operand 5 states. [2020-12-23 07:10:46,373 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-12-23 07:10:46,373 INFO L93 Difference]: Finished difference Result 561 states and 655 transitions. [2020-12-23 07:10:46,374 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2020-12-23 07:10:46,374 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 46 [2020-12-23 07:10:46,374 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-12-23 07:10:46,376 INFO L225 Difference]: With dead ends: 561 [2020-12-23 07:10:46,376 INFO L226 Difference]: Without dead ends: 448 [2020-12-23 07:10:46,377 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=14, Invalid=16, Unknown=0, NotChecked=0, Total=30 [2020-12-23 07:10:46,378 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 448 states. [2020-12-23 07:10:46,439 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 448 to 400. [2020-12-23 07:10:46,440 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 400 states. [2020-12-23 07:10:46,441 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 400 states to 400 states and 469 transitions. [2020-12-23 07:10:46,441 INFO L78 Accepts]: Start accepts. Automaton has 400 states and 469 transitions. Word has length 46 [2020-12-23 07:10:46,441 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-12-23 07:10:46,442 INFO L481 AbstractCegarLoop]: Abstraction has 400 states and 469 transitions. [2020-12-23 07:10:46,442 INFO L482 AbstractCegarLoop]: Interpolant automaton has 5 states. [2020-12-23 07:10:46,442 INFO L276 IsEmpty]: Start isEmpty. Operand 400 states and 469 transitions. [2020-12-23 07:10:46,443 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 88 [2020-12-23 07:10:46,443 INFO L414 BasicCegarLoop]: Found error trace [2020-12-23 07:10:46,443 INFO L422 BasicCegarLoop]: trace histogram [22, 22, 20, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2020-12-23 07:10:46,443 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable20 [2020-12-23 07:10:46,443 INFO L429 AbstractCegarLoop]: === Iteration 22 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-12-23 07:10:46,444 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-12-23 07:10:46,444 INFO L82 PathProgramCache]: Analyzing trace with hash 1284068705, now seen corresponding path program 1 times [2020-12-23 07:10:46,444 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-12-23 07:10:46,444 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [460953464] [2020-12-23 07:10:46,444 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-12-23 07:10:46,459 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-12-23 07:10:46,638 INFO L134 CoverageAnalysis]: Checked inductivity of 745 backedges. 387 proven. 176 refuted. 0 times theorem prover too weak. 182 trivial. 0 not checked. [2020-12-23 07:10:46,638 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [460953464] [2020-12-23 07:10:46,638 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2031007634] [2020-12-23 07:10:46,638 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate-bitabs/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 16 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 16 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-12-23 07:10:46,706 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-12-23 07:10:46,707 INFO L263 TraceCheckSpWp]: Trace formula consists of 220 conjuncts, 14 conjunts are in the unsatisfiable core [2020-12-23 07:10:46,715 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2020-12-23 07:10:46,973 INFO L134 CoverageAnalysis]: Checked inductivity of 745 backedges. 387 proven. 176 refuted. 0 times theorem prover too weak. 182 trivial. 0 not checked. [2020-12-23 07:10:46,973 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2020-12-23 07:10:46,973 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 26 [2020-12-23 07:10:46,973 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1259511956] [2020-12-23 07:10:46,974 INFO L461 AbstractCegarLoop]: Interpolant automaton has 27 states [2020-12-23 07:10:46,974 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-12-23 07:10:46,975 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2020-12-23 07:10:46,975 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=285, Invalid=417, Unknown=0, NotChecked=0, Total=702 [2020-12-23 07:10:46,975 INFO L87 Difference]: Start difference. First operand 400 states and 469 transitions. Second operand 27 states. [2020-12-23 07:10:47,347 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-12-23 07:10:47,347 INFO L93 Difference]: Finished difference Result 1102 states and 1266 transitions. [2020-12-23 07:10:47,348 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2020-12-23 07:10:47,348 INFO L78 Accepts]: Start accepts. Automaton has 27 states. Word has length 87 [2020-12-23 07:10:47,349 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-12-23 07:10:47,352 INFO L225 Difference]: With dead ends: 1102 [2020-12-23 07:10:47,352 INFO L226 Difference]: Without dead ends: 793 [2020-12-23 07:10:47,354 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 100 GetRequests, 75 SyntacticMatches, 0 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 261 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=285, Invalid=417, Unknown=0, NotChecked=0, Total=702 [2020-12-23 07:10:47,354 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 793 states. [2020-12-23 07:10:47,395 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 793 to 439. [2020-12-23 07:10:47,395 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 439 states. [2020-12-23 07:10:47,396 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 439 states to 439 states and 514 transitions. [2020-12-23 07:10:47,397 INFO L78 Accepts]: Start accepts. Automaton has 439 states and 514 transitions. Word has length 87 [2020-12-23 07:10:47,397 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-12-23 07:10:47,397 INFO L481 AbstractCegarLoop]: Abstraction has 439 states and 514 transitions. [2020-12-23 07:10:47,397 INFO L482 AbstractCegarLoop]: Interpolant automaton has 27 states. [2020-12-23 07:10:47,397 INFO L276 IsEmpty]: Start isEmpty. Operand 439 states and 514 transitions. [2020-12-23 07:10:47,398 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 94 [2020-12-23 07:10:47,398 INFO L414 BasicCegarLoop]: Found error trace [2020-12-23 07:10:47,399 INFO L422 BasicCegarLoop]: trace histogram [24, 24, 22, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2020-12-23 07:10:47,612 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable21 [2020-12-23 07:10:47,613 INFO L429 AbstractCegarLoop]: === Iteration 23 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-12-23 07:10:47,613 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-12-23 07:10:47,614 INFO L82 PathProgramCache]: Analyzing trace with hash -1856213775, now seen corresponding path program 2 times [2020-12-23 07:10:47,614 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-12-23 07:10:47,614 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1947158158] [2020-12-23 07:10:47,615 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-12-23 07:10:47,629 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-12-23 07:10:47,811 INFO L134 CoverageAnalysis]: Checked inductivity of 884 backedges. 458 proven. 210 refuted. 0 times theorem prover too weak. 216 trivial. 0 not checked. [2020-12-23 07:10:47,811 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1947158158] [2020-12-23 07:10:47,811 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [359356541] [2020-12-23 07:10:47,811 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate-bitabs/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 17 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 17 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-12-23 07:10:47,877 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2020-12-23 07:10:47,878 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2020-12-23 07:10:47,879 INFO L263 TraceCheckSpWp]: Trace formula consists of 232 conjuncts, 15 conjunts are in the unsatisfiable core [2020-12-23 07:10:47,881 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2020-12-23 07:10:48,192 INFO L134 CoverageAnalysis]: Checked inductivity of 884 backedges. 458 proven. 210 refuted. 0 times theorem prover too weak. 216 trivial. 0 not checked. [2020-12-23 07:10:48,192 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2020-12-23 07:10:48,192 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 15] total 28 [2020-12-23 07:10:48,193 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1851736195] [2020-12-23 07:10:48,193 INFO L461 AbstractCegarLoop]: Interpolant automaton has 29 states [2020-12-23 07:10:48,193 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-12-23 07:10:48,194 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2020-12-23 07:10:48,194 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=328, Invalid=484, Unknown=0, NotChecked=0, Total=812 [2020-12-23 07:10:48,194 INFO L87 Difference]: Start difference. First operand 439 states and 514 transitions. Second operand 29 states. [2020-12-23 07:10:48,579 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-12-23 07:10:48,579 INFO L93 Difference]: Finished difference Result 1171 states and 1346 transitions. [2020-12-23 07:10:48,580 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2020-12-23 07:10:48,580 INFO L78 Accepts]: Start accepts. Automaton has 29 states. Word has length 93 [2020-12-23 07:10:48,580 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-12-23 07:10:48,583 INFO L225 Difference]: With dead ends: 1171 [2020-12-23 07:10:48,584 INFO L226 Difference]: Without dead ends: 832 [2020-12-23 07:10:48,585 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 107 GetRequests, 80 SyntacticMatches, 0 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 309 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=328, Invalid=484, Unknown=0, NotChecked=0, Total=812 [2020-12-23 07:10:48,586 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 832 states. [2020-12-23 07:10:48,663 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 832 to 478. [2020-12-23 07:10:48,663 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 478 states. [2020-12-23 07:10:48,665 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 478 states to 478 states and 559 transitions. [2020-12-23 07:10:48,665 INFO L78 Accepts]: Start accepts. Automaton has 478 states and 559 transitions. Word has length 93 [2020-12-23 07:10:48,665 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-12-23 07:10:48,665 INFO L481 AbstractCegarLoop]: Abstraction has 478 states and 559 transitions. [2020-12-23 07:10:48,666 INFO L482 AbstractCegarLoop]: Interpolant automaton has 29 states. [2020-12-23 07:10:48,666 INFO L276 IsEmpty]: Start isEmpty. Operand 478 states and 559 transitions. [2020-12-23 07:10:48,667 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 100 [2020-12-23 07:10:48,667 INFO L414 BasicCegarLoop]: Found error trace [2020-12-23 07:10:48,667 INFO L422 BasicCegarLoop]: trace histogram [26, 26, 24, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2020-12-23 07:10:48,881 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable22,17 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-12-23 07:10:48,882 INFO L429 AbstractCegarLoop]: === Iteration 24 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-12-23 07:10:48,883 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-12-23 07:10:48,883 INFO L82 PathProgramCache]: Analyzing trace with hash -267019423, now seen corresponding path program 3 times [2020-12-23 07:10:48,883 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-12-23 07:10:48,884 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1742889336] [2020-12-23 07:10:48,884 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-12-23 07:10:48,901 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-12-23 07:10:49,109 INFO L134 CoverageAnalysis]: Checked inductivity of 1035 backedges. 535 proven. 247 refuted. 0 times theorem prover too weak. 253 trivial. 0 not checked. [2020-12-23 07:10:49,110 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1742889336] [2020-12-23 07:10:49,110 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1500374679] [2020-12-23 07:10:49,110 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 No working directory specified, using /storage/repos/ultimate-bitabs/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 18 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 18 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-12-23 07:10:49,173 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2020-12-23 07:10:49,173 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2020-12-23 07:10:49,175 INFO L263 TraceCheckSpWp]: Trace formula consists of 108 conjuncts, 28 conjunts are in the unsatisfiable core [2020-12-23 07:10:49,177 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2020-12-23 07:10:49,430 INFO L639 QuantifierPusher]: Distributing 2 conjuncts over 3 disjuncts [2020-12-23 07:10:49,478 INFO L134 CoverageAnalysis]: Checked inductivity of 1035 backedges. 37 proven. 541 refuted. 0 times theorem prover too weak. 457 trivial. 0 not checked. [2020-12-23 07:10:49,478 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2020-12-23 07:10:49,479 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 10] total 25 [2020-12-23 07:10:49,479 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1754689999] [2020-12-23 07:10:49,479 INFO L461 AbstractCegarLoop]: Interpolant automaton has 25 states [2020-12-23 07:10:49,480 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-12-23 07:10:49,480 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2020-12-23 07:10:49,480 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=144, Invalid=456, Unknown=0, NotChecked=0, Total=600 [2020-12-23 07:10:49,481 INFO L87 Difference]: Start difference. First operand 478 states and 559 transitions. Second operand 25 states. [2020-12-23 07:10:52,616 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-12-23 07:10:52,617 INFO L93 Difference]: Finished difference Result 2208 states and 2540 transitions. [2020-12-23 07:10:52,617 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 68 states. [2020-12-23 07:10:52,617 INFO L78 Accepts]: Start accepts. Automaton has 25 states. Word has length 99 [2020-12-23 07:10:52,617 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-12-23 07:10:52,625 INFO L225 Difference]: With dead ends: 2208 [2020-12-23 07:10:52,626 INFO L226 Difference]: Without dead ends: 1839 [2020-12-23 07:10:52,630 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 180 GetRequests, 92 SyntacticMatches, 0 SemanticMatches, 88 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2259 ImplicationChecksByTransitivity, 2.5s TimeCoverageRelationStatistics Valid=1728, Invalid=6282, Unknown=0, NotChecked=0, Total=8010 [2020-12-23 07:10:52,632 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1839 states. [2020-12-23 07:10:52,747 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1839 to 770. [2020-12-23 07:10:52,747 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 770 states. [2020-12-23 07:10:52,749 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 770 states to 770 states and 901 transitions. [2020-12-23 07:10:52,750 INFO L78 Accepts]: Start accepts. Automaton has 770 states and 901 transitions. Word has length 99 [2020-12-23 07:10:52,750 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-12-23 07:10:52,750 INFO L481 AbstractCegarLoop]: Abstraction has 770 states and 901 transitions. [2020-12-23 07:10:52,750 INFO L482 AbstractCegarLoop]: Interpolant automaton has 25 states. [2020-12-23 07:10:52,750 INFO L276 IsEmpty]: Start isEmpty. Operand 770 states and 901 transitions. [2020-12-23 07:10:52,752 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 106 [2020-12-23 07:10:52,752 INFO L414 BasicCegarLoop]: Found error trace [2020-12-23 07:10:52,752 INFO L422 BasicCegarLoop]: trace histogram [28, 28, 24, 4, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2020-12-23 07:10:52,966 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 18 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable23 [2020-12-23 07:10:52,967 INFO L429 AbstractCegarLoop]: === Iteration 25 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-12-23 07:10:52,967 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-12-23 07:10:52,968 INFO L82 PathProgramCache]: Analyzing trace with hash -111346257, now seen corresponding path program 1 times [2020-12-23 07:10:52,968 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-12-23 07:10:52,968 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [233396155] [2020-12-23 07:10:52,968 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-12-23 07:10:52,986 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-12-23 07:10:53,203 INFO L134 CoverageAnalysis]: Checked inductivity of 1198 backedges. 49 proven. 861 refuted. 0 times theorem prover too weak. 288 trivial. 0 not checked. [2020-12-23 07:10:53,204 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [233396155] [2020-12-23 07:10:53,204 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [109483330] [2020-12-23 07:10:53,204 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate-bitabs/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 19 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 19 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-12-23 07:10:53,282 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-12-23 07:10:53,283 INFO L263 TraceCheckSpWp]: Trace formula consists of 255 conjuncts, 17 conjunts are in the unsatisfiable core [2020-12-23 07:10:53,286 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2020-12-23 07:10:53,640 INFO L134 CoverageAnalysis]: Checked inductivity of 1198 backedges. 618 proven. 287 refuted. 0 times theorem prover too weak. 293 trivial. 0 not checked. [2020-12-23 07:10:53,640 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2020-12-23 07:10:53,640 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 17] total 32 [2020-12-23 07:10:53,641 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [745981928] [2020-12-23 07:10:53,642 INFO L461 AbstractCegarLoop]: Interpolant automaton has 33 states [2020-12-23 07:10:53,642 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-12-23 07:10:53,643 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2020-12-23 07:10:53,644 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=423, Invalid=633, Unknown=0, NotChecked=0, Total=1056 [2020-12-23 07:10:53,644 INFO L87 Difference]: Start difference. First operand 770 states and 901 transitions. Second operand 33 states. [2020-12-23 07:10:54,041 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-12-23 07:10:54,041 INFO L93 Difference]: Finished difference Result 1968 states and 2264 transitions. [2020-12-23 07:10:54,042 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2020-12-23 07:10:54,042 INFO L78 Accepts]: Start accepts. Automaton has 33 states. Word has length 105 [2020-12-23 07:10:54,042 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-12-23 07:10:54,046 INFO L225 Difference]: With dead ends: 1968 [2020-12-23 07:10:54,046 INFO L226 Difference]: Without dead ends: 1316 [2020-12-23 07:10:54,047 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 121 GetRequests, 90 SyntacticMatches, 0 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 417 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=423, Invalid=633, Unknown=0, NotChecked=0, Total=1056 [2020-12-23 07:10:54,049 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1316 states. [2020-12-23 07:10:54,160 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1316 to 809. [2020-12-23 07:10:54,160 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 809 states. [2020-12-23 07:10:54,162 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 809 states to 809 states and 946 transitions. [2020-12-23 07:10:54,162 INFO L78 Accepts]: Start accepts. Automaton has 809 states and 946 transitions. Word has length 105 [2020-12-23 07:10:54,162 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-12-23 07:10:54,162 INFO L481 AbstractCegarLoop]: Abstraction has 809 states and 946 transitions. [2020-12-23 07:10:54,163 INFO L482 AbstractCegarLoop]: Interpolant automaton has 33 states. [2020-12-23 07:10:54,163 INFO L276 IsEmpty]: Start isEmpty. Operand 809 states and 946 transitions. [2020-12-23 07:10:54,164 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 112 [2020-12-23 07:10:54,164 INFO L414 BasicCegarLoop]: Found error trace [2020-12-23 07:10:54,165 INFO L422 BasicCegarLoop]: trace histogram [30, 30, 26, 4, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2020-12-23 07:10:54,379 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 19 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable24 [2020-12-23 07:10:54,380 INFO L429 AbstractCegarLoop]: === Iteration 26 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-12-23 07:10:54,380 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-12-23 07:10:54,381 INFO L82 PathProgramCache]: Analyzing trace with hash 802849635, now seen corresponding path program 2 times [2020-12-23 07:10:54,381 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-12-23 07:10:54,382 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2106649009] [2020-12-23 07:10:54,382 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-12-23 07:10:54,398 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-12-23 07:10:54,639 INFO L134 CoverageAnalysis]: Checked inductivity of 1373 backedges. 52 proven. 990 refuted. 0 times theorem prover too weak. 331 trivial. 0 not checked. [2020-12-23 07:10:54,639 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2106649009] [2020-12-23 07:10:54,640 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [495704359] [2020-12-23 07:10:54,640 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate-bitabs/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 20 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 20 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-12-23 07:10:54,724 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2020-12-23 07:10:54,724 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2020-12-23 07:10:54,725 INFO L263 TraceCheckSpWp]: Trace formula consists of 267 conjuncts, 18 conjunts are in the unsatisfiable core [2020-12-23 07:10:54,727 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2020-12-23 07:10:55,152 INFO L134 CoverageAnalysis]: Checked inductivity of 1373 backedges. 707 proven. 330 refuted. 0 times theorem prover too weak. 336 trivial. 0 not checked. [2020-12-23 07:10:55,152 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2020-12-23 07:10:55,153 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 18] total 34 [2020-12-23 07:10:55,153 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1896781302] [2020-12-23 07:10:55,153 INFO L461 AbstractCegarLoop]: Interpolant automaton has 35 states [2020-12-23 07:10:55,153 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-12-23 07:10:55,154 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 35 interpolants. [2020-12-23 07:10:55,154 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=475, Invalid=715, Unknown=0, NotChecked=0, Total=1190 [2020-12-23 07:10:55,154 INFO L87 Difference]: Start difference. First operand 809 states and 946 transitions. Second operand 35 states. [2020-12-23 07:10:55,809 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-12-23 07:10:55,809 INFO L93 Difference]: Finished difference Result 2078 states and 2393 transitions. [2020-12-23 07:10:55,810 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2020-12-23 07:10:55,810 INFO L78 Accepts]: Start accepts. Automaton has 35 states. Word has length 111 [2020-12-23 07:10:55,810 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-12-23 07:10:55,815 INFO L225 Difference]: With dead ends: 2078 [2020-12-23 07:10:55,815 INFO L226 Difference]: Without dead ends: 1396 [2020-12-23 07:10:55,817 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 128 GetRequests, 95 SyntacticMatches, 0 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 477 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=475, Invalid=715, Unknown=0, NotChecked=0, Total=1190 [2020-12-23 07:10:55,819 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1396 states. [2020-12-23 07:10:55,937 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1396 to 866. [2020-12-23 07:10:55,937 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 866 states. [2020-12-23 07:10:55,945 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 866 states to 866 states and 1012 transitions. [2020-12-23 07:10:55,945 INFO L78 Accepts]: Start accepts. Automaton has 866 states and 1012 transitions. Word has length 111 [2020-12-23 07:10:55,945 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-12-23 07:10:55,945 INFO L481 AbstractCegarLoop]: Abstraction has 866 states and 1012 transitions. [2020-12-23 07:10:55,945 INFO L482 AbstractCegarLoop]: Interpolant automaton has 35 states. [2020-12-23 07:10:55,945 INFO L276 IsEmpty]: Start isEmpty. Operand 866 states and 1012 transitions. [2020-12-23 07:10:55,952 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 118 [2020-12-23 07:10:55,953 INFO L414 BasicCegarLoop]: Found error trace [2020-12-23 07:10:55,953 INFO L422 BasicCegarLoop]: trace histogram [32, 32, 28, 4, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2020-12-23 07:10:56,168 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 20 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable25 [2020-12-23 07:10:56,169 INFO L429 AbstractCegarLoop]: === Iteration 27 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-12-23 07:10:56,169 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-12-23 07:10:56,170 INFO L82 PathProgramCache]: Analyzing trace with hash -780287697, now seen corresponding path program 3 times [2020-12-23 07:10:56,170 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-12-23 07:10:56,170 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [55081917] [2020-12-23 07:10:56,171 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-12-23 07:10:56,191 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-12-23 07:10:56,480 INFO L134 CoverageAnalysis]: Checked inductivity of 1560 backedges. 55 proven. 1128 refuted. 0 times theorem prover too weak. 377 trivial. 0 not checked. [2020-12-23 07:10:56,480 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [55081917] [2020-12-23 07:10:56,480 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [31961304] [2020-12-23 07:10:56,480 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 No working directory specified, using /storage/repos/ultimate-bitabs/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 21 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 21 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-12-23 07:10:56,538 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2020-12-23 07:10:56,539 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2020-12-23 07:10:56,540 INFO L263 TraceCheckSpWp]: Trace formula consists of 111 conjuncts, 9 conjunts are in the unsatisfiable core [2020-12-23 07:10:56,542 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2020-12-23 07:10:56,774 INFO L134 CoverageAnalysis]: Checked inductivity of 1560 backedges. 807 proven. 47 refuted. 0 times theorem prover too weak. 706 trivial. 0 not checked. [2020-12-23 07:10:56,774 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2020-12-23 07:10:56,774 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 7] total 25 [2020-12-23 07:10:56,774 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [255280930] [2020-12-23 07:10:56,775 INFO L461 AbstractCegarLoop]: Interpolant automaton has 25 states [2020-12-23 07:10:56,775 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-12-23 07:10:56,776 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2020-12-23 07:10:56,776 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=185, Invalid=415, Unknown=0, NotChecked=0, Total=600 [2020-12-23 07:10:56,776 INFO L87 Difference]: Start difference. First operand 866 states and 1012 transitions. Second operand 25 states. [2020-12-23 07:10:59,304 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-12-23 07:10:59,304 INFO L93 Difference]: Finished difference Result 2428 states and 2841 transitions. [2020-12-23 07:10:59,305 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 62 states. [2020-12-23 07:10:59,305 INFO L78 Accepts]: Start accepts. Automaton has 25 states. Word has length 117 [2020-12-23 07:10:59,305 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-12-23 07:10:59,313 INFO L225 Difference]: With dead ends: 2428 [2020-12-23 07:10:59,313 INFO L226 Difference]: Without dead ends: 1698 [2020-12-23 07:10:59,316 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 194 GetRequests, 113 SyntacticMatches, 0 SemanticMatches, 81 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1839 ImplicationChecksByTransitivity, 1.8s TimeCoverageRelationStatistics Valid=1816, Invalid=4990, Unknown=0, NotChecked=0, Total=6806 [2020-12-23 07:10:59,318 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1698 states. [2020-12-23 07:10:59,485 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1698 to 1132. [2020-12-23 07:10:59,485 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1132 states. [2020-12-23 07:10:59,488 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1132 states to 1132 states and 1303 transitions. [2020-12-23 07:10:59,488 INFO L78 Accepts]: Start accepts. Automaton has 1132 states and 1303 transitions. Word has length 117 [2020-12-23 07:10:59,488 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-12-23 07:10:59,488 INFO L481 AbstractCegarLoop]: Abstraction has 1132 states and 1303 transitions. [2020-12-23 07:10:59,488 INFO L482 AbstractCegarLoop]: Interpolant automaton has 25 states. [2020-12-23 07:10:59,489 INFO L276 IsEmpty]: Start isEmpty. Operand 1132 states and 1303 transitions. [2020-12-23 07:10:59,491 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 124 [2020-12-23 07:10:59,491 INFO L414 BasicCegarLoop]: Found error trace [2020-12-23 07:10:59,491 INFO L422 BasicCegarLoop]: trace histogram [34, 34, 20, 14, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2020-12-23 07:10:59,706 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 21 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable26 [2020-12-23 07:10:59,707 INFO L429 AbstractCegarLoop]: === Iteration 28 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-12-23 07:10:59,707 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-12-23 07:10:59,708 INFO L82 PathProgramCache]: Analyzing trace with hash 840591843, now seen corresponding path program 4 times [2020-12-23 07:10:59,708 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-12-23 07:10:59,709 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [941158347] [2020-12-23 07:10:59,709 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-12-23 07:10:59,727 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-12-23 07:10:59,766 INFO L134 CoverageAnalysis]: Checked inductivity of 1759 backedges. 984 proven. 0 refuted. 0 times theorem prover too weak. 775 trivial. 0 not checked. [2020-12-23 07:10:59,767 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [941158347] [2020-12-23 07:10:59,767 INFO L219 FreeRefinementEngine]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2020-12-23 07:10:59,767 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2020-12-23 07:10:59,767 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [241205059] [2020-12-23 07:10:59,767 INFO L461 AbstractCegarLoop]: Interpolant automaton has 5 states [2020-12-23 07:10:59,768 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-12-23 07:10:59,768 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2020-12-23 07:10:59,768 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2020-12-23 07:10:59,768 INFO L87 Difference]: Start difference. First operand 1132 states and 1303 transitions. Second operand 5 states. [2020-12-23 07:10:59,950 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-12-23 07:10:59,950 INFO L93 Difference]: Finished difference Result 1815 states and 2023 transitions. [2020-12-23 07:10:59,951 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2020-12-23 07:10:59,951 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 123 [2020-12-23 07:10:59,951 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-12-23 07:10:59,956 INFO L225 Difference]: With dead ends: 1815 [2020-12-23 07:10:59,956 INFO L226 Difference]: Without dead ends: 1604 [2020-12-23 07:10:59,957 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2020-12-23 07:10:59,959 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1604 states. [2020-12-23 07:11:00,085 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1604 to 1150. [2020-12-23 07:11:00,085 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1150 states. [2020-12-23 07:11:00,087 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1150 states to 1150 states and 1327 transitions. [2020-12-23 07:11:00,087 INFO L78 Accepts]: Start accepts. Automaton has 1150 states and 1327 transitions. Word has length 123 [2020-12-23 07:11:00,087 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-12-23 07:11:00,088 INFO L481 AbstractCegarLoop]: Abstraction has 1150 states and 1327 transitions. [2020-12-23 07:11:00,088 INFO L482 AbstractCegarLoop]: Interpolant automaton has 5 states. [2020-12-23 07:11:00,088 INFO L276 IsEmpty]: Start isEmpty. Operand 1150 states and 1327 transitions. [2020-12-23 07:11:00,090 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 124 [2020-12-23 07:11:00,090 INFO L414 BasicCegarLoop]: Found error trace [2020-12-23 07:11:00,090 INFO L422 BasicCegarLoop]: trace histogram [34, 34, 19, 15, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2020-12-23 07:11:00,090 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable27 [2020-12-23 07:11:00,090 INFO L429 AbstractCegarLoop]: === Iteration 29 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-12-23 07:11:00,091 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-12-23 07:11:00,091 INFO L82 PathProgramCache]: Analyzing trace with hash -1273355935, now seen corresponding path program 5 times [2020-12-23 07:11:00,091 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-12-23 07:11:00,091 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1805587457] [2020-12-23 07:11:00,091 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-12-23 07:11:00,122 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-12-23 07:11:00,446 INFO L134 CoverageAnalysis]: Checked inductivity of 1759 backedges. 903 proven. 425 refuted. 0 times theorem prover too weak. 431 trivial. 0 not checked. [2020-12-23 07:11:00,446 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1805587457] [2020-12-23 07:11:00,447 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1114067686] [2020-12-23 07:11:00,447 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate-bitabs/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 22 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 22 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-12-23 07:11:00,526 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 19 check-sat command(s) [2020-12-23 07:11:00,526 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2020-12-23 07:11:00,528 INFO L263 TraceCheckSpWp]: Trace formula consists of 261 conjuncts, 22 conjunts are in the unsatisfiable core [2020-12-23 07:11:00,529 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2020-12-23 07:11:01,316 INFO L134 CoverageAnalysis]: Checked inductivity of 1759 backedges. 1159 proven. 338 refuted. 0 times theorem prover too weak. 262 trivial. 0 not checked. [2020-12-23 07:11:01,317 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2020-12-23 07:11:01,317 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 23] total 42 [2020-12-23 07:11:01,317 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [181320346] [2020-12-23 07:11:01,318 INFO L461 AbstractCegarLoop]: Interpolant automaton has 42 states [2020-12-23 07:11:01,318 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-12-23 07:11:01,318 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 42 interpolants. [2020-12-23 07:11:01,319 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=381, Invalid=1341, Unknown=0, NotChecked=0, Total=1722 [2020-12-23 07:11:01,319 INFO L87 Difference]: Start difference. First operand 1150 states and 1327 transitions. Second operand 42 states. [2020-12-23 07:11:03,816 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-12-23 07:11:03,816 INFO L93 Difference]: Finished difference Result 2896 states and 3293 transitions. [2020-12-23 07:11:03,817 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 58 states. [2020-12-23 07:11:03,817 INFO L78 Accepts]: Start accepts. Automaton has 42 states. Word has length 123 [2020-12-23 07:11:03,817 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-12-23 07:11:03,825 INFO L225 Difference]: With dead ends: 2896 [2020-12-23 07:11:03,825 INFO L226 Difference]: Without dead ends: 1893 [2020-12-23 07:11:03,830 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 197 GetRequests, 103 SyntacticMatches, 0 SemanticMatches, 94 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2477 ImplicationChecksByTransitivity, 2.3s TimeCoverageRelationStatistics Valid=2087, Invalid=7033, Unknown=0, NotChecked=0, Total=9120 [2020-12-23 07:11:03,832 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1893 states. [2020-12-23 07:11:03,988 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1893 to 1123. [2020-12-23 07:11:03,988 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1123 states. [2020-12-23 07:11:03,991 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1123 states to 1123 states and 1285 transitions. [2020-12-23 07:11:03,991 INFO L78 Accepts]: Start accepts. Automaton has 1123 states and 1285 transitions. Word has length 123 [2020-12-23 07:11:03,992 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-12-23 07:11:03,992 INFO L481 AbstractCegarLoop]: Abstraction has 1123 states and 1285 transitions. [2020-12-23 07:11:03,992 INFO L482 AbstractCegarLoop]: Interpolant automaton has 42 states. [2020-12-23 07:11:03,992 INFO L276 IsEmpty]: Start isEmpty. Operand 1123 states and 1285 transitions. [2020-12-23 07:11:03,994 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 130 [2020-12-23 07:11:03,994 INFO L414 BasicCegarLoop]: Found error trace [2020-12-23 07:11:03,994 INFO L422 BasicCegarLoop]: trace histogram [36, 36, 21, 15, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2020-12-23 07:11:04,207 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 22 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable28 [2020-12-23 07:11:04,208 INFO L429 AbstractCegarLoop]: === Iteration 30 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-12-23 07:11:04,209 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-12-23 07:11:04,209 INFO L82 PathProgramCache]: Analyzing trace with hash 1151168365, now seen corresponding path program 6 times [2020-12-23 07:11:04,209 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-12-23 07:11:04,210 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [709519771] [2020-12-23 07:11:04,210 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-12-23 07:11:04,237 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-12-23 07:11:04,568 INFO L134 CoverageAnalysis]: Checked inductivity of 1970 backedges. 1010 proven. 477 refuted. 0 times theorem prover too weak. 483 trivial. 0 not checked. [2020-12-23 07:11:04,568 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [709519771] [2020-12-23 07:11:04,568 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [771615374] [2020-12-23 07:11:04,568 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE No working directory specified, using /storage/repos/ultimate-bitabs/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 23 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 23 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-12-23 07:11:04,616 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 3 check-sat command(s) [2020-12-23 07:11:04,617 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2020-12-23 07:11:04,618 INFO L263 TraceCheckSpWp]: Trace formula consists of 107 conjuncts, 24 conjunts are in the unsatisfiable core [2020-12-23 07:11:04,621 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2020-12-23 07:11:04,936 INFO L639 QuantifierPusher]: Distributing 2 conjuncts over 3 disjuncts [2020-12-23 07:11:05,007 INFO L134 CoverageAnalysis]: Checked inductivity of 1970 backedges. 228 proven. 1027 refuted. 0 times theorem prover too weak. 715 trivial. 0 not checked. [2020-12-23 07:11:05,008 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2020-12-23 07:11:05,008 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 9] total 29 [2020-12-23 07:11:05,008 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1458532719] [2020-12-23 07:11:05,011 INFO L461 AbstractCegarLoop]: Interpolant automaton has 29 states [2020-12-23 07:11:05,011 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-12-23 07:11:05,011 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2020-12-23 07:11:05,012 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=230, Invalid=582, Unknown=0, NotChecked=0, Total=812 [2020-12-23 07:11:05,012 INFO L87 Difference]: Start difference. First operand 1123 states and 1285 transitions. Second operand 29 states. [2020-12-23 07:11:09,887 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-12-23 07:11:09,887 INFO L93 Difference]: Finished difference Result 2474 states and 2859 transitions. [2020-12-23 07:11:09,888 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 106 states. [2020-12-23 07:11:09,888 INFO L78 Accepts]: Start accepts. Automaton has 29 states. Word has length 129 [2020-12-23 07:11:09,888 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-12-23 07:11:09,893 INFO L225 Difference]: With dead ends: 2474 [2020-12-23 07:11:09,893 INFO L226 Difference]: Without dead ends: 1496 [2020-12-23 07:11:09,900 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 251 GetRequests, 122 SyntacticMatches, 0 SemanticMatches, 129 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5530 ImplicationChecksByTransitivity, 4.0s TimeCoverageRelationStatistics Valid=3495, Invalid=13535, Unknown=0, NotChecked=0, Total=17030 [2020-12-23 07:11:09,901 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1496 states. [2020-12-23 07:11:10,039 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1496 to 1254. [2020-12-23 07:11:10,039 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1254 states. [2020-12-23 07:11:10,042 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1254 states to 1254 states and 1444 transitions. [2020-12-23 07:11:10,042 INFO L78 Accepts]: Start accepts. Automaton has 1254 states and 1444 transitions. Word has length 129 [2020-12-23 07:11:10,043 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-12-23 07:11:10,043 INFO L481 AbstractCegarLoop]: Abstraction has 1254 states and 1444 transitions. [2020-12-23 07:11:10,043 INFO L482 AbstractCegarLoop]: Interpolant automaton has 29 states. [2020-12-23 07:11:10,043 INFO L276 IsEmpty]: Start isEmpty. Operand 1254 states and 1444 transitions. [2020-12-23 07:11:10,045 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 139 [2020-12-23 07:11:10,045 INFO L414 BasicCegarLoop]: Found error trace [2020-12-23 07:11:10,046 INFO L422 BasicCegarLoop]: trace histogram [39, 39, 37, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2020-12-23 07:11:10,259 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable29,23 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-12-23 07:11:10,260 INFO L429 AbstractCegarLoop]: === Iteration 31 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-12-23 07:11:10,260 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-12-23 07:11:10,261 INFO L82 PathProgramCache]: Analyzing trace with hash -2144366173, now seen corresponding path program 1 times [2020-12-23 07:11:10,261 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-12-23 07:11:10,261 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [530537707] [2020-12-23 07:11:10,261 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-12-23 07:11:10,283 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-12-23 07:11:10,657 INFO L134 CoverageAnalysis]: Checked inductivity of 2309 backedges. 1182 proven. 590 refuted. 0 times theorem prover too weak. 537 trivial. 0 not checked. [2020-12-23 07:11:10,657 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [530537707] [2020-12-23 07:11:10,657 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [535194409] [2020-12-23 07:11:10,657 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate-bitabs/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 24 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 24 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-12-23 07:11:10,727 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-12-23 07:11:10,728 INFO L263 TraceCheckSpWp]: Trace formula consists of 258 conjuncts, 23 conjunts are in the unsatisfiable core [2020-12-23 07:11:10,731 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2020-12-23 07:11:11,442 INFO L134 CoverageAnalysis]: Checked inductivity of 2309 backedges. 1181 proven. 590 refuted. 0 times theorem prover too weak. 538 trivial. 0 not checked. [2020-12-23 07:11:11,442 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2020-12-23 07:11:11,442 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [24, 23] total 45 [2020-12-23 07:11:11,442 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [859132295] [2020-12-23 07:11:11,443 INFO L461 AbstractCegarLoop]: Interpolant automaton has 46 states [2020-12-23 07:11:11,443 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-12-23 07:11:11,444 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 46 interpolants. [2020-12-23 07:11:11,444 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=741, Invalid=1329, Unknown=0, NotChecked=0, Total=2070 [2020-12-23 07:11:11,444 INFO L87 Difference]: Start difference. First operand 1254 states and 1444 transitions. Second operand 46 states. [2020-12-23 07:11:12,771 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-12-23 07:11:12,771 INFO L93 Difference]: Finished difference Result 2876 states and 3425 transitions. [2020-12-23 07:11:12,771 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 52 states. [2020-12-23 07:11:12,771 INFO L78 Accepts]: Start accepts. Automaton has 46 states. Word has length 138 [2020-12-23 07:11:12,771 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-12-23 07:11:12,777 INFO L225 Difference]: With dead ends: 2876 [2020-12-23 07:11:12,777 INFO L226 Difference]: Without dead ends: 1781 [2020-12-23 07:11:12,779 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 189 GetRequests, 117 SyntacticMatches, 0 SemanticMatches, 72 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1529 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=1654, Invalid=3748, Unknown=0, NotChecked=0, Total=5402 [2020-12-23 07:11:12,780 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1781 states. [2020-12-23 07:11:12,938 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1781 to 1496. [2020-12-23 07:11:12,938 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1496 states. [2020-12-23 07:11:12,941 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1496 states to 1496 states and 1766 transitions. [2020-12-23 07:11:12,941 INFO L78 Accepts]: Start accepts. Automaton has 1496 states and 1766 transitions. Word has length 138 [2020-12-23 07:11:12,942 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-12-23 07:11:12,942 INFO L481 AbstractCegarLoop]: Abstraction has 1496 states and 1766 transitions. [2020-12-23 07:11:12,942 INFO L482 AbstractCegarLoop]: Interpolant automaton has 46 states. [2020-12-23 07:11:12,942 INFO L276 IsEmpty]: Start isEmpty. Operand 1496 states and 1766 transitions. [2020-12-23 07:11:12,944 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 148 [2020-12-23 07:11:12,944 INFO L414 BasicCegarLoop]: Found error trace [2020-12-23 07:11:12,945 INFO L422 BasicCegarLoop]: trace histogram [42, 42, 40, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2020-12-23 07:11:13,159 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 24 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable30 [2020-12-23 07:11:13,160 INFO L429 AbstractCegarLoop]: === Iteration 32 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-12-23 07:11:13,160 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-12-23 07:11:13,161 INFO L82 PathProgramCache]: Analyzing trace with hash 297433953, now seen corresponding path program 2 times [2020-12-23 07:11:13,161 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-12-23 07:11:13,161 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1056404736] [2020-12-23 07:11:13,162 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-12-23 07:11:13,183 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-12-23 07:11:13,609 INFO L134 CoverageAnalysis]: Checked inductivity of 2675 backedges. 1368 proven. 651 refuted. 0 times theorem prover too weak. 656 trivial. 0 not checked. [2020-12-23 07:11:13,609 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1056404736] [2020-12-23 07:11:13,610 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [871956561] [2020-12-23 07:11:13,610 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate-bitabs/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 25 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 25 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-12-23 07:11:13,680 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2020-12-23 07:11:13,680 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2020-12-23 07:11:13,681 INFO L263 TraceCheckSpWp]: Trace formula consists of 270 conjuncts, 25 conjunts are in the unsatisfiable core [2020-12-23 07:11:13,683 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2020-12-23 07:11:14,440 INFO L134 CoverageAnalysis]: Checked inductivity of 2675 backedges. 6 proven. 1975 refuted. 0 times theorem prover too weak. 694 trivial. 0 not checked. [2020-12-23 07:11:14,441 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2020-12-23 07:11:14,441 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [25, 25] total 48 [2020-12-23 07:11:14,441 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [21548714] [2020-12-23 07:11:14,442 INFO L461 AbstractCegarLoop]: Interpolant automaton has 49 states [2020-12-23 07:11:14,442 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-12-23 07:11:14,442 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 49 interpolants. [2020-12-23 07:11:14,443 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=791, Invalid=1561, Unknown=0, NotChecked=0, Total=2352 [2020-12-23 07:11:14,443 INFO L87 Difference]: Start difference. First operand 1496 states and 1766 transitions. Second operand 49 states. [2020-12-23 07:11:15,543 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-12-23 07:11:15,544 INFO L93 Difference]: Finished difference Result 2748 states and 3281 transitions. [2020-12-23 07:11:15,544 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 47 states. [2020-12-23 07:11:15,544 INFO L78 Accepts]: Start accepts. Automaton has 49 states. Word has length 147 [2020-12-23 07:11:15,549 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-12-23 07:11:15,557 INFO L225 Difference]: With dead ends: 2748 [2020-12-23 07:11:15,557 INFO L226 Difference]: Without dead ends: 1869 [2020-12-23 07:11:15,559 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 193 GetRequests, 124 SyntacticMatches, 0 SemanticMatches, 69 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1486 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=1575, Invalid=3395, Unknown=0, NotChecked=0, Total=4970 [2020-12-23 07:11:15,561 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1869 states. [2020-12-23 07:11:15,695 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1869 to 1506. [2020-12-23 07:11:15,696 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1506 states. [2020-12-23 07:11:15,699 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1506 states to 1506 states and 1783 transitions. [2020-12-23 07:11:15,699 INFO L78 Accepts]: Start accepts. Automaton has 1506 states and 1783 transitions. Word has length 147 [2020-12-23 07:11:15,699 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-12-23 07:11:15,700 INFO L481 AbstractCegarLoop]: Abstraction has 1506 states and 1783 transitions. [2020-12-23 07:11:15,700 INFO L482 AbstractCegarLoop]: Interpolant automaton has 49 states. [2020-12-23 07:11:15,700 INFO L276 IsEmpty]: Start isEmpty. Operand 1506 states and 1783 transitions. [2020-12-23 07:11:15,702 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 148 [2020-12-23 07:11:15,702 INFO L414 BasicCegarLoop]: Found error trace [2020-12-23 07:11:15,703 INFO L422 BasicCegarLoop]: trace histogram [42, 42, 42, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2020-12-23 07:11:15,916 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable31,25 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-12-23 07:11:15,917 INFO L429 AbstractCegarLoop]: === Iteration 33 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-12-23 07:11:15,917 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-12-23 07:11:15,918 INFO L82 PathProgramCache]: Analyzing trace with hash -758927133, now seen corresponding path program 1 times [2020-12-23 07:11:15,918 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-12-23 07:11:15,918 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1222451442] [2020-12-23 07:11:15,918 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-12-23 07:11:15,934 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-12-23 07:11:16,031 INFO L134 CoverageAnalysis]: Checked inductivity of 2675 backedges. 2 proven. 1371 refuted. 0 times theorem prover too weak. 1302 trivial. 0 not checked. [2020-12-23 07:11:16,032 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1222451442] [2020-12-23 07:11:16,032 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [936413949] [2020-12-23 07:11:16,032 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate-bitabs/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 26 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 26 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-12-23 07:11:16,138 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-12-23 07:11:16,140 INFO L263 TraceCheckSpWp]: Trace formula consists of 273 conjuncts, 24 conjunts are in the unsatisfiable core [2020-12-23 07:11:16,144 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2020-12-23 07:11:16,806 INFO L134 CoverageAnalysis]: Checked inductivity of 2675 backedges. 1367 proven. 651 refuted. 0 times theorem prover too weak. 657 trivial. 0 not checked. [2020-12-23 07:11:16,806 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2020-12-23 07:11:16,806 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 24] total 27 [2020-12-23 07:11:16,807 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [146542744] [2020-12-23 07:11:16,807 INFO L461 AbstractCegarLoop]: Interpolant automaton has 28 states [2020-12-23 07:11:16,807 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-12-23 07:11:16,808 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2020-12-23 07:11:16,808 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=310, Invalid=446, Unknown=0, NotChecked=0, Total=756 [2020-12-23 07:11:16,808 INFO L87 Difference]: Start difference. First operand 1506 states and 1783 transitions. Second operand 28 states. [2020-12-23 07:11:19,759 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-12-23 07:11:19,759 INFO L93 Difference]: Finished difference Result 3583 states and 4220 transitions. [2020-12-23 07:11:19,759 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 94 states. [2020-12-23 07:11:19,760 INFO L78 Accepts]: Start accepts. Automaton has 28 states. Word has length 147 [2020-12-23 07:11:19,760 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-12-23 07:11:19,768 INFO L225 Difference]: With dead ends: 3583 [2020-12-23 07:11:19,768 INFO L226 Difference]: Without dead ends: 2342 [2020-12-23 07:11:19,770 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 219 GetRequests, 125 SyntacticMatches, 0 SemanticMatches, 94 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2346 ImplicationChecksByTransitivity, 2.8s TimeCoverageRelationStatistics Valid=2973, Invalid=6147, Unknown=0, NotChecked=0, Total=9120 [2020-12-23 07:11:19,772 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2342 states. [2020-12-23 07:11:19,912 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2342 to 1721. [2020-12-23 07:11:19,912 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1721 states. [2020-12-23 07:11:19,914 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1721 states to 1721 states and 2031 transitions. [2020-12-23 07:11:19,914 INFO L78 Accepts]: Start accepts. Automaton has 1721 states and 2031 transitions. Word has length 147 [2020-12-23 07:11:19,915 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-12-23 07:11:19,915 INFO L481 AbstractCegarLoop]: Abstraction has 1721 states and 2031 transitions. [2020-12-23 07:11:19,915 INFO L482 AbstractCegarLoop]: Interpolant automaton has 28 states. [2020-12-23 07:11:19,915 INFO L276 IsEmpty]: Start isEmpty. Operand 1721 states and 2031 transitions. [2020-12-23 07:11:19,917 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 154 [2020-12-23 07:11:19,917 INFO L414 BasicCegarLoop]: Found error trace [2020-12-23 07:11:19,917 INFO L422 BasicCegarLoop]: trace histogram [44, 44, 42, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2020-12-23 07:11:20,130 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 26 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable32 [2020-12-23 07:11:20,131 INFO L429 AbstractCegarLoop]: === Iteration 34 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-12-23 07:11:20,131 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-12-23 07:11:20,132 INFO L82 PathProgramCache]: Analyzing trace with hash -1034830995, now seen corresponding path program 3 times [2020-12-23 07:11:20,132 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-12-23 07:11:20,133 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [462518089] [2020-12-23 07:11:20,133 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-12-23 07:11:20,155 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-12-23 07:11:20,612 INFO L134 CoverageAnalysis]: Checked inductivity of 2934 backedges. 1499 proven. 715 refuted. 0 times theorem prover too weak. 720 trivial. 0 not checked. [2020-12-23 07:11:20,613 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [462518089] [2020-12-23 07:11:20,613 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [912542251] [2020-12-23 07:11:20,613 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 No working directory specified, using /storage/repos/ultimate-bitabs/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 27 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 27 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-12-23 07:11:20,660 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 2 check-sat command(s) [2020-12-23 07:11:20,660 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2020-12-23 07:11:20,661 INFO L263 TraceCheckSpWp]: Trace formula consists of 104 conjuncts, 26 conjunts are in the unsatisfiable core [2020-12-23 07:11:20,663 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2020-12-23 07:11:21,210 INFO L134 CoverageAnalysis]: Checked inductivity of 2934 backedges. 0 proven. 1504 refuted. 0 times theorem prover too weak. 1430 trivial. 0 not checked. [2020-12-23 07:11:21,210 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2020-12-23 07:11:21,210 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [26, 8] total 33 [2020-12-23 07:11:21,210 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1811243674] [2020-12-23 07:11:21,211 INFO L461 AbstractCegarLoop]: Interpolant automaton has 34 states [2020-12-23 07:11:21,211 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-12-23 07:11:21,211 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 34 interpolants. [2020-12-23 07:11:21,211 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=308, Invalid=814, Unknown=0, NotChecked=0, Total=1122 [2020-12-23 07:11:21,211 INFO L87 Difference]: Start difference. First operand 1721 states and 2031 transitions. Second operand 34 states. [2020-12-23 07:11:29,291 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-12-23 07:11:29,291 INFO L93 Difference]: Finished difference Result 3439 states and 4088 transitions. [2020-12-23 07:11:29,292 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 148 states. [2020-12-23 07:11:29,292 INFO L78 Accepts]: Start accepts. Automaton has 34 states. Word has length 153 [2020-12-23 07:11:29,292 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-12-23 07:11:29,299 INFO L225 Difference]: With dead ends: 3439 [2020-12-23 07:11:29,299 INFO L226 Difference]: Without dead ends: 2356 [2020-12-23 07:11:29,304 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 321 GetRequests, 146 SyntacticMatches, 0 SemanticMatches, 175 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10497 ImplicationChecksByTransitivity, 7.4s TimeCoverageRelationStatistics Valid=6053, Invalid=25099, Unknown=0, NotChecked=0, Total=31152 [2020-12-23 07:11:29,306 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2356 states. [2020-12-23 07:11:29,491 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2356 to 1810. [2020-12-23 07:11:29,491 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1810 states. [2020-12-23 07:11:29,493 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1810 states to 1810 states and 2130 transitions. [2020-12-23 07:11:29,494 INFO L78 Accepts]: Start accepts. Automaton has 1810 states and 2130 transitions. Word has length 153 [2020-12-23 07:11:29,494 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-12-23 07:11:29,494 INFO L481 AbstractCegarLoop]: Abstraction has 1810 states and 2130 transitions. [2020-12-23 07:11:29,494 INFO L482 AbstractCegarLoop]: Interpolant automaton has 34 states. [2020-12-23 07:11:29,494 INFO L276 IsEmpty]: Start isEmpty. Operand 1810 states and 2130 transitions. [2020-12-23 07:11:29,496 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 157 [2020-12-23 07:11:29,496 INFO L414 BasicCegarLoop]: Found error trace [2020-12-23 07:11:29,496 INFO L422 BasicCegarLoop]: trace histogram [45, 45, 44, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2020-12-23 07:11:29,709 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 27 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable33 [2020-12-23 07:11:29,710 INFO L429 AbstractCegarLoop]: === Iteration 35 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-12-23 07:11:29,710 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-12-23 07:11:29,710 INFO L82 PathProgramCache]: Analyzing trace with hash 882596709, now seen corresponding path program 1 times [2020-12-23 07:11:29,711 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-12-23 07:11:29,711 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1539491775] [2020-12-23 07:11:29,711 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-12-23 07:11:29,733 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-12-23 07:11:30,200 INFO L134 CoverageAnalysis]: Checked inductivity of 3068 backedges. 1565 proven. 715 refuted. 0 times theorem prover too weak. 788 trivial. 0 not checked. [2020-12-23 07:11:30,200 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1539491775] [2020-12-23 07:11:30,201 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [860214816] [2020-12-23 07:11:30,201 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate-bitabs/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 28 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 28 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-12-23 07:11:30,276 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-12-23 07:11:30,278 INFO L263 TraceCheckSpWp]: Trace formula consists of 281 conjuncts, 25 conjunts are in the unsatisfiable core [2020-12-23 07:11:30,280 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2020-12-23 07:11:31,045 INFO L134 CoverageAnalysis]: Checked inductivity of 3068 backedges. 1565 proven. 715 refuted. 0 times theorem prover too weak. 788 trivial. 0 not checked. [2020-12-23 07:11:31,045 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2020-12-23 07:11:31,045 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [25, 25] total 48 [2020-12-23 07:11:31,045 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1356335993] [2020-12-23 07:11:31,046 INFO L461 AbstractCegarLoop]: Interpolant automaton has 49 states [2020-12-23 07:11:31,046 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-12-23 07:11:31,047 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 49 interpolants. [2020-12-23 07:11:31,047 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=923, Invalid=1429, Unknown=0, NotChecked=0, Total=2352 [2020-12-23 07:11:31,047 INFO L87 Difference]: Start difference. First operand 1810 states and 2130 transitions. Second operand 49 states. [2020-12-23 07:11:31,549 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-12-23 07:11:31,549 INFO L93 Difference]: Finished difference Result 3392 states and 4017 transitions. [2020-12-23 07:11:31,549 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2020-12-23 07:11:31,550 INFO L78 Accepts]: Start accepts. Automaton has 49 states. Word has length 156 [2020-12-23 07:11:31,550 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-12-23 07:11:31,557 INFO L225 Difference]: With dead ends: 3392 [2020-12-23 07:11:31,557 INFO L226 Difference]: Without dead ends: 1936 [2020-12-23 07:11:31,559 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 180 GetRequests, 133 SyntacticMatches, 0 SemanticMatches, 47 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1009 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=923, Invalid=1429, Unknown=0, NotChecked=0, Total=2352 [2020-12-23 07:11:31,561 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1936 states. [2020-12-23 07:11:31,731 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1936 to 1869. [2020-12-23 07:11:31,731 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1869 states. [2020-12-23 07:11:31,734 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1869 states to 1869 states and 2192 transitions. [2020-12-23 07:11:31,734 INFO L78 Accepts]: Start accepts. Automaton has 1869 states and 2192 transitions. Word has length 156 [2020-12-23 07:11:31,735 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-12-23 07:11:31,735 INFO L481 AbstractCegarLoop]: Abstraction has 1869 states and 2192 transitions. [2020-12-23 07:11:31,735 INFO L482 AbstractCegarLoop]: Interpolant automaton has 49 states. [2020-12-23 07:11:31,735 INFO L276 IsEmpty]: Start isEmpty. Operand 1869 states and 2192 transitions. [2020-12-23 07:11:31,737 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 160 [2020-12-23 07:11:31,737 INFO L414 BasicCegarLoop]: Found error trace [2020-12-23 07:11:31,737 INFO L422 BasicCegarLoop]: trace histogram [46, 46, 45, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2020-12-23 07:11:31,937 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 28 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable34 [2020-12-23 07:11:31,938 INFO L429 AbstractCegarLoop]: === Iteration 36 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-12-23 07:11:31,938 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-12-23 07:11:31,939 INFO L82 PathProgramCache]: Analyzing trace with hash -1319566561, now seen corresponding path program 2 times [2020-12-23 07:11:31,939 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-12-23 07:11:31,939 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1456808454] [2020-12-23 07:11:31,939 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-12-23 07:11:31,960 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-12-23 07:11:32,469 INFO L134 CoverageAnalysis]: Checked inductivity of 3205 backedges. 1636 proven. 782 refuted. 0 times theorem prover too weak. 787 trivial. 0 not checked. [2020-12-23 07:11:32,469 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1456808454] [2020-12-23 07:11:32,470 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [817836294] [2020-12-23 07:11:32,470 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate-bitabs/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 29 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 29 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-12-23 07:11:32,548 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2020-12-23 07:11:32,548 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2020-12-23 07:11:32,550 INFO L263 TraceCheckSpWp]: Trace formula consists of 285 conjuncts, 26 conjunts are in the unsatisfiable core [2020-12-23 07:11:32,559 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2020-12-23 07:11:33,402 INFO L134 CoverageAnalysis]: Checked inductivity of 3205 backedges. 1635 proven. 782 refuted. 0 times theorem prover too weak. 788 trivial. 0 not checked. [2020-12-23 07:11:33,402 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2020-12-23 07:11:33,403 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [27, 26] total 51 [2020-12-23 07:11:33,403 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [732192478] [2020-12-23 07:11:33,403 INFO L461 AbstractCegarLoop]: Interpolant automaton has 52 states [2020-12-23 07:11:33,403 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-12-23 07:11:33,404 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 52 interpolants. [2020-12-23 07:11:33,404 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=954, Invalid=1698, Unknown=0, NotChecked=0, Total=2652 [2020-12-23 07:11:33,404 INFO L87 Difference]: Start difference. First operand 1869 states and 2192 transitions. Second operand 52 states. [2020-12-23 07:11:34,994 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-12-23 07:11:34,994 INFO L93 Difference]: Finished difference Result 4186 states and 5017 transitions. [2020-12-23 07:11:34,995 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 58 states. [2020-12-23 07:11:34,995 INFO L78 Accepts]: Start accepts. Automaton has 52 states. Word has length 159 [2020-12-23 07:11:34,995 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-12-23 07:11:35,000 INFO L225 Difference]: With dead ends: 4186 [2020-12-23 07:11:35,000 INFO L226 Difference]: Without dead ends: 2509 [2020-12-23 07:11:35,004 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 216 GetRequests, 135 SyntacticMatches, 0 SemanticMatches, 81 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1964 ImplicationChecksByTransitivity, 2.0s TimeCoverageRelationStatistics Valid=2098, Invalid=4708, Unknown=0, NotChecked=0, Total=6806 [2020-12-23 07:11:35,006 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2509 states. [2020-12-23 07:11:35,147 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2509 to 1941. [2020-12-23 07:11:35,147 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1941 states. [2020-12-23 07:11:35,150 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1941 states to 1941 states and 2275 transitions. [2020-12-23 07:11:35,150 INFO L78 Accepts]: Start accepts. Automaton has 1941 states and 2275 transitions. Word has length 159 [2020-12-23 07:11:35,150 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-12-23 07:11:35,150 INFO L481 AbstractCegarLoop]: Abstraction has 1941 states and 2275 transitions. [2020-12-23 07:11:35,150 INFO L482 AbstractCegarLoop]: Interpolant automaton has 52 states. [2020-12-23 07:11:35,150 INFO L276 IsEmpty]: Start isEmpty. Operand 1941 states and 2275 transitions. [2020-12-23 07:11:35,152 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 166 [2020-12-23 07:11:35,152 INFO L414 BasicCegarLoop]: Found error trace [2020-12-23 07:11:35,153 INFO L422 BasicCegarLoop]: trace histogram [48, 48, 47, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2020-12-23 07:11:35,365 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 29 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable35 [2020-12-23 07:11:35,366 INFO L429 AbstractCegarLoop]: === Iteration 37 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-12-23 07:11:35,366 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-12-23 07:11:35,367 INFO L82 PathProgramCache]: Analyzing trace with hash 1553693227, now seen corresponding path program 3 times [2020-12-23 07:11:35,367 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-12-23 07:11:35,367 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1159849352] [2020-12-23 07:11:35,367 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-12-23 07:11:35,389 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-12-23 07:11:35,924 INFO L134 CoverageAnalysis]: Checked inductivity of 3488 backedges. 1779 proven. 852 refuted. 0 times theorem prover too weak. 857 trivial. 0 not checked. [2020-12-23 07:11:35,925 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1159849352] [2020-12-23 07:11:35,925 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1550581498] [2020-12-23 07:11:35,925 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 No working directory specified, using /storage/repos/ultimate-bitabs/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 30 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 30 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-12-23 07:11:35,981 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 2 check-sat command(s) [2020-12-23 07:11:35,981 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2020-12-23 07:11:35,982 INFO L263 TraceCheckSpWp]: Trace formula consists of 103 conjuncts, 4 conjunts are in the unsatisfiable core [2020-12-23 07:11:35,985 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2020-12-23 07:11:36,214 INFO L134 CoverageAnalysis]: Checked inductivity of 3488 backedges. 102 proven. 0 refuted. 0 times theorem prover too weak. 3386 trivial. 0 not checked. [2020-12-23 07:11:36,214 INFO L219 FreeRefinementEngine]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2020-12-23 07:11:36,214 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [28] total 32 [2020-12-23 07:11:36,215 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1114745548] [2020-12-23 07:11:36,215 INFO L461 AbstractCegarLoop]: Interpolant automaton has 5 states [2020-12-23 07:11:36,215 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-12-23 07:11:36,215 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2020-12-23 07:11:36,216 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=339, Invalid=653, Unknown=0, NotChecked=0, Total=992 [2020-12-23 07:11:36,216 INFO L87 Difference]: Start difference. First operand 1941 states and 2275 transitions. Second operand 5 states. [2020-12-23 07:11:36,448 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-12-23 07:11:36,448 INFO L93 Difference]: Finished difference Result 2712 states and 3137 transitions. [2020-12-23 07:11:36,449 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2020-12-23 07:11:36,449 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 165 [2020-12-23 07:11:36,449 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-12-23 07:11:36,451 INFO L225 Difference]: With dead ends: 2712 [2020-12-23 07:11:36,451 INFO L226 Difference]: Without dead ends: 1328 [2020-12-23 07:11:36,452 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 195 GetRequests, 163 SyntacticMatches, 0 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 146 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=349, Invalid=773, Unknown=0, NotChecked=0, Total=1122 [2020-12-23 07:11:36,453 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1328 states. [2020-12-23 07:11:36,580 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1328 to 1178. [2020-12-23 07:11:36,581 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1178 states. [2020-12-23 07:11:36,582 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1178 states to 1178 states and 1325 transitions. [2020-12-23 07:11:36,582 INFO L78 Accepts]: Start accepts. Automaton has 1178 states and 1325 transitions. Word has length 165 [2020-12-23 07:11:36,582 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-12-23 07:11:36,582 INFO L481 AbstractCegarLoop]: Abstraction has 1178 states and 1325 transitions. [2020-12-23 07:11:36,582 INFO L482 AbstractCegarLoop]: Interpolant automaton has 5 states. [2020-12-23 07:11:36,582 INFO L276 IsEmpty]: Start isEmpty. Operand 1178 states and 1325 transitions. [2020-12-23 07:11:36,589 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 166 [2020-12-23 07:11:36,590 INFO L414 BasicCegarLoop]: Found error trace [2020-12-23 07:11:36,590 INFO L422 BasicCegarLoop]: trace histogram [48, 48, 47, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2020-12-23 07:11:36,803 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 30 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable36 [2020-12-23 07:11:36,804 INFO L429 AbstractCegarLoop]: === Iteration 38 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-12-23 07:11:36,804 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-12-23 07:11:36,804 INFO L82 PathProgramCache]: Analyzing trace with hash 1555540269, now seen corresponding path program 7 times [2020-12-23 07:11:36,805 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-12-23 07:11:36,805 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [13333482] [2020-12-23 07:11:36,805 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-12-23 07:11:36,831 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-12-23 07:11:38,097 INFO L134 CoverageAnalysis]: Checked inductivity of 3488 backedges. 913 proven. 2575 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2020-12-23 07:11:38,098 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [13333482] [2020-12-23 07:11:38,098 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [663205437] [2020-12-23 07:11:38,098 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate-bitabs/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 31 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 31 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-12-23 07:11:38,176 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-12-23 07:11:38,177 INFO L263 TraceCheckSpWp]: Trace formula consists of 289 conjuncts, 27 conjunts are in the unsatisfiable core [2020-12-23 07:11:38,180 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2020-12-23 07:11:39,595 INFO L134 CoverageAnalysis]: Checked inductivity of 3488 backedges. 1778 proven. 852 refuted. 0 times theorem prover too weak. 858 trivial. 0 not checked. [2020-12-23 07:11:39,595 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2020-12-23 07:11:39,595 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [51, 27] total 77 [2020-12-23 07:11:39,595 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1560180227] [2020-12-23 07:11:39,596 INFO L461 AbstractCegarLoop]: Interpolant automaton has 77 states [2020-12-23 07:11:39,596 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-12-23 07:11:39,597 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 77 interpolants. [2020-12-23 07:11:39,597 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1329, Invalid=4523, Unknown=0, NotChecked=0, Total=5852 [2020-12-23 07:11:39,598 INFO L87 Difference]: Start difference. First operand 1178 states and 1325 transitions. Second operand 77 states. [2020-12-23 07:11:42,654 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-12-23 07:11:42,654 INFO L93 Difference]: Finished difference Result 2412 states and 2752 transitions. [2020-12-23 07:11:42,655 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 79 states. [2020-12-23 07:11:42,655 INFO L78 Accepts]: Start accepts. Automaton has 77 states. Word has length 165 [2020-12-23 07:11:42,655 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-12-23 07:11:42,657 INFO L225 Difference]: With dead ends: 2412 [2020-12-23 07:11:42,657 INFO L226 Difference]: Without dead ends: 1441 [2020-12-23 07:11:42,659 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 268 GetRequests, 141 SyntacticMatches, 0 SemanticMatches, 127 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4685 ImplicationChecksByTransitivity, 4.1s TimeCoverageRelationStatistics Valid=4308, Invalid=12204, Unknown=0, NotChecked=0, Total=16512 [2020-12-23 07:11:42,660 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1441 states. [2020-12-23 07:11:42,778 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1441 to 1211. [2020-12-23 07:11:42,778 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1211 states. [2020-12-23 07:11:42,779 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1211 states to 1211 states and 1359 transitions. [2020-12-23 07:11:42,780 INFO L78 Accepts]: Start accepts. Automaton has 1211 states and 1359 transitions. Word has length 165 [2020-12-23 07:11:42,780 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-12-23 07:11:42,780 INFO L481 AbstractCegarLoop]: Abstraction has 1211 states and 1359 transitions. [2020-12-23 07:11:42,780 INFO L482 AbstractCegarLoop]: Interpolant automaton has 77 states. [2020-12-23 07:11:42,780 INFO L276 IsEmpty]: Start isEmpty. Operand 1211 states and 1359 transitions. [2020-12-23 07:11:42,782 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 172 [2020-12-23 07:11:42,783 INFO L414 BasicCegarLoop]: Found error trace [2020-12-23 07:11:42,783 INFO L422 BasicCegarLoop]: trace histogram [50, 50, 49, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2020-12-23 07:11:42,994 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable37,31 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-12-23 07:11:42,995 INFO L429 AbstractCegarLoop]: === Iteration 39 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-12-23 07:11:42,995 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-12-23 07:11:42,996 INFO L82 PathProgramCache]: Analyzing trace with hash -1830883295, now seen corresponding path program 8 times [2020-12-23 07:11:42,996 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-12-23 07:11:42,996 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2096242925] [2020-12-23 07:11:42,997 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-12-23 07:11:43,020 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-12-23 07:11:44,529 INFO L134 CoverageAnalysis]: Checked inductivity of 3783 backedges. 988 proven. 2795 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2020-12-23 07:11:44,530 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2096242925] [2020-12-23 07:11:44,530 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [664764438] [2020-12-23 07:11:44,530 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate-bitabs/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 32 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 32 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-12-23 07:11:44,611 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2020-12-23 07:11:44,611 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2020-12-23 07:11:44,612 INFO L263 TraceCheckSpWp]: Trace formula consists of 297 conjuncts, 30 conjunts are in the unsatisfiable core [2020-12-23 07:11:44,615 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2020-12-23 07:11:46,243 INFO L134 CoverageAnalysis]: Checked inductivity of 3783 backedges. 58 proven. 2800 refuted. 0 times theorem prover too weak. 925 trivial. 0 not checked. [2020-12-23 07:11:46,243 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2020-12-23 07:11:46,244 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [53, 29] total 81 [2020-12-23 07:11:46,244 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1173530535] [2020-12-23 07:11:46,244 INFO L461 AbstractCegarLoop]: Interpolant automaton has 81 states [2020-12-23 07:11:46,244 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-12-23 07:11:46,245 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 81 interpolants. [2020-12-23 07:11:46,245 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1415, Invalid=5065, Unknown=0, NotChecked=0, Total=6480 [2020-12-23 07:11:46,245 INFO L87 Difference]: Start difference. First operand 1211 states and 1359 transitions. Second operand 81 states. [2020-12-23 07:11:49,596 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-12-23 07:11:49,596 INFO L93 Difference]: Finished difference Result 2124 states and 2404 transitions. [2020-12-23 07:11:49,597 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 80 states. [2020-12-23 07:11:49,597 INFO L78 Accepts]: Start accepts. Automaton has 81 states. Word has length 171 [2020-12-23 07:11:49,597 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-12-23 07:11:49,599 INFO L225 Difference]: With dead ends: 2124 [2020-12-23 07:11:49,599 INFO L226 Difference]: Without dead ends: 1610 [2020-12-23 07:11:49,601 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 276 GetRequests, 145 SyntacticMatches, 0 SemanticMatches, 131 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5038 ImplicationChecksByTransitivity, 4.5s TimeCoverageRelationStatistics Valid=4250, Invalid=13306, Unknown=0, NotChecked=0, Total=17556 [2020-12-23 07:11:49,601 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1610 states. [2020-12-23 07:11:49,717 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1610 to 1573. [2020-12-23 07:11:49,718 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1573 states. [2020-12-23 07:11:49,719 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1573 states to 1573 states and 1783 transitions. [2020-12-23 07:11:49,719 INFO L78 Accepts]: Start accepts. Automaton has 1573 states and 1783 transitions. Word has length 171 [2020-12-23 07:11:49,720 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-12-23 07:11:49,720 INFO L481 AbstractCegarLoop]: Abstraction has 1573 states and 1783 transitions. [2020-12-23 07:11:49,720 INFO L482 AbstractCegarLoop]: Interpolant automaton has 81 states. [2020-12-23 07:11:49,720 INFO L276 IsEmpty]: Start isEmpty. Operand 1573 states and 1783 transitions. [2020-12-23 07:11:49,721 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 175 [2020-12-23 07:11:49,721 INFO L414 BasicCegarLoop]: Found error trace [2020-12-23 07:11:49,721 INFO L422 BasicCegarLoop]: trace histogram [51, 51, 50, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2020-12-23 07:11:49,922 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 32 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable38 [2020-12-23 07:11:49,922 INFO L429 AbstractCegarLoop]: === Iteration 40 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-12-23 07:11:49,923 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-12-23 07:11:49,923 INFO L82 PathProgramCache]: Analyzing trace with hash -1730966685, now seen corresponding path program 9 times [2020-12-23 07:11:49,924 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-12-23 07:11:49,924 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1882465108] [2020-12-23 07:11:49,924 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-12-23 07:11:49,949 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-12-23 07:11:50,593 INFO L134 CoverageAnalysis]: Checked inductivity of 3935 backedges. 85 proven. 2848 refuted. 0 times theorem prover too weak. 1002 trivial. 0 not checked. [2020-12-23 07:11:50,594 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1882465108] [2020-12-23 07:11:50,594 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [821718233] [2020-12-23 07:11:50,594 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 No working directory specified, using /storage/repos/ultimate-bitabs/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 33 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 33 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-12-23 07:11:50,643 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 2 check-sat command(s) [2020-12-23 07:11:50,644 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2020-12-23 07:11:50,644 INFO L263 TraceCheckSpWp]: Trace formula consists of 99 conjuncts, 9 conjunts are in the unsatisfiable core [2020-12-23 07:11:50,647 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2020-12-23 07:11:50,746 INFO L639 QuantifierPusher]: Distributing 2 conjuncts over 2 disjuncts [2020-12-23 07:11:50,986 INFO L134 CoverageAnalysis]: Checked inductivity of 3935 backedges. 2007 proven. 2 refuted. 0 times theorem prover too weak. 1926 trivial. 0 not checked. [2020-12-23 07:11:50,987 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2020-12-23 07:11:50,987 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [28, 6] total 33 [2020-12-23 07:11:50,987 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1011398651] [2020-12-23 07:11:50,987 INFO L461 AbstractCegarLoop]: Interpolant automaton has 33 states [2020-12-23 07:11:50,988 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-12-23 07:11:50,988 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2020-12-23 07:11:50,988 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=390, Invalid=666, Unknown=0, NotChecked=0, Total=1056 [2020-12-23 07:11:50,988 INFO L87 Difference]: Start difference. First operand 1573 states and 1783 transitions. Second operand 33 states. [2020-12-23 07:11:57,842 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-12-23 07:11:57,842 INFO L93 Difference]: Finished difference Result 3053 states and 3471 transitions. [2020-12-23 07:11:57,843 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 114 states. [2020-12-23 07:11:57,843 INFO L78 Accepts]: Start accepts. Automaton has 33 states. Word has length 174 [2020-12-23 07:11:57,843 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-12-23 07:11:57,846 INFO L225 Difference]: With dead ends: 3053 [2020-12-23 07:11:57,846 INFO L226 Difference]: Without dead ends: 2060 [2020-12-23 07:11:57,848 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 314 GetRequests, 173 SyntacticMatches, 0 SemanticMatches, 141 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6312 ImplicationChecksByTransitivity, 6.3s TimeCoverageRelationStatistics Valid=5720, Invalid=14586, Unknown=0, NotChecked=0, Total=20306 [2020-12-23 07:11:57,849 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2060 states. [2020-12-23 07:11:57,977 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2060 to 1624. [2020-12-23 07:11:57,978 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1624 states. [2020-12-23 07:11:57,979 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1624 states to 1624 states and 1886 transitions. [2020-12-23 07:11:57,980 INFO L78 Accepts]: Start accepts. Automaton has 1624 states and 1886 transitions. Word has length 174 [2020-12-23 07:11:57,980 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-12-23 07:11:57,980 INFO L481 AbstractCegarLoop]: Abstraction has 1624 states and 1886 transitions. [2020-12-23 07:11:57,980 INFO L482 AbstractCegarLoop]: Interpolant automaton has 33 states. [2020-12-23 07:11:57,980 INFO L276 IsEmpty]: Start isEmpty. Operand 1624 states and 1886 transitions. [2020-12-23 07:11:57,982 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 264 [2020-12-23 07:11:57,982 INFO L414 BasicCegarLoop]: Found error trace [2020-12-23 07:11:57,983 INFO L422 BasicCegarLoop]: trace histogram [78, 78, 75, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1] [2020-12-23 07:11:58,199 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 33 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable39 [2020-12-23 07:11:58,200 INFO L429 AbstractCegarLoop]: === Iteration 41 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-12-23 07:11:58,200 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-12-23 07:11:58,201 INFO L82 PathProgramCache]: Analyzing trace with hash 1331899705, now seen corresponding path program 4 times [2020-12-23 07:11:58,201 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-12-23 07:11:58,201 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1147730544] [2020-12-23 07:11:58,202 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-12-23 07:11:58,233 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-12-23 07:11:58,940 INFO L134 CoverageAnalysis]: Checked inductivity of 9267 backedges. 4164 proven. 1001 refuted. 0 times theorem prover too weak. 4102 trivial. 0 not checked. [2020-12-23 07:11:58,940 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1147730544] [2020-12-23 07:11:58,941 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1599402839] [2020-12-23 07:11:58,941 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST No working directory specified, using /storage/repos/ultimate-bitabs/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 34 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 34 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-12-23 07:11:59,068 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2020-12-23 07:11:59,069 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2020-12-23 07:11:59,072 INFO L263 TraceCheckSpWp]: Trace formula consists of 531 conjuncts, 74 conjunts are in the unsatisfiable core [2020-12-23 07:11:59,078 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2020-12-23 07:12:03,388 INFO L639 QuantifierPusher]: Distributing 2 conjuncts over 3 disjuncts [2020-12-23 07:12:03,389 INFO L639 QuantifierPusher]: Distributing 2 conjuncts over 2 disjuncts [2020-12-23 07:12:03,391 INFO L639 QuantifierPusher]: Distributing 2 conjuncts over 2 disjuncts [2020-12-23 07:12:03,677 INFO L134 CoverageAnalysis]: Checked inductivity of 9267 backedges. 925 proven. 7341 refuted. 0 times theorem prover too weak. 1001 trivial. 0 not checked. [2020-12-23 07:12:03,677 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2020-12-23 07:12:03,678 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [29, 62] total 90 [2020-12-23 07:12:03,678 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [284871285] [2020-12-23 07:12:03,678 INFO L461 AbstractCegarLoop]: Interpolant automaton has 90 states [2020-12-23 07:12:03,679 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-12-23 07:12:03,679 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 90 interpolants. [2020-12-23 07:12:03,680 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1261, Invalid=6749, Unknown=0, NotChecked=0, Total=8010 [2020-12-23 07:12:03,680 INFO L87 Difference]: Start difference. First operand 1624 states and 1886 transitions. Second operand 90 states. [2020-12-23 07:12:12,199 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-12-23 07:12:12,199 INFO L93 Difference]: Finished difference Result 3521 states and 4093 transitions. [2020-12-23 07:12:12,200 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 114 states. [2020-12-23 07:12:12,200 INFO L78 Accepts]: Start accepts. Automaton has 90 states. Word has length 263 [2020-12-23 07:12:12,200 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-12-23 07:12:12,204 INFO L225 Difference]: With dead ends: 3521 [2020-12-23 07:12:12,204 INFO L226 Difference]: Without dead ends: 2326 [2020-12-23 07:12:12,208 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 401 GetRequests, 203 SyntacticMatches, 0 SemanticMatches, 198 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13421 ImplicationChecksByTransitivity, 10.4s TimeCoverageRelationStatistics Valid=6210, Invalid=33590, Unknown=0, NotChecked=0, Total=39800 [2020-12-23 07:12:12,210 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2326 states. [2020-12-23 07:12:12,350 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2326 to 1678. [2020-12-23 07:12:12,350 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1678 states. [2020-12-23 07:12:12,352 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1678 states to 1678 states and 1940 transitions. [2020-12-23 07:12:12,352 INFO L78 Accepts]: Start accepts. Automaton has 1678 states and 1940 transitions. Word has length 263 [2020-12-23 07:12:12,353 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-12-23 07:12:12,353 INFO L481 AbstractCegarLoop]: Abstraction has 1678 states and 1940 transitions. [2020-12-23 07:12:12,353 INFO L482 AbstractCegarLoop]: Interpolant automaton has 90 states. [2020-12-23 07:12:12,353 INFO L276 IsEmpty]: Start isEmpty. Operand 1678 states and 1940 transitions. [2020-12-23 07:12:12,355 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 273 [2020-12-23 07:12:12,355 INFO L414 BasicCegarLoop]: Found error trace [2020-12-23 07:12:12,356 INFO L422 BasicCegarLoop]: trace histogram [81, 81, 78, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1] [2020-12-23 07:12:12,556 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable40,34 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-12-23 07:12:12,556 INFO L429 AbstractCegarLoop]: === Iteration 42 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-12-23 07:12:12,557 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-12-23 07:12:12,557 INFO L82 PathProgramCache]: Analyzing trace with hash -282690071, now seen corresponding path program 5 times [2020-12-23 07:12:12,558 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-12-23 07:12:12,558 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [315837731] [2020-12-23 07:12:12,558 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-12-23 07:12:12,586 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-12-23 07:12:13,365 INFO L134 CoverageAnalysis]: Checked inductivity of 9987 backedges. 4486 proven. 1080 refuted. 0 times theorem prover too weak. 4421 trivial. 0 not checked. [2020-12-23 07:12:13,366 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [315837731] [2020-12-23 07:12:13,366 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1500638796] [2020-12-23 07:12:13,366 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate-bitabs/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 35 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 35 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-12-23 07:12:13,558 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 56 check-sat command(s) [2020-12-23 07:12:13,559 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2020-12-23 07:12:13,561 INFO L263 TraceCheckSpWp]: Trace formula consists of 590 conjuncts, 30 conjunts are in the unsatisfiable core [2020-12-23 07:12:13,565 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2020-12-23 07:12:14,656 INFO L134 CoverageAnalysis]: Checked inductivity of 9987 backedges. 4486 proven. 1080 refuted. 0 times theorem prover too weak. 4421 trivial. 0 not checked. [2020-12-23 07:12:14,657 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2020-12-23 07:12:14,657 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [30, 30] total 58 [2020-12-23 07:12:14,657 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [365405785] [2020-12-23 07:12:14,657 INFO L461 AbstractCegarLoop]: Interpolant automaton has 59 states [2020-12-23 07:12:14,657 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-12-23 07:12:14,658 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 59 interpolants. [2020-12-23 07:12:14,658 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1333, Invalid=2089, Unknown=0, NotChecked=0, Total=3422 [2020-12-23 07:12:14,658 INFO L87 Difference]: Start difference. First operand 1678 states and 1940 transitions. Second operand 59 states. [2020-12-23 07:12:15,278 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-12-23 07:12:15,279 INFO L93 Difference]: Finished difference Result 3245 states and 3772 transitions. [2020-12-23 07:12:15,279 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 31 states. [2020-12-23 07:12:15,280 INFO L78 Accepts]: Start accepts. Automaton has 59 states. Word has length 272 [2020-12-23 07:12:15,280 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-12-23 07:12:15,283 INFO L225 Difference]: With dead ends: 3245 [2020-12-23 07:12:15,284 INFO L226 Difference]: Without dead ends: 1814 [2020-12-23 07:12:15,286 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 301 GetRequests, 244 SyntacticMatches, 0 SemanticMatches, 57 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1509 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=1333, Invalid=2089, Unknown=0, NotChecked=0, Total=3422 [2020-12-23 07:12:15,288 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1814 states. [2020-12-23 07:12:15,454 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1814 to 1747. [2020-12-23 07:12:15,455 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1747 states. [2020-12-23 07:12:15,456 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1747 states to 1747 states and 2014 transitions. [2020-12-23 07:12:15,457 INFO L78 Accepts]: Start accepts. Automaton has 1747 states and 2014 transitions. Word has length 272 [2020-12-23 07:12:15,463 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-12-23 07:12:15,464 INFO L481 AbstractCegarLoop]: Abstraction has 1747 states and 2014 transitions. [2020-12-23 07:12:15,464 INFO L482 AbstractCegarLoop]: Interpolant automaton has 59 states. [2020-12-23 07:12:15,464 INFO L276 IsEmpty]: Start isEmpty. Operand 1747 states and 2014 transitions. [2020-12-23 07:12:15,467 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 282 [2020-12-23 07:12:15,468 INFO L414 BasicCegarLoop]: Found error trace [2020-12-23 07:12:15,468 INFO L422 BasicCegarLoop]: trace histogram [84, 84, 81, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1] [2020-12-23 07:12:15,682 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 35 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable41 [2020-12-23 07:12:15,683 INFO L429 AbstractCegarLoop]: === Iteration 43 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2020-12-23 07:12:15,683 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2020-12-23 07:12:15,684 INFO L82 PathProgramCache]: Analyzing trace with hash -407080135, now seen corresponding path program 6 times [2020-12-23 07:12:15,684 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2020-12-23 07:12:15,684 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [794178652] [2020-12-23 07:12:15,684 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2020-12-23 07:12:15,714 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2020-12-23 07:12:16,546 INFO L134 CoverageAnalysis]: Checked inductivity of 10734 backedges. 4820 proven. 1162 refuted. 0 times theorem prover too weak. 4752 trivial. 0 not checked. [2020-12-23 07:12:16,546 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [794178652] [2020-12-23 07:12:16,547 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1714656598] [2020-12-23 07:12:16,547 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE No working directory specified, using /storage/repos/ultimate-bitabs/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 36 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 36 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-12-23 07:12:16,615 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 5 check-sat command(s) [2020-12-23 07:12:16,616 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2020-12-23 07:12:16,617 INFO L263 TraceCheckSpWp]: Trace formula consists of 120 conjuncts, 15 conjunts are in the unsatisfiable core [2020-12-23 07:12:16,621 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2020-12-23 07:12:17,114 INFO L639 QuantifierPusher]: Distributing 2 conjuncts over 3 disjuncts [2020-12-23 07:12:17,223 INFO L134 CoverageAnalysis]: Checked inductivity of 10734 backedges. 4914 proven. 1 refuted. 0 times theorem prover too weak. 5819 trivial. 0 not checked. [2020-12-23 07:12:17,224 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2020-12-23 07:12:17,224 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [31, 8] total 38 [2020-12-23 07:12:17,224 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [704697058] [2020-12-23 07:12:17,225 INFO L461 AbstractCegarLoop]: Interpolant automaton has 38 states [2020-12-23 07:12:17,225 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2020-12-23 07:12:17,226 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 38 interpolants. [2020-12-23 07:12:17,226 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=485, Invalid=921, Unknown=0, NotChecked=0, Total=1406 [2020-12-23 07:12:17,227 INFO L87 Difference]: Start difference. First operand 1747 states and 2014 transitions. Second operand 38 states. [2020-12-23 07:12:22,246 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2020-12-23 07:12:22,246 INFO L93 Difference]: Finished difference Result 3405 states and 3970 transitions. [2020-12-23 07:12:22,247 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 67 states. [2020-12-23 07:12:22,247 INFO L78 Accepts]: Start accepts. Automaton has 38 states. Word has length 281 [2020-12-23 07:12:22,247 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2020-12-23 07:12:22,247 INFO L225 Difference]: With dead ends: 3405 [2020-12-23 07:12:22,248 INFO L226 Difference]: Without dead ends: 0 [2020-12-23 07:12:22,250 INFO L677 BasicCegarLoop]: 0 DeclaredPredicates, 377 GetRequests, 277 SyntacticMatches, 0 SemanticMatches, 100 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2189 ImplicationChecksByTransitivity, 4.9s TimeCoverageRelationStatistics Valid=3231, Invalid=7071, Unknown=0, NotChecked=0, Total=10302 [2020-12-23 07:12:22,250 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2020-12-23 07:12:22,250 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2020-12-23 07:12:22,250 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 0 states. [2020-12-23 07:12:22,251 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2020-12-23 07:12:22,251 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 281 [2020-12-23 07:12:22,251 INFO L84 Accepts]: Finished accepts. word is rejected. [2020-12-23 07:12:22,251 INFO L481 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2020-12-23 07:12:22,251 INFO L482 AbstractCegarLoop]: Interpolant automaton has 38 states. [2020-12-23 07:12:22,251 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2020-12-23 07:12:22,251 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2020-12-23 07:12:22,461 WARN L518 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable42,36 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2020-12-23 07:12:22,465 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends 0 states and 0 transitions. [2020-12-23 07:13:49,065 WARN L197 SmtUtils]: Spent 1.44 m on a formula simplification. DAG size of input: 6330 DAG size of output: 4353 [2020-12-23 07:13:49,365 WARN L197 SmtUtils]: Spent 274.00 ms on a formula simplification. DAG size of input: 293 DAG size of output: 216