/usr/bin/java -Xmx8000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata ./data --core.log.level.for.class de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN -tc ../../../trunk/examples/toolchains/AutomizerCTransformed.xml -s ../../../trunk/examples/settings/automizer/LoopAccelerationJordanC.epf -i ../../../trunk/examples/svcomp/nla-digbench-scaling/ps4-ll_valuebound20.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-b030c9e [2022-03-20 07:03:08,116 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-03-20 07:03:08,125 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-03-20 07:03:08,156 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-03-20 07:03:08,156 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-03-20 07:03:08,157 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-03-20 07:03:08,158 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-03-20 07:03:08,167 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-03-20 07:03:08,168 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-03-20 07:03:08,169 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-03-20 07:03:08,170 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-03-20 07:03:08,172 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-03-20 07:03:08,172 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-03-20 07:03:08,176 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-03-20 07:03:08,177 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-03-20 07:03:08,178 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-03-20 07:03:08,179 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-03-20 07:03:08,180 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-03-20 07:03:08,183 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-03-20 07:03:08,185 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-03-20 07:03:08,186 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-03-20 07:03:08,187 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-03-20 07:03:08,188 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-03-20 07:03:08,190 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-03-20 07:03:08,191 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-03-20 07:03:08,194 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-03-20 07:03:08,194 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-03-20 07:03:08,194 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-03-20 07:03:08,195 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-03-20 07:03:08,196 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-03-20 07:03:08,197 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-03-20 07:03:08,197 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-03-20 07:03:08,198 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-03-20 07:03:08,198 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-03-20 07:03:08,199 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-03-20 07:03:08,199 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-03-20 07:03:08,200 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-03-20 07:03:08,200 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-03-20 07:03:08,200 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-03-20 07:03:08,200 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-03-20 07:03:08,201 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-03-20 07:03:08,202 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-03-20 07:03:08,203 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/LoopAccelerationJordanC.epf [2022-03-20 07:03:08,213 INFO L113 SettingsManager]: Loading preferences was successful [2022-03-20 07:03:08,213 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-03-20 07:03:08,214 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-03-20 07:03:08,215 INFO L138 SettingsManager]: * sizeof long=4 [2022-03-20 07:03:08,215 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-03-20 07:03:08,215 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-03-20 07:03:08,215 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-03-20 07:03:08,215 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-03-20 07:03:08,215 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-03-20 07:03:08,216 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-03-20 07:03:08,216 INFO L138 SettingsManager]: * sizeof long double=12 [2022-03-20 07:03:08,216 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-03-20 07:03:08,216 INFO L138 SettingsManager]: * Use constant arrays=true [2022-03-20 07:03:08,216 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-03-20 07:03:08,216 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-03-20 07:03:08,216 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-03-20 07:03:08,216 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-03-20 07:03:08,216 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-03-20 07:03:08,217 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-20 07:03:08,217 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-03-20 07:03:08,217 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-03-20 07:03:08,217 INFO L136 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2022-03-20 07:03:08,217 INFO L138 SettingsManager]: * TransformationType=LOOP_ACCELERATION_JORDAN 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/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 Applying setting for plugin de.uni_freiburg.informatik.ultimate.core: Log level for class -> de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN; [2022-03-20 07:03:08,415 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-03-20 07:03:08,434 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-03-20 07:03:08,436 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-03-20 07:03:08,436 INFO L271 PluginConnector]: Initializing CDTParser... [2022-03-20 07:03:08,437 INFO L275 PluginConnector]: CDTParser initialized [2022-03-20 07:03:08,438 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/ps4-ll_valuebound20.c [2022-03-20 07:03:08,482 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/9111af4ac/22c27d8c177947929a2a7b6f9828b63d/FLAGd9e68535b [2022-03-20 07:03:08,806 INFO L306 CDTParser]: Found 1 translation units. [2022-03-20 07:03:08,806 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/ps4-ll_valuebound20.c [2022-03-20 07:03:08,812 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/9111af4ac/22c27d8c177947929a2a7b6f9828b63d/FLAGd9e68535b [2022-03-20 07:03:08,820 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/9111af4ac/22c27d8c177947929a2a7b6f9828b63d [2022-03-20 07:03:08,822 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-03-20 07:03:08,823 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2022-03-20 07:03:08,834 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-03-20 07:03:08,834 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-03-20 07:03:08,836 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-03-20 07:03:08,837 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.03 07:03:08" (1/1) ... [2022-03-20 07:03:08,838 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@2450c143 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 07:03:08, skipping insertion in model container [2022-03-20 07:03:08,838 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.03 07:03:08" (1/1) ... [2022-03-20 07:03:08,842 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-03-20 07:03:08,854 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-03-20 07:03:09,011 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/ps4-ll_valuebound20.c[458,471] [2022-03-20 07:03:09,031 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-03-20 07:03:09,038 INFO L203 MainTranslator]: Completed pre-run [2022-03-20 07:03:09,047 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/ps4-ll_valuebound20.c[458,471] [2022-03-20 07:03:09,063 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-03-20 07:03:09,072 INFO L208 MainTranslator]: Completed translation [2022-03-20 07:03:09,072 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 07:03:09 WrapperNode [2022-03-20 07:03:09,073 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-03-20 07:03:09,073 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-03-20 07:03:09,073 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-03-20 07:03:09,074 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-03-20 07:03:09,081 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 07:03:09" (1/1) ... [2022-03-20 07:03:09,081 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 07:03:09" (1/1) ... [2022-03-20 07:03:09,086 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 07:03:09" (1/1) ... [2022-03-20 07:03:09,086 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 07:03:09" (1/1) ... [2022-03-20 07:03:09,094 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 07:03:09" (1/1) ... [2022-03-20 07:03:09,097 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 07:03:09" (1/1) ... [2022-03-20 07:03:09,098 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 07:03:09" (1/1) ... [2022-03-20 07:03:09,102 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-03-20 07:03:09,103 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-03-20 07:03:09,103 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-03-20 07:03:09,103 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-03-20 07:03:09,104 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 07:03:09" (1/1) ... [2022-03-20 07:03:09,109 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-20 07:03:09,117 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 07:03:09,133 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2022-03-20 07:03:09,155 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2022-03-20 07:03:09,161 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-03-20 07:03:09,161 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-03-20 07:03:09,162 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-03-20 07:03:09,162 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-03-20 07:03:09,162 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-03-20 07:03:09,162 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-03-20 07:03:09,162 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-03-20 07:03:09,162 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-03-20 07:03:09,162 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-03-20 07:03:09,163 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-03-20 07:03:09,163 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_short [2022-03-20 07:03:09,163 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-03-20 07:03:09,163 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-03-20 07:03:09,163 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-03-20 07:03:09,164 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-03-20 07:03:09,164 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-03-20 07:03:09,164 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-03-20 07:03:09,164 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-03-20 07:03:09,165 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-03-20 07:03:09,165 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-03-20 07:03:09,214 INFO L234 CfgBuilder]: Building ICFG [2022-03-20 07:03:09,216 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-03-20 07:03:09,338 INFO L275 CfgBuilder]: Performing block encoding [2022-03-20 07:03:09,342 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-03-20 07:03:09,342 INFO L299 CfgBuilder]: Removed 1 assume(true) statements. [2022-03-20 07:03:09,343 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.03 07:03:09 BoogieIcfgContainer [2022-03-20 07:03:09,344 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-03-20 07:03:09,344 INFO L113 PluginConnector]: ------------------------IcfgTransformer---------------------------- [2022-03-20 07:03:09,344 INFO L271 PluginConnector]: Initializing IcfgTransformer... [2022-03-20 07:03:09,357 INFO L275 PluginConnector]: IcfgTransformer initialized [2022-03-20 07:03:09,373 INFO L185 PluginConnector]: Executing the observer IcfgTransformationObserver from plugin IcfgTransformer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.03 07:03:09" (1/1) ... [2022-03-20 07:03:09,374 INFO L168 ansformationObserver]: Applying ICFG transformation LOOP_ACCELERATION_JORDAN [2022-03-20 07:03:09,388 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 20.03 07:03:09 BasicIcfg [2022-03-20 07:03:09,388 INFO L132 PluginConnector]: ------------------------ END IcfgTransformer---------------------------- [2022-03-20 07:03:09,389 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-03-20 07:03:09,389 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-03-20 07:03:09,391 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-03-20 07:03:09,391 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 20.03 07:03:08" (1/4) ... [2022-03-20 07:03:09,392 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@c24666 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.03 07:03:09, skipping insertion in model container [2022-03-20 07:03:09,392 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 07:03:09" (2/4) ... [2022-03-20 07:03:09,392 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@c24666 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.03 07:03:09, skipping insertion in model container [2022-03-20 07:03:09,392 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.03 07:03:09" (3/4) ... [2022-03-20 07:03:09,392 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@c24666 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 20.03 07:03:09, skipping insertion in model container [2022-03-20 07:03:09,392 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 20.03 07:03:09" (4/4) ... [2022-03-20 07:03:09,393 INFO L111 eAbstractionObserver]: Analyzing ICFG ps4-ll_valuebound20.cJordan [2022-03-20 07:03:09,396 INFO L205 ceAbstractionStarter]: Automizer settings: Hoare:false NWA Interpolation:ForwardPredicates Determinization: PREDICATE_ABSTRACTION [2022-03-20 07:03:09,397 INFO L164 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-03-20 07:03:09,433 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-03-20 07:03:09,438 INFO L340 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=ForwardPredicates, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=false, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=All, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP [2022-03-20 07:03:09,438 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-03-20 07:03:09,446 INFO L276 IsEmpty]: Start isEmpty. Operand has 28 states, 16 states have (on average 1.375) internal successors, (22), 17 states have internal predecessors, (22), 6 states have call successors, (6), 4 states have call predecessors, (6), 4 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-03-20 07:03:09,450 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2022-03-20 07:03:09,450 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 07:03:09,451 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 07:03:09,451 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 07:03:09,454 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 07:03:09,454 INFO L85 PathProgramCache]: Analyzing trace with hash -1885409022, now seen corresponding path program 1 times [2022-03-20 07:03:09,460 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 07:03:09,460 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [967632721] [2022-03-20 07:03:09,460 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 07:03:09,461 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 07:03:09,539 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 07:03:09,586 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-03-20 07:03:09,596 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 07:03:09,602 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-03-20 07:03:09,607 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 07:03:09,613 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-20 07:03:09,614 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 07:03:09,614 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [967632721] [2022-03-20 07:03:09,615 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [967632721] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 07:03:09,615 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 07:03:09,615 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-03-20 07:03:09,616 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1537233376] [2022-03-20 07:03:09,617 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 07:03:09,620 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-03-20 07:03:09,620 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 07:03:09,640 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-03-20 07:03:09,641 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-03-20 07:03:09,643 INFO L87 Difference]: Start difference. First operand has 28 states, 16 states have (on average 1.375) internal successors, (22), 17 states have internal predecessors, (22), 6 states have call successors, (6), 4 states have call predecessors, (6), 4 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) Second operand has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-03-20 07:03:09,695 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 07:03:09,695 INFO L93 Difference]: Finished difference Result 28 states and 30 transitions. [2022-03-20 07:03:09,696 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-03-20 07:03:09,697 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 17 [2022-03-20 07:03:09,697 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 07:03:09,701 INFO L225 Difference]: With dead ends: 28 [2022-03-20 07:03:09,702 INFO L226 Difference]: Without dead ends: 23 [2022-03-20 07:03:09,703 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-03-20 07:03:09,706 INFO L913 BasicCegarLoop]: 26 mSDtfsCounter, 15 mSDsluCounter, 3 mSDsCounter, 0 mSdLazyCounter, 6 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 29 SdHoareTripleChecker+Invalid, 11 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 6 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 07:03:09,708 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [19 Valid, 29 Invalid, 11 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 6 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 07:03:09,719 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states. [2022-03-20 07:03:09,732 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 23. [2022-03-20 07:03:09,733 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 23 states, 13 states have (on average 1.1538461538461537) internal successors, (15), 14 states have internal predecessors, (15), 6 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2022-03-20 07:03:09,734 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 23 states to 23 states and 25 transitions. [2022-03-20 07:03:09,735 INFO L78 Accepts]: Start accepts. Automaton has 23 states and 25 transitions. Word has length 17 [2022-03-20 07:03:09,735 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 07:03:09,735 INFO L478 AbstractCegarLoop]: Abstraction has 23 states and 25 transitions. [2022-03-20 07:03:09,736 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-03-20 07:03:09,736 INFO L276 IsEmpty]: Start isEmpty. Operand 23 states and 25 transitions. [2022-03-20 07:03:09,736 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2022-03-20 07:03:09,737 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 07:03:09,737 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 07:03:09,737 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-03-20 07:03:09,737 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 07:03:09,737 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 07:03:09,738 INFO L85 PathProgramCache]: Analyzing trace with hash 603980644, now seen corresponding path program 1 times [2022-03-20 07:03:09,738 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 07:03:09,738 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1500138294] [2022-03-20 07:03:09,738 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 07:03:09,739 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 07:03:09,767 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 07:03:09,768 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1218527061] [2022-03-20 07:03:09,768 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 07:03:09,768 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 07:03:09,768 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 07:03:09,776 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 07:03:09,777 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2022-03-20 07:03:09,820 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 07:03:09,822 INFO L263 TraceCheckSpWp]: Trace formula consists of 68 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-20 07:03:09,827 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 07:03:09,934 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-20 07:03:09,934 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-20 07:03:09,934 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 07:03:09,935 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1500138294] [2022-03-20 07:03:09,935 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 07:03:09,935 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1218527061] [2022-03-20 07:03:09,935 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1218527061] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 07:03:09,935 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 07:03:09,935 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-20 07:03:09,936 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1011204632] [2022-03-20 07:03:09,936 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 07:03:09,937 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-20 07:03:09,937 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 07:03:09,937 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-20 07:03:09,937 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-03-20 07:03:09,937 INFO L87 Difference]: Start difference. First operand 23 states and 25 transitions. Second operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-03-20 07:03:09,985 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 07:03:09,986 INFO L93 Difference]: Finished difference Result 32 states and 36 transitions. [2022-03-20 07:03:09,987 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-20 07:03:09,987 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 17 [2022-03-20 07:03:09,987 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 07:03:09,987 INFO L225 Difference]: With dead ends: 32 [2022-03-20 07:03:09,988 INFO L226 Difference]: Without dead ends: 30 [2022-03-20 07:03:09,988 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 17 GetRequests, 13 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-03-20 07:03:09,989 INFO L913 BasicCegarLoop]: 22 mSDtfsCounter, 6 mSDsluCounter, 61 mSDsCounter, 0 mSdLazyCounter, 22 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 83 SdHoareTripleChecker+Invalid, 24 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 22 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 07:03:09,989 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [8 Valid, 83 Invalid, 24 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 22 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 07:03:09,990 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 30 states. [2022-03-20 07:03:09,993 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 30 to 30. [2022-03-20 07:03:09,993 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 30 states, 18 states have (on average 1.1111111111111112) internal successors, (20), 19 states have internal predecessors, (20), 7 states have call successors, (7), 5 states have call predecessors, (7), 4 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-03-20 07:03:09,994 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 32 transitions. [2022-03-20 07:03:09,994 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 32 transitions. Word has length 17 [2022-03-20 07:03:09,994 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 07:03:09,994 INFO L478 AbstractCegarLoop]: Abstraction has 30 states and 32 transitions. [2022-03-20 07:03:09,994 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-03-20 07:03:09,994 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 32 transitions. [2022-03-20 07:03:09,995 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2022-03-20 07:03:09,995 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 07:03:09,995 INFO L499 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 07:03:10,014 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2022-03-20 07:03:10,207 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 07:03:10,208 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 07:03:10,208 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 07:03:10,208 INFO L85 PathProgramCache]: Analyzing trace with hash -169450186, now seen corresponding path program 1 times [2022-03-20 07:03:10,208 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 07:03:10,208 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [894822988] [2022-03-20 07:03:10,209 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 07:03:10,209 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 07:03:10,216 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 07:03:10,216 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [550254461] [2022-03-20 07:03:10,216 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 07:03:10,216 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 07:03:10,216 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 07:03:10,217 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 07:03:10,231 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2022-03-20 07:03:10,272 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 07:03:10,272 INFO L263 TraceCheckSpWp]: Trace formula consists of 85 conjuncts, 11 conjunts are in the unsatisfiable core [2022-03-20 07:03:10,289 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 07:03:10,437 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-20 07:03:10,438 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 07:03:10,751 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2022-03-20 07:03:10,752 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 07:03:10,752 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [894822988] [2022-03-20 07:03:10,752 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 07:03:10,753 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [550254461] [2022-03-20 07:03:10,753 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [550254461] provided 1 perfect and 1 imperfect interpolant sequences [2022-03-20 07:03:10,753 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-03-20 07:03:10,753 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2022-03-20 07:03:10,754 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1589306233] [2022-03-20 07:03:10,754 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 07:03:10,755 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-20 07:03:10,755 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 07:03:10,755 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-20 07:03:10,756 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2022-03-20 07:03:10,756 INFO L87 Difference]: Start difference. First operand 30 states and 32 transitions. Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-03-20 07:03:10,792 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 07:03:10,792 INFO L93 Difference]: Finished difference Result 34 states and 35 transitions. [2022-03-20 07:03:10,792 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-20 07:03:10,792 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 24 [2022-03-20 07:03:10,793 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 07:03:10,793 INFO L225 Difference]: With dead ends: 34 [2022-03-20 07:03:10,793 INFO L226 Difference]: Without dead ends: 31 [2022-03-20 07:03:10,793 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 48 GetRequests, 40 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2022-03-20 07:03:10,794 INFO L913 BasicCegarLoop]: 21 mSDtfsCounter, 6 mSDsluCounter, 55 mSDsCounter, 0 mSdLazyCounter, 16 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 76 SdHoareTripleChecker+Invalid, 17 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 16 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 07:03:10,794 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [7 Valid, 76 Invalid, 17 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 16 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 07:03:10,795 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 31 states. [2022-03-20 07:03:10,797 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 31 to 31. [2022-03-20 07:03:10,797 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 31 states, 20 states have (on average 1.05) internal successors, (21), 20 states have internal predecessors, (21), 6 states have call successors, (6), 6 states have call predecessors, (6), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2022-03-20 07:03:10,798 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 31 states to 31 states and 31 transitions. [2022-03-20 07:03:10,798 INFO L78 Accepts]: Start accepts. Automaton has 31 states and 31 transitions. Word has length 24 [2022-03-20 07:03:10,798 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 07:03:10,798 INFO L478 AbstractCegarLoop]: Abstraction has 31 states and 31 transitions. [2022-03-20 07:03:10,798 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-03-20 07:03:10,798 INFO L276 IsEmpty]: Start isEmpty. Operand 31 states and 31 transitions. [2022-03-20 07:03:10,799 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2022-03-20 07:03:10,799 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 07:03:10,799 INFO L499 BasicCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 07:03:10,816 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2022-03-20 07:03:10,999 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2022-03-20 07:03:11,000 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 07:03:11,000 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 07:03:11,000 INFO L85 PathProgramCache]: Analyzing trace with hash -434891502, now seen corresponding path program 1 times [2022-03-20 07:03:11,001 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 07:03:11,001 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1001707682] [2022-03-20 07:03:11,001 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 07:03:11,001 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 07:03:11,011 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 07:03:11,011 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1697356] [2022-03-20 07:03:11,011 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 07:03:11,011 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 07:03:11,011 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 07:03:11,013 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 07:03:11,014 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2022-03-20 07:03:11,045 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 07:03:11,046 INFO L263 TraceCheckSpWp]: Trace formula consists of 95 conjuncts, 12 conjunts are in the unsatisfiable core [2022-03-20 07:03:11,048 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 07:03:11,224 INFO L134 CoverageAnalysis]: Checked inductivity of 11 backedges. 4 proven. 3 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-03-20 07:03:11,225 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 07:03:11,408 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 07:03:11,408 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1001707682] [2022-03-20 07:03:11,409 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 07:03:11,409 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1697356] [2022-03-20 07:03:11,409 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1697356] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 07:03:11,409 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 07:03:11,409 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2022-03-20 07:03:11,409 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1404166330] [2022-03-20 07:03:11,409 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-03-20 07:03:11,410 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-03-20 07:03:11,410 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 07:03:11,410 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-03-20 07:03:11,410 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=24, Invalid=66, Unknown=0, NotChecked=0, Total=90 [2022-03-20 07:03:11,410 INFO L87 Difference]: Start difference. First operand 31 states and 31 transitions. Second operand has 7 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 6 states have internal predecessors, (17), 4 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2022-03-20 07:03:11,461 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 07:03:11,461 INFO L93 Difference]: Finished difference Result 37 states and 38 transitions. [2022-03-20 07:03:11,462 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-03-20 07:03:11,462 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 6 states have internal predecessors, (17), 4 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) Word has length 30 [2022-03-20 07:03:11,462 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 07:03:11,463 INFO L225 Difference]: With dead ends: 37 [2022-03-20 07:03:11,463 INFO L226 Difference]: Without dead ends: 34 [2022-03-20 07:03:11,464 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 44 GetRequests, 33 SyntacticMatches, 1 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=34, Invalid=98, Unknown=0, NotChecked=0, Total=132 [2022-03-20 07:03:11,467 INFO L913 BasicCegarLoop]: 25 mSDtfsCounter, 2 mSDsluCounter, 104 mSDsCounter, 0 mSdLazyCounter, 37 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 129 SdHoareTripleChecker+Invalid, 37 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 37 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 07:03:11,471 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 129 Invalid, 37 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 37 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 07:03:11,473 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 34 states. [2022-03-20 07:03:11,481 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 34 to 34. [2022-03-20 07:03:11,481 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 34 states, 22 states have (on average 1.0454545454545454) internal successors, (23), 22 states have internal predecessors, (23), 7 states have call successors, (7), 6 states have call predecessors, (7), 4 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-03-20 07:03:11,482 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 34 states to 34 states and 35 transitions. [2022-03-20 07:03:11,482 INFO L78 Accepts]: Start accepts. Automaton has 34 states and 35 transitions. Word has length 30 [2022-03-20 07:03:11,483 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 07:03:11,483 INFO L478 AbstractCegarLoop]: Abstraction has 34 states and 35 transitions. [2022-03-20 07:03:11,484 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 6 states have internal predecessors, (17), 4 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2022-03-20 07:03:11,484 INFO L276 IsEmpty]: Start isEmpty. Operand 34 states and 35 transitions. [2022-03-20 07:03:11,487 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2022-03-20 07:03:11,487 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 07:03:11,489 INFO L499 BasicCegarLoop]: trace histogram [4, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 07:03:11,512 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2022-03-20 07:03:11,689 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 07:03:11,690 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 07:03:11,690 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 07:03:11,690 INFO L85 PathProgramCache]: Analyzing trace with hash 725792896, now seen corresponding path program 2 times [2022-03-20 07:03:11,690 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 07:03:11,691 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [814118368] [2022-03-20 07:03:11,691 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 07:03:11,691 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 07:03:11,700 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 07:03:11,701 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1781523580] [2022-03-20 07:03:11,701 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 07:03:11,701 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 07:03:11,701 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 07:03:11,705 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 07:03:11,706 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2022-03-20 07:03:11,752 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 07:03:11,752 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 07:03:11,753 INFO L263 TraceCheckSpWp]: Trace formula consists of 112 conjuncts, 16 conjunts are in the unsatisfiable core [2022-03-20 07:03:11,754 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 07:03:11,903 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 6 proven. 9 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-03-20 07:03:11,903 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 07:03:12,036 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 07:03:12,036 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [814118368] [2022-03-20 07:03:12,036 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 07:03:12,036 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1781523580] [2022-03-20 07:03:12,037 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1781523580] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 07:03:12,037 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 07:03:12,037 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8] total 8 [2022-03-20 07:03:12,037 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [633979772] [2022-03-20 07:03:12,037 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-03-20 07:03:12,039 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-03-20 07:03:12,039 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 07:03:12,040 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-03-20 07:03:12,040 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=83, Unknown=0, NotChecked=0, Total=110 [2022-03-20 07:03:12,040 INFO L87 Difference]: Start difference. First operand 34 states and 35 transitions. Second operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 7 states have internal predecessors, (19), 5 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 4 states have call predecessors, (5), 4 states have call successors, (5) [2022-03-20 07:03:12,102 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 07:03:12,102 INFO L93 Difference]: Finished difference Result 40 states and 42 transitions. [2022-03-20 07:03:12,103 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-03-20 07:03:12,103 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 7 states have internal predecessors, (19), 5 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 4 states have call predecessors, (5), 4 states have call successors, (5) Word has length 37 [2022-03-20 07:03:12,103 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 07:03:12,103 INFO L225 Difference]: With dead ends: 40 [2022-03-20 07:03:12,104 INFO L226 Difference]: Without dead ends: 37 [2022-03-20 07:03:12,104 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 51 GetRequests, 39 SyntacticMatches, 1 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=37, Invalid=119, Unknown=0, NotChecked=0, Total=156 [2022-03-20 07:03:12,104 INFO L913 BasicCegarLoop]: 28 mSDtfsCounter, 2 mSDsluCounter, 137 mSDsCounter, 0 mSdLazyCounter, 55 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 165 SdHoareTripleChecker+Invalid, 55 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 55 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 07:03:12,105 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 165 Invalid, 55 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 55 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 07:03:12,105 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 37 states. [2022-03-20 07:03:12,107 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 37 to 37. [2022-03-20 07:03:12,107 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 37 states, 24 states have (on average 1.0416666666666667) internal successors, (25), 24 states have internal predecessors, (25), 8 states have call successors, (8), 6 states have call predecessors, (8), 4 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-03-20 07:03:12,108 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 39 transitions. [2022-03-20 07:03:12,108 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 39 transitions. Word has length 37 [2022-03-20 07:03:12,108 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 07:03:12,108 INFO L478 AbstractCegarLoop]: Abstraction has 37 states and 39 transitions. [2022-03-20 07:03:12,108 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 7 states have internal predecessors, (19), 5 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 4 states have call predecessors, (5), 4 states have call successors, (5) [2022-03-20 07:03:12,108 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 39 transitions. [2022-03-20 07:03:12,109 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2022-03-20 07:03:12,109 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 07:03:12,109 INFO L499 BasicCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 07:03:12,127 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2022-03-20 07:03:12,323 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 07:03:12,323 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 07:03:12,323 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 07:03:12,323 INFO L85 PathProgramCache]: Analyzing trace with hash 1487404370, now seen corresponding path program 3 times [2022-03-20 07:03:12,324 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 07:03:12,324 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [740069375] [2022-03-20 07:03:12,324 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 07:03:12,324 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 07:03:12,330 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 07:03:12,330 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1956490076] [2022-03-20 07:03:12,331 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-03-20 07:03:12,331 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 07:03:12,331 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 07:03:12,333 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 07:03:12,334 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2022-03-20 07:03:12,432 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2022-03-20 07:03:12,433 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 07:03:12,434 INFO L263 TraceCheckSpWp]: Trace formula consists of 129 conjuncts, 20 conjunts are in the unsatisfiable core [2022-03-20 07:03:12,435 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 07:03:12,575 INFO L134 CoverageAnalysis]: Checked inductivity of 50 backedges. 8 proven. 18 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-03-20 07:03:12,575 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 07:03:12,672 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 07:03:12,672 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [740069375] [2022-03-20 07:03:12,672 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 07:03:12,672 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1956490076] [2022-03-20 07:03:12,672 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1956490076] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 07:03:12,672 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 07:03:12,672 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2022-03-20 07:03:12,672 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [543996369] [2022-03-20 07:03:12,672 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-03-20 07:03:12,673 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-03-20 07:03:12,673 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 07:03:12,673 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-03-20 07:03:12,673 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2022-03-20 07:03:12,673 INFO L87 Difference]: Start difference. First operand 37 states and 39 transitions. Second operand has 9 states, 8 states have (on average 2.625) internal successors, (21), 8 states have internal predecessors, (21), 6 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) [2022-03-20 07:03:12,738 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 07:03:12,738 INFO L93 Difference]: Finished difference Result 43 states and 46 transitions. [2022-03-20 07:03:12,739 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-03-20 07:03:12,739 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 2.625) internal successors, (21), 8 states have internal predecessors, (21), 6 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) Word has length 44 [2022-03-20 07:03:12,739 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 07:03:12,739 INFO L225 Difference]: With dead ends: 43 [2022-03-20 07:03:12,739 INFO L226 Difference]: Without dead ends: 40 [2022-03-20 07:03:12,740 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 58 GetRequests, 45 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=40, Invalid=142, Unknown=0, NotChecked=0, Total=182 [2022-03-20 07:03:12,740 INFO L913 BasicCegarLoop]: 31 mSDtfsCounter, 2 mSDsluCounter, 174 mSDsCounter, 0 mSdLazyCounter, 77 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 205 SdHoareTripleChecker+Invalid, 77 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 77 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 07:03:12,740 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 205 Invalid, 77 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 77 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 07:03:12,741 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 40 states. [2022-03-20 07:03:12,742 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 40 to 40. [2022-03-20 07:03:12,743 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 40 states, 26 states have (on average 1.0384615384615385) internal successors, (27), 26 states have internal predecessors, (27), 9 states have call successors, (9), 6 states have call predecessors, (9), 4 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-03-20 07:03:12,743 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 40 states to 40 states and 43 transitions. [2022-03-20 07:03:12,743 INFO L78 Accepts]: Start accepts. Automaton has 40 states and 43 transitions. Word has length 44 [2022-03-20 07:03:12,743 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 07:03:12,743 INFO L478 AbstractCegarLoop]: Abstraction has 40 states and 43 transitions. [2022-03-20 07:03:12,743 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 8 states have (on average 2.625) internal successors, (21), 8 states have internal predecessors, (21), 6 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) [2022-03-20 07:03:12,744 INFO L276 IsEmpty]: Start isEmpty. Operand 40 states and 43 transitions. [2022-03-20 07:03:12,744 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2022-03-20 07:03:12,744 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 07:03:12,744 INFO L499 BasicCegarLoop]: trace histogram [6, 5, 5, 5, 5, 5, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 07:03:12,751 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2022-03-20 07:03:12,949 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 07:03:12,950 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 07:03:12,950 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 07:03:12,950 INFO L85 PathProgramCache]: Analyzing trace with hash 1178929216, now seen corresponding path program 4 times [2022-03-20 07:03:12,950 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 07:03:12,951 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1832581643] [2022-03-20 07:03:12,951 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 07:03:12,951 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 07:03:12,963 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 07:03:12,964 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [753261440] [2022-03-20 07:03:12,964 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-03-20 07:03:12,964 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 07:03:12,964 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 07:03:12,966 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 07:03:12,967 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2022-03-20 07:03:13,186 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-03-20 07:03:13,186 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 07:03:13,187 INFO L263 TraceCheckSpWp]: Trace formula consists of 115 conjuncts, 24 conjunts are in the unsatisfiable core [2022-03-20 07:03:13,189 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 07:03:13,383 INFO L134 CoverageAnalysis]: Checked inductivity of 80 backedges. 10 proven. 30 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2022-03-20 07:03:13,384 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 07:03:13,487 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 07:03:13,487 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1832581643] [2022-03-20 07:03:13,487 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 07:03:13,487 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [753261440] [2022-03-20 07:03:13,487 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [753261440] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 07:03:13,487 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 07:03:13,487 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2022-03-20 07:03:13,488 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [879714350] [2022-03-20 07:03:13,488 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-03-20 07:03:13,488 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-03-20 07:03:13,489 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 07:03:13,490 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-03-20 07:03:13,490 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=123, Unknown=0, NotChecked=0, Total=156 [2022-03-20 07:03:13,490 INFO L87 Difference]: Start difference. First operand 40 states and 43 transitions. Second operand has 10 states, 9 states have (on average 2.5555555555555554) internal successors, (23), 9 states have internal predecessors, (23), 7 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 6 states have call predecessors, (7), 6 states have call successors, (7) [2022-03-20 07:03:13,576 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 07:03:13,576 INFO L93 Difference]: Finished difference Result 46 states and 50 transitions. [2022-03-20 07:03:13,577 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-03-20 07:03:13,577 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 9 states have (on average 2.5555555555555554) internal successors, (23), 9 states have internal predecessors, (23), 7 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 6 states have call predecessors, (7), 6 states have call successors, (7) Word has length 51 [2022-03-20 07:03:13,577 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 07:03:13,577 INFO L225 Difference]: With dead ends: 46 [2022-03-20 07:03:13,578 INFO L226 Difference]: Without dead ends: 43 [2022-03-20 07:03:13,578 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 65 GetRequests, 51 SyntacticMatches, 1 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=43, Invalid=167, Unknown=0, NotChecked=0, Total=210 [2022-03-20 07:03:13,578 INFO L913 BasicCegarLoop]: 34 mSDtfsCounter, 2 mSDsluCounter, 215 mSDsCounter, 0 mSdLazyCounter, 103 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 249 SdHoareTripleChecker+Invalid, 103 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 103 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 07:03:13,578 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 249 Invalid, 103 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 103 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 07:03:13,579 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2022-03-20 07:03:13,581 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 43. [2022-03-20 07:03:13,581 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 43 states, 28 states have (on average 1.0357142857142858) internal successors, (29), 28 states have internal predecessors, (29), 10 states have call successors, (10), 6 states have call predecessors, (10), 4 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-03-20 07:03:13,581 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 47 transitions. [2022-03-20 07:03:13,581 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 47 transitions. Word has length 51 [2022-03-20 07:03:13,581 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 07:03:13,582 INFO L478 AbstractCegarLoop]: Abstraction has 43 states and 47 transitions. [2022-03-20 07:03:13,582 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 9 states have (on average 2.5555555555555554) internal successors, (23), 9 states have internal predecessors, (23), 7 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 6 states have call predecessors, (7), 6 states have call successors, (7) [2022-03-20 07:03:13,582 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 47 transitions. [2022-03-20 07:03:13,582 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2022-03-20 07:03:13,582 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 07:03:13,583 INFO L499 BasicCegarLoop]: trace histogram [7, 6, 6, 6, 6, 6, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 07:03:13,599 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2022-03-20 07:03:13,799 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 07:03:13,800 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 07:03:13,800 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 07:03:13,800 INFO L85 PathProgramCache]: Analyzing trace with hash -1658817134, now seen corresponding path program 5 times [2022-03-20 07:03:13,800 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 07:03:13,800 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [821612177] [2022-03-20 07:03:13,800 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 07:03:13,800 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 07:03:13,806 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 07:03:13,807 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1556951523] [2022-03-20 07:03:13,807 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2022-03-20 07:03:13,807 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 07:03:13,807 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 07:03:13,808 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 07:03:13,809 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2022-03-20 07:03:13,917 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2022-03-20 07:03:13,917 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 07:03:13,918 INFO L263 TraceCheckSpWp]: Trace formula consists of 163 conjuncts, 28 conjunts are in the unsatisfiable core [2022-03-20 07:03:13,920 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 07:03:14,094 INFO L134 CoverageAnalysis]: Checked inductivity of 117 backedges. 12 proven. 45 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2022-03-20 07:03:14,095 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 07:03:14,204 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 07:03:14,204 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [821612177] [2022-03-20 07:03:14,204 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 07:03:14,204 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1556951523] [2022-03-20 07:03:14,205 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1556951523] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 07:03:14,205 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 07:03:14,205 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11] total 11 [2022-03-20 07:03:14,205 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [781209163] [2022-03-20 07:03:14,205 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-03-20 07:03:14,206 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2022-03-20 07:03:14,206 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 07:03:14,206 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2022-03-20 07:03:14,206 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=36, Invalid=146, Unknown=0, NotChecked=0, Total=182 [2022-03-20 07:03:14,206 INFO L87 Difference]: Start difference. First operand 43 states and 47 transitions. Second operand has 11 states, 10 states have (on average 2.5) internal successors, (25), 10 states have internal predecessors, (25), 8 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 7 states have call predecessors, (8), 7 states have call successors, (8) [2022-03-20 07:03:14,312 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 07:03:14,313 INFO L93 Difference]: Finished difference Result 49 states and 54 transitions. [2022-03-20 07:03:14,313 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2022-03-20 07:03:14,313 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 10 states have (on average 2.5) internal successors, (25), 10 states have internal predecessors, (25), 8 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 7 states have call predecessors, (8), 7 states have call successors, (8) Word has length 58 [2022-03-20 07:03:14,313 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 07:03:14,314 INFO L225 Difference]: With dead ends: 49 [2022-03-20 07:03:14,314 INFO L226 Difference]: Without dead ends: 46 [2022-03-20 07:03:14,314 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 72 GetRequests, 57 SyntacticMatches, 1 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=46, Invalid=194, Unknown=0, NotChecked=0, Total=240 [2022-03-20 07:03:14,314 INFO L913 BasicCegarLoop]: 37 mSDtfsCounter, 2 mSDsluCounter, 260 mSDsCounter, 0 mSdLazyCounter, 133 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 297 SdHoareTripleChecker+Invalid, 133 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 133 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 07:03:14,315 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 297 Invalid, 133 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 133 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 07:03:14,315 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 46 states. [2022-03-20 07:03:14,317 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 46 to 46. [2022-03-20 07:03:14,317 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 46 states, 30 states have (on average 1.0333333333333334) internal successors, (31), 30 states have internal predecessors, (31), 11 states have call successors, (11), 6 states have call predecessors, (11), 4 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-03-20 07:03:14,317 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 51 transitions. [2022-03-20 07:03:14,318 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 51 transitions. Word has length 58 [2022-03-20 07:03:14,318 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 07:03:14,318 INFO L478 AbstractCegarLoop]: Abstraction has 46 states and 51 transitions. [2022-03-20 07:03:14,318 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 10 states have (on average 2.5) internal successors, (25), 10 states have internal predecessors, (25), 8 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 7 states have call predecessors, (8), 7 states have call successors, (8) [2022-03-20 07:03:14,318 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 51 transitions. [2022-03-20 07:03:14,318 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 66 [2022-03-20 07:03:14,318 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 07:03:14,319 INFO L499 BasicCegarLoop]: trace histogram [8, 7, 7, 7, 7, 7, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 07:03:14,334 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2022-03-20 07:03:14,519 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 07:03:14,519 INFO L403 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 07:03:14,520 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 07:03:14,520 INFO L85 PathProgramCache]: Analyzing trace with hash 270583808, now seen corresponding path program 6 times [2022-03-20 07:03:14,520 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 07:03:14,520 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [107046894] [2022-03-20 07:03:14,520 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 07:03:14,520 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 07:03:14,526 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 07:03:14,526 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [633419280] [2022-03-20 07:03:14,526 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-03-20 07:03:14,527 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 07:03:14,527 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 07:03:14,528 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 07:03:14,529 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2022-03-20 07:03:14,664 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2022-03-20 07:03:14,664 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 07:03:14,665 INFO L263 TraceCheckSpWp]: Trace formula consists of 180 conjuncts, 32 conjunts are in the unsatisfiable core [2022-03-20 07:03:14,667 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 07:03:14,897 INFO L134 CoverageAnalysis]: Checked inductivity of 161 backedges. 14 proven. 63 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2022-03-20 07:03:14,897 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 07:03:15,005 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 07:03:15,005 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [107046894] [2022-03-20 07:03:15,006 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 07:03:15,006 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [633419280] [2022-03-20 07:03:15,006 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [633419280] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 07:03:15,006 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 07:03:15,006 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12] total 12 [2022-03-20 07:03:15,006 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [961315538] [2022-03-20 07:03:15,006 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-03-20 07:03:15,006 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2022-03-20 07:03:15,006 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 07:03:15,007 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-03-20 07:03:15,007 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=39, Invalid=171, Unknown=0, NotChecked=0, Total=210 [2022-03-20 07:03:15,007 INFO L87 Difference]: Start difference. First operand 46 states and 51 transitions. Second operand has 12 states, 11 states have (on average 2.4545454545454546) internal successors, (27), 11 states have internal predecessors, (27), 9 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 8 states have call predecessors, (9), 8 states have call successors, (9) [2022-03-20 07:03:15,112 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 07:03:15,112 INFO L93 Difference]: Finished difference Result 52 states and 58 transitions. [2022-03-20 07:03:15,112 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2022-03-20 07:03:15,112 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 11 states have (on average 2.4545454545454546) internal successors, (27), 11 states have internal predecessors, (27), 9 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 8 states have call predecessors, (9), 8 states have call successors, (9) Word has length 65 [2022-03-20 07:03:15,113 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 07:03:15,113 INFO L225 Difference]: With dead ends: 52 [2022-03-20 07:03:15,113 INFO L226 Difference]: Without dead ends: 49 [2022-03-20 07:03:15,113 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 79 GetRequests, 63 SyntacticMatches, 1 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=49, Invalid=223, Unknown=0, NotChecked=0, Total=272 [2022-03-20 07:03:15,114 INFO L913 BasicCegarLoop]: 40 mSDtfsCounter, 2 mSDsluCounter, 309 mSDsCounter, 0 mSdLazyCounter, 167 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 349 SdHoareTripleChecker+Invalid, 167 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 167 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 07:03:15,114 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 349 Invalid, 167 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 167 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 07:03:15,114 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 49 states. [2022-03-20 07:03:15,116 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 49 to 49. [2022-03-20 07:03:15,117 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 49 states, 32 states have (on average 1.03125) internal successors, (33), 32 states have internal predecessors, (33), 12 states have call successors, (12), 6 states have call predecessors, (12), 4 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-03-20 07:03:15,117 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 49 states to 49 states and 55 transitions. [2022-03-20 07:03:15,117 INFO L78 Accepts]: Start accepts. Automaton has 49 states and 55 transitions. Word has length 65 [2022-03-20 07:03:15,117 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 07:03:15,117 INFO L478 AbstractCegarLoop]: Abstraction has 49 states and 55 transitions. [2022-03-20 07:03:15,117 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 11 states have (on average 2.4545454545454546) internal successors, (27), 11 states have internal predecessors, (27), 9 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 8 states have call predecessors, (9), 8 states have call successors, (9) [2022-03-20 07:03:15,117 INFO L276 IsEmpty]: Start isEmpty. Operand 49 states and 55 transitions. [2022-03-20 07:03:15,118 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 73 [2022-03-20 07:03:15,118 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 07:03:15,118 INFO L499 BasicCegarLoop]: trace histogram [9, 8, 8, 8, 8, 8, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 07:03:15,125 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2022-03-20 07:03:15,323 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable8 [2022-03-20 07:03:15,324 INFO L403 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 07:03:15,324 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 07:03:15,324 INFO L85 PathProgramCache]: Analyzing trace with hash 4292050, now seen corresponding path program 7 times [2022-03-20 07:03:15,324 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 07:03:15,324 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [409152302] [2022-03-20 07:03:15,324 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 07:03:15,325 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 07:03:15,330 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 07:03:15,331 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [442613643] [2022-03-20 07:03:15,331 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2022-03-20 07:03:15,331 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 07:03:15,331 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 07:03:15,332 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 07:03:15,333 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2022-03-20 07:03:15,614 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 07:03:15,616 INFO L263 TraceCheckSpWp]: Trace formula consists of 197 conjuncts, 36 conjunts are in the unsatisfiable core [2022-03-20 07:03:15,617 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 07:03:15,851 INFO L134 CoverageAnalysis]: Checked inductivity of 212 backedges. 16 proven. 84 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2022-03-20 07:03:15,851 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 07:03:15,969 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 07:03:15,969 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [409152302] [2022-03-20 07:03:15,969 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 07:03:15,969 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [442613643] [2022-03-20 07:03:15,969 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [442613643] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 07:03:15,969 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 07:03:15,969 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2022-03-20 07:03:15,969 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1041596405] [2022-03-20 07:03:15,969 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-03-20 07:03:15,970 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2022-03-20 07:03:15,970 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 07:03:15,970 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2022-03-20 07:03:15,970 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=42, Invalid=198, Unknown=0, NotChecked=0, Total=240 [2022-03-20 07:03:15,970 INFO L87 Difference]: Start difference. First operand 49 states and 55 transitions. Second operand has 13 states, 12 states have (on average 2.4166666666666665) internal successors, (29), 12 states have internal predecessors, (29), 10 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (10), 9 states have call predecessors, (10), 9 states have call successors, (10) [2022-03-20 07:03:16,118 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 07:03:16,119 INFO L93 Difference]: Finished difference Result 55 states and 62 transitions. [2022-03-20 07:03:16,119 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2022-03-20 07:03:16,119 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 12 states have (on average 2.4166666666666665) internal successors, (29), 12 states have internal predecessors, (29), 10 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (10), 9 states have call predecessors, (10), 9 states have call successors, (10) Word has length 72 [2022-03-20 07:03:16,119 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 07:03:16,120 INFO L225 Difference]: With dead ends: 55 [2022-03-20 07:03:16,120 INFO L226 Difference]: Without dead ends: 52 [2022-03-20 07:03:16,120 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 86 GetRequests, 69 SyntacticMatches, 1 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=52, Invalid=254, Unknown=0, NotChecked=0, Total=306 [2022-03-20 07:03:16,120 INFO L913 BasicCegarLoop]: 43 mSDtfsCounter, 2 mSDsluCounter, 362 mSDsCounter, 0 mSdLazyCounter, 205 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 405 SdHoareTripleChecker+Invalid, 205 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 205 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 07:03:16,121 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 405 Invalid, 205 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 205 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 07:03:16,121 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 52 states. [2022-03-20 07:03:16,123 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 52 to 52. [2022-03-20 07:03:16,123 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 52 states, 34 states have (on average 1.0294117647058822) internal successors, (35), 34 states have internal predecessors, (35), 13 states have call successors, (13), 6 states have call predecessors, (13), 4 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-03-20 07:03:16,124 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 52 states to 52 states and 59 transitions. [2022-03-20 07:03:16,124 INFO L78 Accepts]: Start accepts. Automaton has 52 states and 59 transitions. Word has length 72 [2022-03-20 07:03:16,124 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 07:03:16,124 INFO L478 AbstractCegarLoop]: Abstraction has 52 states and 59 transitions. [2022-03-20 07:03:16,124 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 12 states have (on average 2.4166666666666665) internal successors, (29), 12 states have internal predecessors, (29), 10 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (10), 9 states have call predecessors, (10), 9 states have call successors, (10) [2022-03-20 07:03:16,124 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 59 transitions. [2022-03-20 07:03:16,125 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 80 [2022-03-20 07:03:16,125 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 07:03:16,125 INFO L499 BasicCegarLoop]: trace histogram [10, 9, 9, 9, 9, 9, 8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 07:03:16,135 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2022-03-20 07:03:16,330 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2022-03-20 07:03:16,331 INFO L403 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 07:03:16,331 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 07:03:16,331 INFO L85 PathProgramCache]: Analyzing trace with hash 395442112, now seen corresponding path program 8 times [2022-03-20 07:03:16,331 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 07:03:16,331 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1727591355] [2022-03-20 07:03:16,331 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 07:03:16,331 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 07:03:16,338 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 07:03:16,338 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [625725024] [2022-03-20 07:03:16,338 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 07:03:16,338 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 07:03:16,338 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 07:03:16,339 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 07:03:16,344 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2022-03-20 07:03:16,915 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 07:03:16,915 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 07:03:16,916 INFO L263 TraceCheckSpWp]: Trace formula consists of 214 conjuncts, 40 conjunts are in the unsatisfiable core [2022-03-20 07:03:16,918 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 07:03:17,179 INFO L134 CoverageAnalysis]: Checked inductivity of 270 backedges. 18 proven. 108 refuted. 0 times theorem prover too weak. 144 trivial. 0 not checked. [2022-03-20 07:03:17,179 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 07:03:17,324 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 07:03:17,324 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1727591355] [2022-03-20 07:03:17,324 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 07:03:17,324 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [625725024] [2022-03-20 07:03:17,324 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [625725024] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 07:03:17,324 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 07:03:17,324 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14] total 14 [2022-03-20 07:03:17,325 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [337926573] [2022-03-20 07:03:17,325 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-03-20 07:03:17,325 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2022-03-20 07:03:17,325 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 07:03:17,325 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2022-03-20 07:03:17,325 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=45, Invalid=227, Unknown=0, NotChecked=0, Total=272 [2022-03-20 07:03:17,326 INFO L87 Difference]: Start difference. First operand 52 states and 59 transitions. Second operand has 14 states, 13 states have (on average 2.3846153846153846) internal successors, (31), 13 states have internal predecessors, (31), 11 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (11), 10 states have call predecessors, (11), 10 states have call successors, (11) [2022-03-20 07:03:17,479 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 07:03:17,479 INFO L93 Difference]: Finished difference Result 58 states and 66 transitions. [2022-03-20 07:03:17,480 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2022-03-20 07:03:17,480 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 13 states have (on average 2.3846153846153846) internal successors, (31), 13 states have internal predecessors, (31), 11 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (11), 10 states have call predecessors, (11), 10 states have call successors, (11) Word has length 79 [2022-03-20 07:03:17,480 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 07:03:17,480 INFO L225 Difference]: With dead ends: 58 [2022-03-20 07:03:17,481 INFO L226 Difference]: Without dead ends: 55 [2022-03-20 07:03:17,481 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 93 GetRequests, 75 SyntacticMatches, 1 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=55, Invalid=287, Unknown=0, NotChecked=0, Total=342 [2022-03-20 07:03:17,481 INFO L913 BasicCegarLoop]: 46 mSDtfsCounter, 2 mSDsluCounter, 419 mSDsCounter, 0 mSdLazyCounter, 247 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 465 SdHoareTripleChecker+Invalid, 247 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 247 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 07:03:17,481 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 465 Invalid, 247 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 247 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 07:03:17,482 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2022-03-20 07:03:17,484 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 55. [2022-03-20 07:03:17,484 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 55 states, 36 states have (on average 1.0277777777777777) internal successors, (37), 36 states have internal predecessors, (37), 14 states have call successors, (14), 6 states have call predecessors, (14), 4 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-03-20 07:03:17,484 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 63 transitions. [2022-03-20 07:03:17,485 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 63 transitions. Word has length 79 [2022-03-20 07:03:17,485 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 07:03:17,485 INFO L478 AbstractCegarLoop]: Abstraction has 55 states and 63 transitions. [2022-03-20 07:03:17,485 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 13 states have (on average 2.3846153846153846) internal successors, (31), 13 states have internal predecessors, (31), 11 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (11), 10 states have call predecessors, (11), 10 states have call successors, (11) [2022-03-20 07:03:17,485 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 63 transitions. [2022-03-20 07:03:17,486 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 87 [2022-03-20 07:03:17,486 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 07:03:17,486 INFO L499 BasicCegarLoop]: trace histogram [11, 10, 10, 10, 10, 10, 9, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 07:03:17,498 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2022-03-20 07:03:17,690 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2022-03-20 07:03:17,691 INFO L403 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 07:03:17,691 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 07:03:17,691 INFO L85 PathProgramCache]: Analyzing trace with hash 667883026, now seen corresponding path program 9 times [2022-03-20 07:03:17,691 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 07:03:17,691 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [421611950] [2022-03-20 07:03:17,691 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 07:03:17,691 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 07:03:17,697 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 07:03:17,697 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1012597348] [2022-03-20 07:03:17,698 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-03-20 07:03:17,698 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 07:03:17,698 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 07:03:17,699 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 07:03:17,700 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2022-03-20 07:03:18,045 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 10 check-sat command(s) [2022-03-20 07:03:18,046 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 07:03:18,047 INFO L263 TraceCheckSpWp]: Trace formula consists of 231 conjuncts, 45 conjunts are in the unsatisfiable core [2022-03-20 07:03:18,049 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 07:03:18,341 INFO L134 CoverageAnalysis]: Checked inductivity of 335 backedges. 20 proven. 135 refuted. 0 times theorem prover too weak. 180 trivial. 0 not checked. [2022-03-20 07:03:18,341 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 07:03:18,547 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 07:03:18,547 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [421611950] [2022-03-20 07:03:18,548 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 07:03:18,548 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1012597348] [2022-03-20 07:03:18,548 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1012597348] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 07:03:18,548 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 07:03:18,548 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15] total 15 [2022-03-20 07:03:18,548 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1329859483] [2022-03-20 07:03:18,548 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-03-20 07:03:18,548 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2022-03-20 07:03:18,548 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 07:03:18,549 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2022-03-20 07:03:18,549 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=309, Unknown=0, NotChecked=0, Total=380 [2022-03-20 07:03:18,549 INFO L87 Difference]: Start difference. First operand 55 states and 63 transitions. Second operand has 15 states, 14 states have (on average 2.357142857142857) internal successors, (33), 14 states have internal predecessors, (33), 12 states have call successors, (14), 2 states have call predecessors, (14), 1 states have return successors, (12), 11 states have call predecessors, (12), 11 states have call successors, (12) [2022-03-20 07:03:18,728 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 07:03:18,729 INFO L93 Difference]: Finished difference Result 61 states and 70 transitions. [2022-03-20 07:03:18,729 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2022-03-20 07:03:18,729 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 14 states have (on average 2.357142857142857) internal successors, (33), 14 states have internal predecessors, (33), 12 states have call successors, (14), 2 states have call predecessors, (14), 1 states have return successors, (12), 11 states have call predecessors, (12), 11 states have call successors, (12) Word has length 86 [2022-03-20 07:03:18,729 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 07:03:18,730 INFO L225 Difference]: With dead ends: 61 [2022-03-20 07:03:18,730 INFO L226 Difference]: Without dead ends: 58 [2022-03-20 07:03:18,730 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 114 GetRequests, 93 SyntacticMatches, 1 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=81, Invalid=381, Unknown=0, NotChecked=0, Total=462 [2022-03-20 07:03:18,730 INFO L913 BasicCegarLoop]: 49 mSDtfsCounter, 2 mSDsluCounter, 480 mSDsCounter, 0 mSdLazyCounter, 293 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 529 SdHoareTripleChecker+Invalid, 293 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 293 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-03-20 07:03:18,731 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 529 Invalid, 293 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 293 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-03-20 07:03:18,731 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 58 states. [2022-03-20 07:03:18,733 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 58 to 58. [2022-03-20 07:03:18,733 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 58 states, 38 states have (on average 1.0263157894736843) internal successors, (39), 38 states have internal predecessors, (39), 15 states have call successors, (15), 6 states have call predecessors, (15), 4 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2022-03-20 07:03:18,733 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 67 transitions. [2022-03-20 07:03:18,734 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 67 transitions. Word has length 86 [2022-03-20 07:03:18,734 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 07:03:18,734 INFO L478 AbstractCegarLoop]: Abstraction has 58 states and 67 transitions. [2022-03-20 07:03:18,734 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 14 states have (on average 2.357142857142857) internal successors, (33), 14 states have internal predecessors, (33), 12 states have call successors, (14), 2 states have call predecessors, (14), 1 states have return successors, (12), 11 states have call predecessors, (12), 11 states have call successors, (12) [2022-03-20 07:03:18,734 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 67 transitions. [2022-03-20 07:03:18,735 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 94 [2022-03-20 07:03:18,735 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 07:03:18,735 INFO L499 BasicCegarLoop]: trace histogram [12, 11, 11, 11, 11, 11, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 07:03:18,741 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2022-03-20 07:03:18,940 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2022-03-20 07:03:18,940 INFO L403 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 07:03:18,940 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 07:03:18,940 INFO L85 PathProgramCache]: Analyzing trace with hash 1918146432, now seen corresponding path program 10 times [2022-03-20 07:03:18,940 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 07:03:18,940 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1729291085] [2022-03-20 07:03:18,941 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 07:03:18,941 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 07:03:18,946 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 07:03:18,947 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [991189645] [2022-03-20 07:03:18,947 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-03-20 07:03:18,947 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 07:03:18,947 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 07:03:18,948 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 07:03:18,949 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2022-03-20 07:03:19,442 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-03-20 07:03:19,443 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 07:03:19,444 INFO L263 TraceCheckSpWp]: Trace formula consists of 217 conjuncts, 48 conjunts are in the unsatisfiable core [2022-03-20 07:03:19,446 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 07:03:19,722 INFO L134 CoverageAnalysis]: Checked inductivity of 407 backedges. 22 proven. 165 refuted. 0 times theorem prover too weak. 220 trivial. 0 not checked. [2022-03-20 07:03:19,723 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 07:03:19,897 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 07:03:19,897 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1729291085] [2022-03-20 07:03:19,897 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 07:03:19,897 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [991189645] [2022-03-20 07:03:19,897 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [991189645] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 07:03:19,897 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 07:03:19,897 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16] total 16 [2022-03-20 07:03:19,897 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2070351106] [2022-03-20 07:03:19,897 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-03-20 07:03:19,898 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2022-03-20 07:03:19,898 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 07:03:19,898 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2022-03-20 07:03:19,898 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=51, Invalid=291, Unknown=0, NotChecked=0, Total=342 [2022-03-20 07:03:19,898 INFO L87 Difference]: Start difference. First operand 58 states and 67 transitions. Second operand has 16 states, 15 states have (on average 2.3333333333333335) internal successors, (35), 15 states have internal predecessors, (35), 13 states have call successors, (15), 2 states have call predecessors, (15), 1 states have return successors, (13), 12 states have call predecessors, (13), 12 states have call successors, (13) [2022-03-20 07:03:20,108 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 07:03:20,108 INFO L93 Difference]: Finished difference Result 64 states and 74 transitions. [2022-03-20 07:03:20,108 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2022-03-20 07:03:20,108 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 15 states have (on average 2.3333333333333335) internal successors, (35), 15 states have internal predecessors, (35), 13 states have call successors, (15), 2 states have call predecessors, (15), 1 states have return successors, (13), 12 states have call predecessors, (13), 12 states have call successors, (13) Word has length 93 [2022-03-20 07:03:20,108 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 07:03:20,109 INFO L225 Difference]: With dead ends: 64 [2022-03-20 07:03:20,109 INFO L226 Difference]: Without dead ends: 61 [2022-03-20 07:03:20,109 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 107 GetRequests, 87 SyntacticMatches, 1 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=61, Invalid=359, Unknown=0, NotChecked=0, Total=420 [2022-03-20 07:03:20,109 INFO L913 BasicCegarLoop]: 52 mSDtfsCounter, 2 mSDsluCounter, 545 mSDsCounter, 0 mSdLazyCounter, 343 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 597 SdHoareTripleChecker+Invalid, 343 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 343 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-03-20 07:03:20,110 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 597 Invalid, 343 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 343 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-03-20 07:03:20,110 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 61 states. [2022-03-20 07:03:20,112 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 61 to 61. [2022-03-20 07:03:20,112 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 61 states, 40 states have (on average 1.025) internal successors, (41), 40 states have internal predecessors, (41), 16 states have call successors, (16), 6 states have call predecessors, (16), 4 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) [2022-03-20 07:03:20,112 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 61 states to 61 states and 71 transitions. [2022-03-20 07:03:20,113 INFO L78 Accepts]: Start accepts. Automaton has 61 states and 71 transitions. Word has length 93 [2022-03-20 07:03:20,113 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 07:03:20,113 INFO L478 AbstractCegarLoop]: Abstraction has 61 states and 71 transitions. [2022-03-20 07:03:20,113 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 15 states have (on average 2.3333333333333335) internal successors, (35), 15 states have internal predecessors, (35), 13 states have call successors, (15), 2 states have call predecessors, (15), 1 states have return successors, (13), 12 states have call predecessors, (13), 12 states have call successors, (13) [2022-03-20 07:03:20,113 INFO L276 IsEmpty]: Start isEmpty. Operand 61 states and 71 transitions. [2022-03-20 07:03:20,121 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 101 [2022-03-20 07:03:20,121 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 07:03:20,121 INFO L499 BasicCegarLoop]: trace histogram [13, 12, 12, 12, 12, 12, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 07:03:20,126 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2022-03-20 07:03:20,326 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2022-03-20 07:03:20,326 INFO L403 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 07:03:20,327 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 07:03:20,327 INFO L85 PathProgramCache]: Analyzing trace with hash 1384988242, now seen corresponding path program 11 times [2022-03-20 07:03:20,327 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 07:03:20,327 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1494544778] [2022-03-20 07:03:20,327 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 07:03:20,327 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 07:03:20,333 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 07:03:20,333 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [541254976] [2022-03-20 07:03:20,333 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2022-03-20 07:03:20,333 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 07:03:20,333 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 07:03:20,334 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 07:03:20,350 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2022-03-20 07:03:20,920 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 12 check-sat command(s) [2022-03-20 07:03:20,920 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 07:03:20,922 INFO L263 TraceCheckSpWp]: Trace formula consists of 265 conjuncts, 53 conjunts are in the unsatisfiable core [2022-03-20 07:03:20,924 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 07:03:21,336 INFO L134 CoverageAnalysis]: Checked inductivity of 486 backedges. 24 proven. 198 refuted. 0 times theorem prover too weak. 264 trivial. 0 not checked. [2022-03-20 07:03:21,337 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 07:03:22,006 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 07:03:22,006 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1494544778] [2022-03-20 07:03:22,006 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 07:03:22,006 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [541254976] [2022-03-20 07:03:22,006 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [541254976] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 07:03:22,006 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 07:03:22,006 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17] total 17 [2022-03-20 07:03:22,007 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1590645499] [2022-03-20 07:03:22,007 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-03-20 07:03:22,007 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2022-03-20 07:03:22,007 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 07:03:22,007 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2022-03-20 07:03:22,008 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=185, Invalid=685, Unknown=0, NotChecked=0, Total=870 [2022-03-20 07:03:22,008 INFO L87 Difference]: Start difference. First operand 61 states and 71 transitions. Second operand has 17 states, 16 states have (on average 2.3125) internal successors, (37), 16 states have internal predecessors, (37), 14 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (14), 13 states have call predecessors, (14), 13 states have call successors, (14) [2022-03-20 07:03:22,258 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 07:03:22,258 INFO L93 Difference]: Finished difference Result 67 states and 78 transitions. [2022-03-20 07:03:22,258 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2022-03-20 07:03:22,258 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 16 states have (on average 2.3125) internal successors, (37), 16 states have internal predecessors, (37), 14 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (14), 13 states have call predecessors, (14), 13 states have call successors, (14) Word has length 100 [2022-03-20 07:03:22,259 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 07:03:22,260 INFO L225 Difference]: With dead ends: 67 [2022-03-20 07:03:22,260 INFO L226 Difference]: Without dead ends: 64 [2022-03-20 07:03:22,260 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 184 GetRequests, 153 SyntacticMatches, 1 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 23 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=195, Invalid=797, Unknown=0, NotChecked=0, Total=992 [2022-03-20 07:03:22,261 INFO L913 BasicCegarLoop]: 55 mSDtfsCounter, 2 mSDsluCounter, 614 mSDsCounter, 0 mSdLazyCounter, 397 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 669 SdHoareTripleChecker+Invalid, 397 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 397 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-03-20 07:03:22,261 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 669 Invalid, 397 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 397 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-03-20 07:03:22,261 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 64 states. [2022-03-20 07:03:22,267 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 64 to 64. [2022-03-20 07:03:22,267 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 64 states, 42 states have (on average 1.0238095238095237) internal successors, (43), 42 states have internal predecessors, (43), 17 states have call successors, (17), 6 states have call predecessors, (17), 4 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) [2022-03-20 07:03:22,268 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 64 states to 64 states and 75 transitions. [2022-03-20 07:03:22,268 INFO L78 Accepts]: Start accepts. Automaton has 64 states and 75 transitions. Word has length 100 [2022-03-20 07:03:22,268 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 07:03:22,268 INFO L478 AbstractCegarLoop]: Abstraction has 64 states and 75 transitions. [2022-03-20 07:03:22,268 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 16 states have (on average 2.3125) internal successors, (37), 16 states have internal predecessors, (37), 14 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (14), 13 states have call predecessors, (14), 13 states have call successors, (14) [2022-03-20 07:03:22,269 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 75 transitions. [2022-03-20 07:03:22,270 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 108 [2022-03-20 07:03:22,270 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 07:03:22,270 INFO L499 BasicCegarLoop]: trace histogram [14, 13, 13, 13, 13, 13, 12, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 07:03:22,278 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2022-03-20 07:03:22,474 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2022-03-20 07:03:22,474 INFO L403 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 07:03:22,475 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 07:03:22,475 INFO L85 PathProgramCache]: Analyzing trace with hash 2099554112, now seen corresponding path program 12 times [2022-03-20 07:03:22,475 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 07:03:22,475 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [491349012] [2022-03-20 07:03:22,475 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 07:03:22,475 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 07:03:22,481 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 07:03:22,481 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [662753872] [2022-03-20 07:03:22,481 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-03-20 07:03:22,481 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 07:03:22,481 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 07:03:22,487 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 07:03:22,488 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2022-03-20 07:03:22,693 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 13 check-sat command(s) [2022-03-20 07:03:22,693 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 07:03:22,695 INFO L263 TraceCheckSpWp]: Trace formula consists of 282 conjuncts, 57 conjunts are in the unsatisfiable core [2022-03-20 07:03:22,696 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 07:03:23,069 INFO L134 CoverageAnalysis]: Checked inductivity of 572 backedges. 26 proven. 234 refuted. 0 times theorem prover too weak. 312 trivial. 0 not checked. [2022-03-20 07:03:23,069 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 07:03:23,514 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 07:03:23,514 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [491349012] [2022-03-20 07:03:23,514 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 07:03:23,514 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [662753872] [2022-03-20 07:03:23,515 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [662753872] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 07:03:23,515 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 07:03:23,515 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18] total 18 [2022-03-20 07:03:23,516 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1983458125] [2022-03-20 07:03:23,516 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-03-20 07:03:23,516 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2022-03-20 07:03:23,516 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 07:03:23,516 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2022-03-20 07:03:23,517 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=142, Invalid=560, Unknown=0, NotChecked=0, Total=702 [2022-03-20 07:03:23,517 INFO L87 Difference]: Start difference. First operand 64 states and 75 transitions. Second operand has 18 states, 17 states have (on average 2.2941176470588234) internal successors, (39), 17 states have internal predecessors, (39), 15 states have call successors, (17), 2 states have call predecessors, (17), 1 states have return successors, (15), 14 states have call predecessors, (15), 14 states have call successors, (15) [2022-03-20 07:03:23,786 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 07:03:23,786 INFO L93 Difference]: Finished difference Result 70 states and 82 transitions. [2022-03-20 07:03:23,786 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2022-03-20 07:03:23,786 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 17 states have (on average 2.2941176470588234) internal successors, (39), 17 states have internal predecessors, (39), 15 states have call successors, (17), 2 states have call predecessors, (17), 1 states have return successors, (15), 14 states have call predecessors, (15), 14 states have call successors, (15) Word has length 107 [2022-03-20 07:03:23,787 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 07:03:23,787 INFO L225 Difference]: With dead ends: 70 [2022-03-20 07:03:23,787 INFO L226 Difference]: Without dead ends: 67 [2022-03-20 07:03:23,787 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 163 GetRequests, 135 SyntacticMatches, 1 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=152, Invalid=660, Unknown=0, NotChecked=0, Total=812 [2022-03-20 07:03:23,788 INFO L913 BasicCegarLoop]: 58 mSDtfsCounter, 2 mSDsluCounter, 687 mSDsCounter, 0 mSdLazyCounter, 455 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 745 SdHoareTripleChecker+Invalid, 455 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 455 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-03-20 07:03:23,788 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 745 Invalid, 455 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 455 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-03-20 07:03:23,788 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 67 states. [2022-03-20 07:03:23,790 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 67 to 67. [2022-03-20 07:03:23,790 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 67 states, 44 states have (on average 1.0227272727272727) internal successors, (45), 44 states have internal predecessors, (45), 18 states have call successors, (18), 6 states have call predecessors, (18), 4 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2022-03-20 07:03:23,790 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 67 states to 67 states and 79 transitions. [2022-03-20 07:03:23,790 INFO L78 Accepts]: Start accepts. Automaton has 67 states and 79 transitions. Word has length 107 [2022-03-20 07:03:23,791 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 07:03:23,791 INFO L478 AbstractCegarLoop]: Abstraction has 67 states and 79 transitions. [2022-03-20 07:03:23,791 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 17 states have (on average 2.2941176470588234) internal successors, (39), 17 states have internal predecessors, (39), 15 states have call successors, (17), 2 states have call predecessors, (17), 1 states have return successors, (15), 14 states have call predecessors, (15), 14 states have call successors, (15) [2022-03-20 07:03:23,791 INFO L276 IsEmpty]: Start isEmpty. Operand 67 states and 79 transitions. [2022-03-20 07:03:23,791 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 115 [2022-03-20 07:03:23,792 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 07:03:23,792 INFO L499 BasicCegarLoop]: trace histogram [15, 14, 14, 14, 14, 14, 13, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 07:03:23,803 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2022-03-20 07:03:24,003 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable14,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 07:03:24,003 INFO L403 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 07:03:24,003 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 07:03:24,004 INFO L85 PathProgramCache]: Analyzing trace with hash -1740638574, now seen corresponding path program 13 times [2022-03-20 07:03:24,004 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 07:03:24,004 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1618948156] [2022-03-20 07:03:24,004 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 07:03:24,004 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 07:03:24,018 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 07:03:24,019 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [876227439] [2022-03-20 07:03:24,019 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2022-03-20 07:03:24,019 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 07:03:24,019 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 07:03:24,020 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 07:03:24,021 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2022-03-20 07:03:24,859 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 07:03:24,861 INFO L263 TraceCheckSpWp]: Trace formula consists of 299 conjuncts, 71 conjunts are in the unsatisfiable core [2022-03-20 07:03:24,863 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 07:03:25,377 INFO L134 CoverageAnalysis]: Checked inductivity of 665 backedges. 98 proven. 275 refuted. 0 times theorem prover too weak. 292 trivial. 0 not checked. [2022-03-20 07:03:25,377 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 07:03:52,880 WARN L833 $PredicateComparison]: unable to prove that (or (forall ((main_~k~0 Int)) (or (< (+ c_main_~c~0 1) main_~k~0) (not (< c_main_~c~0 main_~k~0)) (let ((.cse0 (+ c_main_~y~0 1))) (= (* .cse0 .cse0) (* main_~k~0 .cse0))))) (not (= 0 (mod (+ (* 6 c_main_~y~0 c_main_~y~0 c_main_~y~0) (* 13 c_main_~y~0 c_main_~y~0) (* c_main_~y~0 c_main_~y~0 c_main_~y~0 c_main_~y~0)) 4)))) is different from false [2022-03-20 07:03:52,882 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 07:03:52,882 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1618948156] [2022-03-20 07:03:52,882 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 07:03:52,882 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [876227439] [2022-03-20 07:03:52,882 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [876227439] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 07:03:52,882 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 07:03:52,882 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [23] total 23 [2022-03-20 07:03:52,883 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [279169966] [2022-03-20 07:03:52,883 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-03-20 07:03:52,883 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2022-03-20 07:03:52,883 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 07:03:52,883 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2022-03-20 07:03:52,883 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=88, Invalid=665, Unknown=7, NotChecked=52, Total=812 [2022-03-20 07:03:52,884 INFO L87 Difference]: Start difference. First operand 67 states and 79 transitions. Second operand has 23 states, 22 states have (on average 2.0) internal successors, (44), 20 states have internal predecessors, (44), 16 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (16), 15 states have call predecessors, (16), 15 states have call successors, (16) [2022-03-20 07:03:53,269 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 07:03:53,270 INFO L93 Difference]: Finished difference Result 73 states and 86 transitions. [2022-03-20 07:03:53,270 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2022-03-20 07:03:53,270 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 22 states have (on average 2.0) internal successors, (44), 20 states have internal predecessors, (44), 16 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (16), 15 states have call predecessors, (16), 15 states have call successors, (16) Word has length 114 [2022-03-20 07:03:53,270 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 07:03:53,271 INFO L225 Difference]: With dead ends: 73 [2022-03-20 07:03:53,271 INFO L226 Difference]: Without dead ends: 70 [2022-03-20 07:03:53,271 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 129 GetRequests, 98 SyntacticMatches, 1 SemanticMatches, 30 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 41 ImplicationChecksByTransitivity, 23.6s TimeCoverageRelationStatistics Valid=109, Invalid=818, Unknown=7, NotChecked=58, Total=992 [2022-03-20 07:03:53,272 INFO L913 BasicCegarLoop]: 44 mSDtfsCounter, 8 mSDsluCounter, 741 mSDsCounter, 0 mSdLazyCounter, 704 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 785 SdHoareTripleChecker+Invalid, 706 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 704 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-03-20 07:03:53,272 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [10 Valid, 785 Invalid, 706 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 704 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-03-20 07:03:53,272 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 70 states. [2022-03-20 07:03:53,274 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 70 to 70. [2022-03-20 07:03:53,274 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 70 states, 46 states have (on average 1.0217391304347827) internal successors, (47), 46 states have internal predecessors, (47), 19 states have call successors, (19), 6 states have call predecessors, (19), 4 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) [2022-03-20 07:03:53,275 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 70 states to 70 states and 83 transitions. [2022-03-20 07:03:53,275 INFO L78 Accepts]: Start accepts. Automaton has 70 states and 83 transitions. Word has length 114 [2022-03-20 07:03:53,275 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 07:03:53,275 INFO L478 AbstractCegarLoop]: Abstraction has 70 states and 83 transitions. [2022-03-20 07:03:53,275 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 22 states have (on average 2.0) internal successors, (44), 20 states have internal predecessors, (44), 16 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (16), 15 states have call predecessors, (16), 15 states have call successors, (16) [2022-03-20 07:03:53,275 INFO L276 IsEmpty]: Start isEmpty. Operand 70 states and 83 transitions. [2022-03-20 07:03:53,276 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 122 [2022-03-20 07:03:53,276 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 07:03:53,276 INFO L499 BasicCegarLoop]: trace histogram [16, 15, 15, 15, 15, 15, 14, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 07:03:53,283 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Forceful destruction successful, exit code 0 [2022-03-20 07:03:53,477 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2022-03-20 07:03:53,477 INFO L403 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 07:03:53,477 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 07:03:53,477 INFO L85 PathProgramCache]: Analyzing trace with hash -1682036992, now seen corresponding path program 14 times [2022-03-20 07:03:53,477 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 07:03:53,477 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [887005597] [2022-03-20 07:03:53,477 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 07:03:53,477 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 07:03:53,488 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 07:03:53,488 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1879483023] [2022-03-20 07:03:53,488 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 07:03:53,488 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 07:03:53,488 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 07:03:53,496 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 07:03:53,497 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2022-03-20 07:03:54,005 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 07:03:54,005 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 07:03:54,007 INFO L263 TraceCheckSpWp]: Trace formula consists of 316 conjuncts, 64 conjunts are in the unsatisfiable core [2022-03-20 07:03:54,009 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 07:03:54,404 INFO L134 CoverageAnalysis]: Checked inductivity of 765 backedges. 30 proven. 315 refuted. 0 times theorem prover too weak. 420 trivial. 0 not checked. [2022-03-20 07:03:54,404 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 07:03:54,561 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 07:03:54,562 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [887005597] [2022-03-20 07:03:54,562 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 07:03:54,562 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1879483023] [2022-03-20 07:03:54,562 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1879483023] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 07:03:54,562 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 07:03:54,562 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [20] total 20 [2022-03-20 07:03:54,562 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1244776991] [2022-03-20 07:03:54,562 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-03-20 07:03:54,562 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2022-03-20 07:03:54,562 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 07:03:54,563 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2022-03-20 07:03:54,563 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=63, Invalid=443, Unknown=0, NotChecked=0, Total=506 [2022-03-20 07:03:54,563 INFO L87 Difference]: Start difference. First operand 70 states and 83 transitions. Second operand has 20 states, 19 states have (on average 2.263157894736842) internal successors, (43), 19 states have internal predecessors, (43), 17 states have call successors, (19), 2 states have call predecessors, (19), 1 states have return successors, (17), 16 states have call predecessors, (17), 16 states have call successors, (17) [2022-03-20 07:03:54,882 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 07:03:54,883 INFO L93 Difference]: Finished difference Result 76 states and 90 transitions. [2022-03-20 07:03:54,883 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2022-03-20 07:03:54,883 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 19 states have (on average 2.263157894736842) internal successors, (43), 19 states have internal predecessors, (43), 17 states have call successors, (19), 2 states have call predecessors, (19), 1 states have return successors, (17), 16 states have call predecessors, (17), 16 states have call successors, (17) Word has length 121 [2022-03-20 07:03:54,884 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 07:03:54,884 INFO L225 Difference]: With dead ends: 76 [2022-03-20 07:03:54,884 INFO L226 Difference]: Without dead ends: 73 [2022-03-20 07:03:54,884 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 135 GetRequests, 111 SyntacticMatches, 1 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=73, Invalid=527, Unknown=0, NotChecked=0, Total=600 [2022-03-20 07:03:54,885 INFO L913 BasicCegarLoop]: 64 mSDtfsCounter, 2 mSDsluCounter, 845 mSDsCounter, 0 mSdLazyCounter, 583 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 909 SdHoareTripleChecker+Invalid, 583 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 583 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-03-20 07:03:54,885 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 909 Invalid, 583 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 583 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-03-20 07:03:54,885 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 73 states. [2022-03-20 07:03:54,887 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 73 to 73. [2022-03-20 07:03:54,887 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 73 states, 48 states have (on average 1.0208333333333333) internal successors, (49), 48 states have internal predecessors, (49), 20 states have call successors, (20), 6 states have call predecessors, (20), 4 states have return successors, (18), 18 states have call predecessors, (18), 18 states have call successors, (18) [2022-03-20 07:03:54,887 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 73 states to 73 states and 87 transitions. [2022-03-20 07:03:54,888 INFO L78 Accepts]: Start accepts. Automaton has 73 states and 87 transitions. Word has length 121 [2022-03-20 07:03:54,888 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 07:03:54,888 INFO L478 AbstractCegarLoop]: Abstraction has 73 states and 87 transitions. [2022-03-20 07:03:54,888 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 19 states have (on average 2.263157894736842) internal successors, (43), 19 states have internal predecessors, (43), 17 states have call successors, (19), 2 states have call predecessors, (19), 1 states have return successors, (17), 16 states have call predecessors, (17), 16 states have call successors, (17) [2022-03-20 07:03:54,888 INFO L276 IsEmpty]: Start isEmpty. Operand 73 states and 87 transitions. [2022-03-20 07:03:54,889 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 129 [2022-03-20 07:03:54,889 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 07:03:54,889 INFO L499 BasicCegarLoop]: trace histogram [17, 16, 16, 16, 16, 16, 15, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 07:03:54,894 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Ended with exit code 0 [2022-03-20 07:03:55,094 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2022-03-20 07:03:55,094 INFO L403 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 07:03:55,094 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 07:03:55,095 INFO L85 PathProgramCache]: Analyzing trace with hash 699088594, now seen corresponding path program 15 times [2022-03-20 07:03:55,095 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 07:03:55,095 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1111391057] [2022-03-20 07:03:55,095 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 07:03:55,095 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 07:03:55,104 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 07:03:55,104 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [395729737] [2022-03-20 07:03:55,104 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-03-20 07:03:55,104 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 07:03:55,105 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 07:03:55,105 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 07:03:55,106 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2022-03-20 07:03:55,695 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 16 check-sat command(s) [2022-03-20 07:03:55,695 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 07:03:55,698 INFO L263 TraceCheckSpWp]: Trace formula consists of 333 conjuncts, 68 conjunts are in the unsatisfiable core [2022-03-20 07:03:55,699 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 07:03:56,120 INFO L134 CoverageAnalysis]: Checked inductivity of 872 backedges. 32 proven. 360 refuted. 0 times theorem prover too weak. 480 trivial. 0 not checked. [2022-03-20 07:03:56,120 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 07:03:56,266 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 07:03:56,266 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1111391057] [2022-03-20 07:03:56,267 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 07:03:56,267 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [395729737] [2022-03-20 07:03:56,267 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [395729737] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 07:03:56,267 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 07:03:56,267 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21] total 21 [2022-03-20 07:03:56,267 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [893056341] [2022-03-20 07:03:56,267 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-03-20 07:03:56,267 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2022-03-20 07:03:56,267 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 07:03:56,268 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2022-03-20 07:03:56,268 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=66, Invalid=486, Unknown=0, NotChecked=0, Total=552 [2022-03-20 07:03:56,268 INFO L87 Difference]: Start difference. First operand 73 states and 87 transitions. Second operand has 21 states, 20 states have (on average 2.25) internal successors, (45), 20 states have internal predecessors, (45), 18 states have call successors, (20), 2 states have call predecessors, (20), 1 states have return successors, (18), 17 states have call predecessors, (18), 17 states have call successors, (18) [2022-03-20 07:03:56,619 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 07:03:56,619 INFO L93 Difference]: Finished difference Result 79 states and 94 transitions. [2022-03-20 07:03:56,619 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2022-03-20 07:03:56,619 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 20 states have (on average 2.25) internal successors, (45), 20 states have internal predecessors, (45), 18 states have call successors, (20), 2 states have call predecessors, (20), 1 states have return successors, (18), 17 states have call predecessors, (18), 17 states have call successors, (18) Word has length 128 [2022-03-20 07:03:56,620 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 07:03:56,620 INFO L225 Difference]: With dead ends: 79 [2022-03-20 07:03:56,620 INFO L226 Difference]: Without dead ends: 76 [2022-03-20 07:03:56,620 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 142 GetRequests, 117 SyntacticMatches, 1 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=76, Invalid=574, Unknown=0, NotChecked=0, Total=650 [2022-03-20 07:03:56,621 INFO L913 BasicCegarLoop]: 67 mSDtfsCounter, 2 mSDsluCounter, 930 mSDsCounter, 0 mSdLazyCounter, 653 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 997 SdHoareTripleChecker+Invalid, 653 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 653 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-03-20 07:03:56,621 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 997 Invalid, 653 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 653 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-03-20 07:03:56,621 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 76 states. [2022-03-20 07:03:56,623 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 76 to 76. [2022-03-20 07:03:56,623 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 76 states, 50 states have (on average 1.02) internal successors, (51), 50 states have internal predecessors, (51), 21 states have call successors, (21), 6 states have call predecessors, (21), 4 states have return successors, (19), 19 states have call predecessors, (19), 19 states have call successors, (19) [2022-03-20 07:03:56,624 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 76 states to 76 states and 91 transitions. [2022-03-20 07:03:56,624 INFO L78 Accepts]: Start accepts. Automaton has 76 states and 91 transitions. Word has length 128 [2022-03-20 07:03:56,624 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 07:03:56,624 INFO L478 AbstractCegarLoop]: Abstraction has 76 states and 91 transitions. [2022-03-20 07:03:56,624 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 20 states have (on average 2.25) internal successors, (45), 20 states have internal predecessors, (45), 18 states have call successors, (20), 2 states have call predecessors, (20), 1 states have return successors, (18), 17 states have call predecessors, (18), 17 states have call successors, (18) [2022-03-20 07:03:56,624 INFO L276 IsEmpty]: Start isEmpty. Operand 76 states and 91 transitions. [2022-03-20 07:03:56,625 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 136 [2022-03-20 07:03:56,625 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 07:03:56,625 INFO L499 BasicCegarLoop]: trace histogram [18, 17, 17, 17, 17, 17, 16, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 07:03:56,632 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Ended with exit code 0 [2022-03-20 07:03:56,832 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 18 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2022-03-20 07:03:56,833 INFO L403 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 07:03:56,833 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 07:03:56,833 INFO L85 PathProgramCache]: Analyzing trace with hash -119728448, now seen corresponding path program 16 times [2022-03-20 07:03:56,833 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 07:03:56,833 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1210091622] [2022-03-20 07:03:56,833 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 07:03:56,833 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 07:03:56,839 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 07:03:56,839 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1539496148] [2022-03-20 07:03:56,839 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-03-20 07:03:56,839 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 07:03:56,839 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 07:03:56,840 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 07:03:56,841 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Waiting until timeout for monitored process [2022-03-20 07:03:57,181 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-03-20 07:03:57,181 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 07:03:57,183 INFO L263 TraceCheckSpWp]: Trace formula consists of 319 conjuncts, 83 conjunts are in the unsatisfiable core [2022-03-20 07:03:57,185 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 07:03:57,733 INFO L134 CoverageAnalysis]: Checked inductivity of 986 backedges. 122 proven. 410 refuted. 0 times theorem prover too weak. 454 trivial. 0 not checked. [2022-03-20 07:03:57,733 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 07:04:33,030 WARN L833 $PredicateComparison]: unable to prove that (or (forall ((main_~k~0 Int)) (or (< (+ c_main_~c~0 1) main_~k~0) (not (< c_main_~c~0 main_~k~0)) (let ((.cse0 (+ c_main_~y~0 1))) (= (* .cse0 .cse0) (* main_~k~0 .cse0))))) (not (= (mod (+ (* (- 6) c_main_~y~0 c_main_~y~0 c_main_~y~0) (* (- 13) c_main_~y~0 c_main_~y~0) (* (- 1) c_main_~y~0 c_main_~y~0 c_main_~y~0 c_main_~y~0)) 4) 0))) is different from false [2022-03-20 07:04:33,032 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 07:04:33,032 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1210091622] [2022-03-20 07:04:33,032 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 07:04:33,032 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1539496148] [2022-03-20 07:04:33,032 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1539496148] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 07:04:33,032 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 07:04:33,032 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [26] total 26 [2022-03-20 07:04:33,033 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1825604778] [2022-03-20 07:04:33,033 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-03-20 07:04:33,033 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2022-03-20 07:04:33,033 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 07:04:33,033 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2022-03-20 07:04:33,034 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=97, Invalid=829, Unknown=8, NotChecked=58, Total=992 [2022-03-20 07:04:33,034 INFO L87 Difference]: Start difference. First operand 76 states and 91 transitions. Second operand has 26 states, 25 states have (on average 2.0) internal successors, (50), 23 states have internal predecessors, (50), 19 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (19), 18 states have call predecessors, (19), 18 states have call successors, (19) [2022-03-20 07:04:33,565 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 07:04:33,565 INFO L93 Difference]: Finished difference Result 82 states and 98 transitions. [2022-03-20 07:04:33,565 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2022-03-20 07:04:33,566 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 25 states have (on average 2.0) internal successors, (50), 23 states have internal predecessors, (50), 19 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (19), 18 states have call predecessors, (19), 18 states have call successors, (19) Word has length 135 [2022-03-20 07:04:33,566 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 07:04:33,566 INFO L225 Difference]: With dead ends: 82 [2022-03-20 07:04:33,566 INFO L226 Difference]: Without dead ends: 79 [2022-03-20 07:04:33,567 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 150 GetRequests, 116 SyntacticMatches, 1 SemanticMatches, 33 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 40 ImplicationChecksByTransitivity, 31.5s TimeCoverageRelationStatistics Valid=118, Invalid=1000, Unknown=8, NotChecked=64, Total=1190 [2022-03-20 07:04:33,567 INFO L913 BasicCegarLoop]: 50 mSDtfsCounter, 8 mSDsluCounter, 1004 mSDsCounter, 0 mSdLazyCounter, 933 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 1054 SdHoareTripleChecker+Invalid, 935 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 933 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2022-03-20 07:04:33,567 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [10 Valid, 1054 Invalid, 935 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 933 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2022-03-20 07:04:33,568 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 79 states. [2022-03-20 07:04:33,569 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 79 to 79. [2022-03-20 07:04:33,569 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 79 states, 52 states have (on average 1.0192307692307692) internal successors, (53), 52 states have internal predecessors, (53), 22 states have call successors, (22), 6 states have call predecessors, (22), 4 states have return successors, (20), 20 states have call predecessors, (20), 20 states have call successors, (20) [2022-03-20 07:04:33,570 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 79 states to 79 states and 95 transitions. [2022-03-20 07:04:33,570 INFO L78 Accepts]: Start accepts. Automaton has 79 states and 95 transitions. Word has length 135 [2022-03-20 07:04:33,570 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 07:04:33,570 INFO L478 AbstractCegarLoop]: Abstraction has 79 states and 95 transitions. [2022-03-20 07:04:33,570 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 25 states have (on average 2.0) internal successors, (50), 23 states have internal predecessors, (50), 19 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (19), 18 states have call predecessors, (19), 18 states have call successors, (19) [2022-03-20 07:04:33,570 INFO L276 IsEmpty]: Start isEmpty. Operand 79 states and 95 transitions. [2022-03-20 07:04:33,571 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 143 [2022-03-20 07:04:33,571 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 07:04:33,571 INFO L499 BasicCegarLoop]: trace histogram [19, 18, 18, 18, 18, 18, 17, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 07:04:33,578 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Forceful destruction successful, exit code 0 [2022-03-20 07:04:33,776 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,19 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 07:04:33,777 INFO L403 AbstractCegarLoop]: === Iteration 20 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 07:04:33,777 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 07:04:33,777 INFO L85 PathProgramCache]: Analyzing trace with hash -1869408494, now seen corresponding path program 17 times [2022-03-20 07:04:33,777 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 07:04:33,777 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1463555565] [2022-03-20 07:04:33,777 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 07:04:33,777 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 07:04:33,783 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 07:04:33,784 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1024902728] [2022-03-20 07:04:33,784 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2022-03-20 07:04:33,784 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 07:04:33,784 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 07:04:33,785 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 07:04:33,799 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Waiting until timeout for monitored process [2022-03-20 07:04:34,922 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 18 check-sat command(s) [2022-03-20 07:04:34,922 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 07:04:34,925 INFO L263 TraceCheckSpWp]: Trace formula consists of 367 conjuncts, 76 conjunts are in the unsatisfiable core [2022-03-20 07:04:34,927 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 07:04:35,410 INFO L134 CoverageAnalysis]: Checked inductivity of 1107 backedges. 36 proven. 459 refuted. 0 times theorem prover too weak. 612 trivial. 0 not checked. [2022-03-20 07:04:35,410 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 07:04:35,564 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 07:04:35,564 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1463555565] [2022-03-20 07:04:35,564 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 07:04:35,564 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1024902728] [2022-03-20 07:04:35,564 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1024902728] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 07:04:35,565 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 07:04:35,565 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [23] total 23 [2022-03-20 07:04:35,565 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1609485623] [2022-03-20 07:04:35,565 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-03-20 07:04:35,565 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2022-03-20 07:04:35,565 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 07:04:35,565 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2022-03-20 07:04:35,566 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=72, Invalid=578, Unknown=0, NotChecked=0, Total=650 [2022-03-20 07:04:35,566 INFO L87 Difference]: Start difference. First operand 79 states and 95 transitions. Second operand has 23 states, 22 states have (on average 2.227272727272727) internal successors, (49), 22 states have internal predecessors, (49), 20 states have call successors, (22), 2 states have call predecessors, (22), 1 states have return successors, (20), 19 states have call predecessors, (20), 19 states have call successors, (20) [2022-03-20 07:04:36,019 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 07:04:36,019 INFO L93 Difference]: Finished difference Result 85 states and 102 transitions. [2022-03-20 07:04:36,019 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2022-03-20 07:04:36,019 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 22 states have (on average 2.227272727272727) internal successors, (49), 22 states have internal predecessors, (49), 20 states have call successors, (22), 2 states have call predecessors, (22), 1 states have return successors, (20), 19 states have call predecessors, (20), 19 states have call successors, (20) Word has length 142 [2022-03-20 07:04:36,020 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 07:04:36,020 INFO L225 Difference]: With dead ends: 85 [2022-03-20 07:04:36,020 INFO L226 Difference]: Without dead ends: 82 [2022-03-20 07:04:36,020 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 156 GetRequests, 129 SyntacticMatches, 1 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=82, Invalid=674, Unknown=0, NotChecked=0, Total=756 [2022-03-20 07:04:36,021 INFO L913 BasicCegarLoop]: 73 mSDtfsCounter, 2 mSDsluCounter, 1112 mSDsCounter, 0 mSdLazyCounter, 805 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 1185 SdHoareTripleChecker+Invalid, 805 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 805 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2022-03-20 07:04:36,021 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 1185 Invalid, 805 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 805 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2022-03-20 07:04:36,021 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 82 states. [2022-03-20 07:04:36,023 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 82 to 82. [2022-03-20 07:04:36,023 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 82 states, 54 states have (on average 1.0185185185185186) internal successors, (55), 54 states have internal predecessors, (55), 23 states have call successors, (23), 6 states have call predecessors, (23), 4 states have return successors, (21), 21 states have call predecessors, (21), 21 states have call successors, (21) [2022-03-20 07:04:36,023 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 82 states to 82 states and 99 transitions. [2022-03-20 07:04:36,024 INFO L78 Accepts]: Start accepts. Automaton has 82 states and 99 transitions. Word has length 142 [2022-03-20 07:04:36,024 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 07:04:36,024 INFO L478 AbstractCegarLoop]: Abstraction has 82 states and 99 transitions. [2022-03-20 07:04:36,024 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 22 states have (on average 2.227272727272727) internal successors, (49), 22 states have internal predecessors, (49), 20 states have call successors, (22), 2 states have call predecessors, (22), 1 states have return successors, (20), 19 states have call predecessors, (20), 19 states have call successors, (20) [2022-03-20 07:04:36,024 INFO L276 IsEmpty]: Start isEmpty. Operand 82 states and 99 transitions. [2022-03-20 07:04:36,025 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 150 [2022-03-20 07:04:36,025 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 07:04:36,025 INFO L499 BasicCegarLoop]: trace histogram [20, 19, 19, 19, 19, 19, 18, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 07:04:36,035 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Forceful destruction successful, exit code 0 [2022-03-20 07:04:36,231 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19,20 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 07:04:36,231 INFO L403 AbstractCegarLoop]: === Iteration 21 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 07:04:36,232 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 07:04:36,232 INFO L85 PathProgramCache]: Analyzing trace with hash 1178433152, now seen corresponding path program 18 times [2022-03-20 07:04:36,232 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 07:04:36,232 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1964279931] [2022-03-20 07:04:36,232 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 07:04:36,232 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 07:04:36,237 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 07:04:36,238 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [298300554] [2022-03-20 07:04:36,238 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-03-20 07:04:36,238 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 07:04:36,238 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 07:04:36,239 INFO L229 MonitoredProcess]: Starting monitored process 21 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 07:04:36,240 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Waiting until timeout for monitored process [2022-03-20 07:04:47,090 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 19 check-sat command(s) [2022-03-20 07:04:47,090 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 07:04:47,094 INFO L263 TraceCheckSpWp]: Trace formula consists of 384 conjuncts, 80 conjunts are in the unsatisfiable core [2022-03-20 07:04:47,096 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 07:04:47,629 INFO L134 CoverageAnalysis]: Checked inductivity of 1235 backedges. 38 proven. 513 refuted. 0 times theorem prover too weak. 684 trivial. 0 not checked. [2022-03-20 07:04:47,629 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 07:04:47,804 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 07:04:47,804 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1964279931] [2022-03-20 07:04:47,804 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 07:04:47,804 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [298300554] [2022-03-20 07:04:47,804 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [298300554] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 07:04:47,804 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 07:04:47,805 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [24] total 24 [2022-03-20 07:04:47,805 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [775536282] [2022-03-20 07:04:47,805 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-03-20 07:04:47,805 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2022-03-20 07:04:47,805 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 07:04:47,805 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2022-03-20 07:04:47,806 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=75, Invalid=627, Unknown=0, NotChecked=0, Total=702 [2022-03-20 07:04:47,806 INFO L87 Difference]: Start difference. First operand 82 states and 99 transitions. Second operand has 24 states, 23 states have (on average 2.217391304347826) internal successors, (51), 23 states have internal predecessors, (51), 21 states have call successors, (23), 2 states have call predecessors, (23), 1 states have return successors, (21), 20 states have call predecessors, (21), 20 states have call successors, (21) [2022-03-20 07:04:48,296 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 07:04:48,297 INFO L93 Difference]: Finished difference Result 88 states and 106 transitions. [2022-03-20 07:04:48,297 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2022-03-20 07:04:48,297 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 23 states have (on average 2.217391304347826) internal successors, (51), 23 states have internal predecessors, (51), 21 states have call successors, (23), 2 states have call predecessors, (23), 1 states have return successors, (21), 20 states have call predecessors, (21), 20 states have call successors, (21) Word has length 149 [2022-03-20 07:04:48,297 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 07:04:48,298 INFO L225 Difference]: With dead ends: 88 [2022-03-20 07:04:48,298 INFO L226 Difference]: Without dead ends: 85 [2022-03-20 07:04:48,298 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 163 GetRequests, 135 SyntacticMatches, 1 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=85, Invalid=727, Unknown=0, NotChecked=0, Total=812 [2022-03-20 07:04:48,299 INFO L913 BasicCegarLoop]: 76 mSDtfsCounter, 2 mSDsluCounter, 1209 mSDsCounter, 0 mSdLazyCounter, 887 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 1285 SdHoareTripleChecker+Invalid, 887 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 887 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2022-03-20 07:04:48,299 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 1285 Invalid, 887 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 887 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2022-03-20 07:04:48,299 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 85 states. [2022-03-20 07:04:48,300 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 85 to 85. [2022-03-20 07:04:48,301 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 85 states, 56 states have (on average 1.0178571428571428) internal successors, (57), 56 states have internal predecessors, (57), 24 states have call successors, (24), 6 states have call predecessors, (24), 4 states have return successors, (22), 22 states have call predecessors, (22), 22 states have call successors, (22) [2022-03-20 07:04:48,301 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 85 states to 85 states and 103 transitions. [2022-03-20 07:04:48,301 INFO L78 Accepts]: Start accepts. Automaton has 85 states and 103 transitions. Word has length 149 [2022-03-20 07:04:48,301 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 07:04:48,301 INFO L478 AbstractCegarLoop]: Abstraction has 85 states and 103 transitions. [2022-03-20 07:04:48,302 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 23 states have (on average 2.217391304347826) internal successors, (51), 23 states have internal predecessors, (51), 21 states have call successors, (23), 2 states have call predecessors, (23), 1 states have return successors, (21), 20 states have call predecessors, (21), 20 states have call successors, (21) [2022-03-20 07:04:48,302 INFO L276 IsEmpty]: Start isEmpty. Operand 85 states and 103 transitions. [2022-03-20 07:04:48,302 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 157 [2022-03-20 07:04:48,302 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 07:04:48,302 INFO L499 BasicCegarLoop]: trace histogram [21, 20, 20, 20, 20, 20, 19, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 07:04:48,309 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Forceful destruction successful, exit code 0 [2022-03-20 07:04:48,509 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 21 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable20 [2022-03-20 07:04:48,509 INFO L403 AbstractCegarLoop]: === Iteration 22 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 07:04:48,509 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 07:04:48,510 INFO L85 PathProgramCache]: Analyzing trace with hash -272924846, now seen corresponding path program 19 times [2022-03-20 07:04:48,510 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 07:04:48,510 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1037797817] [2022-03-20 07:04:48,510 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 07:04:48,510 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 07:04:48,516 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 07:04:48,516 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [952451067] [2022-03-20 07:04:48,516 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2022-03-20 07:04:48,516 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 07:04:48,516 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 07:04:48,517 INFO L229 MonitoredProcess]: Starting monitored process 22 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 07:04:48,518 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (22)] Waiting until timeout for monitored process [2022-03-20 07:04:49,200 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 07:04:49,203 INFO L263 TraceCheckSpWp]: Trace formula consists of 401 conjuncts, 84 conjunts are in the unsatisfiable core [2022-03-20 07:04:49,205 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 07:04:49,757 INFO L134 CoverageAnalysis]: Checked inductivity of 1370 backedges. 40 proven. 570 refuted. 0 times theorem prover too weak. 760 trivial. 0 not checked. [2022-03-20 07:04:49,757 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 07:04:49,917 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 07:04:49,917 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1037797817] [2022-03-20 07:04:49,917 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 07:04:49,918 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [952451067] [2022-03-20 07:04:49,918 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [952451067] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 07:04:49,918 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 07:04:49,918 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [25] total 25 [2022-03-20 07:04:49,918 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [212201203] [2022-03-20 07:04:49,918 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-03-20 07:04:49,918 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2022-03-20 07:04:49,918 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 07:04:49,918 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2022-03-20 07:04:49,919 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=78, Invalid=678, Unknown=0, NotChecked=0, Total=756 [2022-03-20 07:04:49,919 INFO L87 Difference]: Start difference. First operand 85 states and 103 transitions. Second operand has 25 states, 24 states have (on average 2.2083333333333335) internal successors, (53), 24 states have internal predecessors, (53), 22 states have call successors, (24), 2 states have call predecessors, (24), 1 states have return successors, (22), 21 states have call predecessors, (22), 21 states have call successors, (22) [2022-03-20 07:04:50,433 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 07:04:50,433 INFO L93 Difference]: Finished difference Result 91 states and 110 transitions. [2022-03-20 07:04:50,433 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2022-03-20 07:04:50,433 INFO L78 Accepts]: Start accepts. Automaton has has 25 states, 24 states have (on average 2.2083333333333335) internal successors, (53), 24 states have internal predecessors, (53), 22 states have call successors, (24), 2 states have call predecessors, (24), 1 states have return successors, (22), 21 states have call predecessors, (22), 21 states have call successors, (22) Word has length 156 [2022-03-20 07:04:50,434 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 07:04:50,434 INFO L225 Difference]: With dead ends: 91 [2022-03-20 07:04:50,434 INFO L226 Difference]: Without dead ends: 88 [2022-03-20 07:04:50,435 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 170 GetRequests, 141 SyntacticMatches, 1 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=88, Invalid=782, Unknown=0, NotChecked=0, Total=870 [2022-03-20 07:04:50,435 INFO L913 BasicCegarLoop]: 79 mSDtfsCounter, 2 mSDsluCounter, 1310 mSDsCounter, 0 mSdLazyCounter, 973 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 1389 SdHoareTripleChecker+Invalid, 973 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 973 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2022-03-20 07:04:50,435 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 1389 Invalid, 973 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 973 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2022-03-20 07:04:50,435 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 88 states. [2022-03-20 07:04:50,437 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 88 to 88. [2022-03-20 07:04:50,437 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 88 states, 58 states have (on average 1.0172413793103448) internal successors, (59), 58 states have internal predecessors, (59), 25 states have call successors, (25), 6 states have call predecessors, (25), 4 states have return successors, (23), 23 states have call predecessors, (23), 23 states have call successors, (23) [2022-03-20 07:04:50,437 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 88 states to 88 states and 107 transitions. [2022-03-20 07:04:50,437 INFO L78 Accepts]: Start accepts. Automaton has 88 states and 107 transitions. Word has length 156 [2022-03-20 07:04:50,438 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 07:04:50,438 INFO L478 AbstractCegarLoop]: Abstraction has 88 states and 107 transitions. [2022-03-20 07:04:50,438 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 25 states, 24 states have (on average 2.2083333333333335) internal successors, (53), 24 states have internal predecessors, (53), 22 states have call successors, (24), 2 states have call predecessors, (24), 1 states have return successors, (22), 21 states have call predecessors, (22), 21 states have call successors, (22) [2022-03-20 07:04:50,438 INFO L276 IsEmpty]: Start isEmpty. Operand 88 states and 107 transitions. [2022-03-20 07:04:50,438 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 164 [2022-03-20 07:04:50,438 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 07:04:50,439 INFO L499 BasicCegarLoop]: trace histogram [22, 21, 21, 21, 21, 21, 20, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 07:04:50,450 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (22)] Forceful destruction successful, exit code 0 [2022-03-20 07:04:50,644 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 22 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable21 [2022-03-20 07:04:50,644 INFO L403 AbstractCegarLoop]: === Iteration 23 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 07:04:50,644 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 07:04:50,644 INFO L85 PathProgramCache]: Analyzing trace with hash 2090550848, now seen corresponding path program 20 times [2022-03-20 07:04:50,644 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 07:04:50,644 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1573957431] [2022-03-20 07:04:50,645 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 07:04:50,645 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 07:04:50,650 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 07:04:50,650 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [682653659] [2022-03-20 07:04:50,650 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 07:04:50,650 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 07:04:50,651 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 07:04:50,653 INFO L229 MonitoredProcess]: Starting monitored process 23 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 07:04:50,654 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (23)] Waiting until timeout for monitored process [2022-03-20 07:04:51,467 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 07:04:51,467 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 07:04:51,471 INFO L263 TraceCheckSpWp]: Trace formula consists of 418 conjuncts, 71 conjunts are in the unsatisfiable core [2022-03-20 07:04:51,473 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 07:04:52,362 INFO L134 CoverageAnalysis]: Checked inductivity of 1512 backedges. 42 proven. 630 refuted. 0 times theorem prover too weak. 840 trivial. 0 not checked. [2022-03-20 07:04:52,362 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 07:04:54,396 INFO L134 CoverageAnalysis]: Checked inductivity of 1512 backedges. 42 proven. 630 refuted. 0 times theorem prover too weak. 840 trivial. 0 not checked. [2022-03-20 07:04:54,396 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 07:04:54,396 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1573957431] [2022-03-20 07:04:54,396 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 07:04:54,396 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [682653659] [2022-03-20 07:04:54,396 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [682653659] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 07:04:54,396 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 07:04:54,396 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [28, 28] total 51 [2022-03-20 07:04:54,397 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1302021908] [2022-03-20 07:04:54,397 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-20 07:04:54,397 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 51 states [2022-03-20 07:04:54,397 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 07:04:54,397 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 51 interpolants. [2022-03-20 07:04:54,398 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=356, Invalid=2194, Unknown=0, NotChecked=0, Total=2550 [2022-03-20 07:04:54,398 INFO L87 Difference]: Start difference. First operand 88 states and 107 transitions. Second operand has 51 states, 51 states have (on average 1.9607843137254901) internal successors, (100), 48 states have internal predecessors, (100), 43 states have call successors, (47), 2 states have call predecessors, (47), 2 states have return successors, (45), 45 states have call predecessors, (45), 43 states have call successors, (45) [2022-03-20 07:04:55,319 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 07:04:55,319 INFO L93 Difference]: Finished difference Result 86 states and 104 transitions. [2022-03-20 07:04:55,319 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2022-03-20 07:04:55,320 INFO L78 Accepts]: Start accepts. Automaton has has 51 states, 51 states have (on average 1.9607843137254901) internal successors, (100), 48 states have internal predecessors, (100), 43 states have call successors, (47), 2 states have call predecessors, (47), 2 states have return successors, (45), 45 states have call predecessors, (45), 43 states have call successors, (45) Word has length 163 [2022-03-20 07:04:55,320 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 07:04:55,320 INFO L225 Difference]: With dead ends: 86 [2022-03-20 07:04:55,320 INFO L226 Difference]: Without dead ends: 0 [2022-03-20 07:04:55,321 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 328 GetRequests, 275 SyntacticMatches, 1 SemanticMatches, 52 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 654 ImplicationChecksByTransitivity, 2.0s TimeCoverageRelationStatistics Valid=391, Invalid=2471, Unknown=0, NotChecked=0, Total=2862 [2022-03-20 07:04:55,321 INFO L913 BasicCegarLoop]: 77 mSDtfsCounter, 46 mSDsluCounter, 1525 mSDsCounter, 0 mSdLazyCounter, 1169 mSolverCounterSat, 63 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 46 SdHoareTripleChecker+Valid, 1602 SdHoareTripleChecker+Invalid, 1232 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 63 IncrementalHoareTripleChecker+Valid, 1169 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2022-03-20 07:04:55,321 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [46 Valid, 1602 Invalid, 1232 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [63 Valid, 1169 Invalid, 0 Unknown, 0 Unchecked, 0.8s Time] [2022-03-20 07:04:55,321 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2022-03-20 07:04:55,322 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2022-03-20 07:04:55,322 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-20 07:04:55,322 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2022-03-20 07:04:55,322 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 163 [2022-03-20 07:04:55,322 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 07:04:55,322 INFO L478 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2022-03-20 07:04:55,322 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 51 states, 51 states have (on average 1.9607843137254901) internal successors, (100), 48 states have internal predecessors, (100), 43 states have call successors, (47), 2 states have call predecessors, (47), 2 states have return successors, (45), 45 states have call predecessors, (45), 43 states have call successors, (45) [2022-03-20 07:04:55,322 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2022-03-20 07:04:55,322 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-03-20 07:04:55,324 INFO L788 garLoopResultBuilder]: Registering result SAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2022-03-20 07:04:55,331 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (23)] Forceful destruction successful, exit code 0 [2022-03-20 07:04:55,530 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable22,23 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 07:04:55,533 INFO L719 BasicCegarLoop]: Path program histogram: [20, 1, 1, 1] [2022-03-20 07:04:55,533 INFO L180 ceAbstractionStarter]: Computing trace abstraction results [2022-03-20 07:04:55,536 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 20.03 07:04:55 BasicIcfg [2022-03-20 07:04:55,536 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2022-03-20 07:04:55,536 INFO L158 Benchmark]: Toolchain (without parser) took 106713.08ms. Allocated memory was 186.6MB in the beginning and 259.0MB in the end (delta: 72.4MB). Free memory was 138.9MB in the beginning and 163.4MB in the end (delta: -24.4MB). Peak memory consumption was 49.1MB. Max. memory is 8.0GB. [2022-03-20 07:04:55,536 INFO L158 Benchmark]: CDTParser took 0.09ms. Allocated memory is still 186.6MB. Free memory was 155.0MB in the beginning and 154.8MB in the end (delta: 151.9kB). There was no memory consumed. Max. memory is 8.0GB. [2022-03-20 07:04:55,536 INFO L158 Benchmark]: CACSL2BoogieTranslator took 238.84ms. Allocated memory is still 186.6MB. Free memory was 138.8MB in the beginning and 163.5MB in the end (delta: -24.7MB). Peak memory consumption was 12.6MB. Max. memory is 8.0GB. [2022-03-20 07:04:55,537 INFO L158 Benchmark]: Boogie Preprocessor took 29.22ms. Allocated memory is still 186.6MB. Free memory was 163.5MB in the beginning and 162.2MB in the end (delta: 1.2MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. [2022-03-20 07:04:55,537 INFO L158 Benchmark]: RCFGBuilder took 240.34ms. Allocated memory is still 186.6MB. Free memory was 162.2MB in the beginning and 152.0MB in the end (delta: 10.2MB). Peak memory consumption was 10.5MB. Max. memory is 8.0GB. [2022-03-20 07:04:55,537 INFO L158 Benchmark]: IcfgTransformer took 43.98ms. Allocated memory is still 186.6MB. Free memory was 152.0MB in the beginning and 150.9MB in the end (delta: 1.1MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. [2022-03-20 07:04:55,537 INFO L158 Benchmark]: TraceAbstraction took 106146.68ms. Allocated memory was 186.6MB in the beginning and 259.0MB in the end (delta: 72.4MB). Free memory was 150.3MB in the beginning and 163.4MB in the end (delta: -13.1MB). Peak memory consumption was 60.0MB. Max. memory is 8.0GB. [2022-03-20 07:04:55,538 INFO L339 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.09ms. Allocated memory is still 186.6MB. Free memory was 155.0MB in the beginning and 154.8MB in the end (delta: 151.9kB). There was no memory consumed. Max. memory is 8.0GB. * CACSL2BoogieTranslator took 238.84ms. Allocated memory is still 186.6MB. Free memory was 138.8MB in the beginning and 163.5MB in the end (delta: -24.7MB). Peak memory consumption was 12.6MB. Max. memory is 8.0GB. * Boogie Preprocessor took 29.22ms. Allocated memory is still 186.6MB. Free memory was 163.5MB in the beginning and 162.2MB in the end (delta: 1.2MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. * RCFGBuilder took 240.34ms. Allocated memory is still 186.6MB. Free memory was 162.2MB in the beginning and 152.0MB in the end (delta: 10.2MB). Peak memory consumption was 10.5MB. Max. memory is 8.0GB. * IcfgTransformer took 43.98ms. Allocated memory is still 186.6MB. Free memory was 152.0MB in the beginning and 150.9MB in the end (delta: 1.1MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. * TraceAbstraction took 106146.68ms. Allocated memory was 186.6MB in the beginning and 259.0MB in the end (delta: 72.4MB). Free memory was 150.3MB in the beginning and 163.4MB in the end (delta: -13.1MB). Peak memory consumption was 60.0MB. Max. memory is 8.0GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - PositiveResult [Line: 12]: call to reach_error is unreachable For all program executions holds that call to reach_error is unreachable at this location - StatisticsResult: Ultimate Automizer benchmark data CFG has 5 procedures, 28 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 106.1s, OverallIterations: 23, TraceHistogramMax: 22, PathProgramHistogramMax: 20, EmptinessCheckTime: 0.0s, AutomataDifference: 5.9s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, PartialOrderReductionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 134 SdHoareTripleChecker+Valid, 5.0s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 123 mSDsluCounter, 14198 SdHoareTripleChecker+Invalid, 4.2s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 13101 mSDsCounter, 75 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 9263 IncrementalHoareTripleChecker+Invalid, 9338 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 75 mSolverCounterUnsat, 1097 mSDtfsCounter, 9263 mSolverCounterSat, 0.1s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 2561 GetRequests, 2081 SyntacticMatches, 22 SemanticMatches, 458 ConstructedPredicates, 2 IntricatePredicates, 0 DeprecatedPredicates, 822 ImplicationChecksByTransitivity, 61.2s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=88occurred in iteration=22, InterpolantAutomatonStates: 351, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.1s AutomataMinimizationTime, 23 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 18.6s SatisfiabilityAnalysisTime, 76.1s InterpolantComputationTime, 1988 NumberOfCodeBlocks, 1979 NumberOfCodeBlocksAsserted, 123 NumberOfCheckSat, 2150 ConstructedInterpolants, 0 QuantifiedInterpolants, 9922 SizeOfPredicates, 49 NumberOfNonLiveVariables, 5190 ConjunctsInSsa, 1026 ConjunctsInUnsatCore, 25 InterpolantComputations, 3 PerfectInterpolantSequences, 7504/12760 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available - AllSpecificationsHoldResult: All specifications hold 1 specifications checked. All of them hold RESULT: Ultimate proved your program to be correct! [2022-03-20 07:04:55,569 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Forceful destruction successful, exit code 0 Received shutdown request...