/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/hard-ll_valuebound20.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-34549b5 [2022-04-06 07:09:15,313 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-04-06 07:09:15,321 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-04-06 07:09:15,358 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-04-06 07:09:15,358 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-04-06 07:09:15,359 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-04-06 07:09:15,361 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-04-06 07:09:15,363 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-04-06 07:09:15,364 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-04-06 07:09:15,367 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-04-06 07:09:15,368 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-04-06 07:09:15,369 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-04-06 07:09:15,369 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-04-06 07:09:15,371 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-04-06 07:09:15,371 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-04-06 07:09:15,374 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-04-06 07:09:15,374 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-04-06 07:09:15,376 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-04-06 07:09:15,377 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-04-06 07:09:15,379 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-04-06 07:09:15,380 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-04-06 07:09:15,381 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-04-06 07:09:15,382 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-04-06 07:09:15,382 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-04-06 07:09:15,383 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-04-06 07:09:15,385 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-04-06 07:09:15,385 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-04-06 07:09:15,385 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-04-06 07:09:15,386 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-04-06 07:09:15,386 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-04-06 07:09:15,386 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-04-06 07:09:15,387 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-04-06 07:09:15,387 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-04-06 07:09:15,387 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-04-06 07:09:15,388 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-04-06 07:09:15,388 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-04-06 07:09:15,389 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-04-06 07:09:15,389 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-04-06 07:09:15,389 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-04-06 07:09:15,389 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-04-06 07:09:15,390 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-04-06 07:09:15,391 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-04-06 07:09:15,391 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/LoopAccelerationJordanC.epf [2022-04-06 07:09:15,400 INFO L113 SettingsManager]: Loading preferences was successful [2022-04-06 07:09:15,401 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-04-06 07:09:15,401 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-04-06 07:09:15,402 INFO L138 SettingsManager]: * sizeof long=4 [2022-04-06 07:09:15,402 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-04-06 07:09:15,402 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-04-06 07:09:15,402 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-04-06 07:09:15,402 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-04-06 07:09:15,402 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-04-06 07:09:15,403 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-04-06 07:09:15,403 INFO L138 SettingsManager]: * sizeof long double=12 [2022-04-06 07:09:15,403 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-04-06 07:09:15,403 INFO L138 SettingsManager]: * Use constant arrays=true [2022-04-06 07:09:15,403 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-04-06 07:09:15,403 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-04-06 07:09:15,403 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-04-06 07:09:15,403 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-04-06 07:09:15,403 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-04-06 07:09:15,404 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-06 07:09:15,404 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-04-06 07:09:15,404 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-04-06 07:09:15,405 INFO L136 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2022-04-06 07:09:15,405 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-04-06 07:09:15,587 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-04-06 07:09:15,605 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-04-06 07:09:15,606 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-04-06 07:09:15,607 INFO L271 PluginConnector]: Initializing CDTParser... [2022-04-06 07:09:15,608 INFO L275 PluginConnector]: CDTParser initialized [2022-04-06 07:09:15,609 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/hard-ll_valuebound20.c [2022-04-06 07:09:15,671 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/f3b861340/6a9fad32b712434c93bb13280a506f67/FLAG4a327c99f [2022-04-06 07:09:16,026 INFO L306 CDTParser]: Found 1 translation units. [2022-04-06 07:09:16,027 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/hard-ll_valuebound20.c [2022-04-06 07:09:16,032 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/f3b861340/6a9fad32b712434c93bb13280a506f67/FLAG4a327c99f [2022-04-06 07:09:16,043 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/f3b861340/6a9fad32b712434c93bb13280a506f67 [2022-04-06 07:09:16,045 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-04-06 07:09:16,046 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2022-04-06 07:09:16,048 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-04-06 07:09:16,048 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-04-06 07:09:16,051 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-04-06 07:09:16,051 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.04 07:09:16" (1/1) ... [2022-04-06 07:09:16,052 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@3a64371e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 07:09:16, skipping insertion in model container [2022-04-06 07:09:16,052 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.04 07:09:16" (1/1) ... [2022-04-06 07:09:16,056 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-04-06 07:09:16,065 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-04-06 07:09:16,176 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/hard-ll_valuebound20.c[538,551] [2022-04-06 07:09:16,193 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-06 07:09:16,233 INFO L203 MainTranslator]: Completed pre-run [2022-04-06 07:09:16,243 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/hard-ll_valuebound20.c[538,551] [2022-04-06 07:09:16,256 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-06 07:09:16,265 INFO L208 MainTranslator]: Completed translation [2022-04-06 07:09:16,266 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 07:09:16 WrapperNode [2022-04-06 07:09:16,266 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-04-06 07:09:16,268 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-04-06 07:09:16,268 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-04-06 07:09:16,268 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-04-06 07:09:16,275 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 07:09:16" (1/1) ... [2022-04-06 07:09:16,275 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 07:09:16" (1/1) ... [2022-04-06 07:09:16,279 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 07:09:16" (1/1) ... [2022-04-06 07:09:16,279 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 07:09:16" (1/1) ... [2022-04-06 07:09:16,288 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 07:09:16" (1/1) ... [2022-04-06 07:09:16,292 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 07:09:16" (1/1) ... [2022-04-06 07:09:16,298 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 07:09:16" (1/1) ... [2022-04-06 07:09:16,300 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-04-06 07:09:16,301 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-04-06 07:09:16,301 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-04-06 07:09:16,301 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-04-06 07:09:16,302 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 07:09:16" (1/1) ... [2022-04-06 07:09:16,306 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-06 07:09:16,312 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 07:09:16,321 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-04-06 07:09:16,338 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-04-06 07:09:16,353 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-04-06 07:09:16,353 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-04-06 07:09:16,353 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-04-06 07:09:16,353 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-04-06 07:09:16,354 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-04-06 07:09:16,354 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-04-06 07:09:16,354 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-04-06 07:09:16,354 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-04-06 07:09:16,354 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-04-06 07:09:16,354 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-04-06 07:09:16,354 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_uint [2022-04-06 07:09:16,354 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-04-06 07:09:16,355 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-04-06 07:09:16,355 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-04-06 07:09:16,355 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-04-06 07:09:16,356 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-04-06 07:09:16,356 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-04-06 07:09:16,356 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-04-06 07:09:16,356 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-04-06 07:09:16,356 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-04-06 07:09:16,400 INFO L234 CfgBuilder]: Building ICFG [2022-04-06 07:09:16,402 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-04-06 07:09:16,487 INFO L275 CfgBuilder]: Performing block encoding [2022-04-06 07:09:16,491 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-04-06 07:09:16,491 INFO L299 CfgBuilder]: Removed 2 assume(true) statements. [2022-04-06 07:09:16,492 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.04 07:09:16 BoogieIcfgContainer [2022-04-06 07:09:16,492 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-04-06 07:09:16,493 INFO L113 PluginConnector]: ------------------------IcfgTransformer---------------------------- [2022-04-06 07:09:16,493 INFO L271 PluginConnector]: Initializing IcfgTransformer... [2022-04-06 07:09:16,494 INFO L275 PluginConnector]: IcfgTransformer initialized [2022-04-06 07:09:16,496 INFO L185 PluginConnector]: Executing the observer IcfgTransformationObserver from plugin IcfgTransformer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.04 07:09:16" (1/1) ... [2022-04-06 07:09:16,497 INFO L168 ansformationObserver]: Applying ICFG transformation LOOP_ACCELERATION_JORDAN [2022-04-06 07:09:16,509 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 06.04 07:09:16 BasicIcfg [2022-04-06 07:09:16,509 INFO L132 PluginConnector]: ------------------------ END IcfgTransformer---------------------------- [2022-04-06 07:09:16,510 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-04-06 07:09:16,510 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-04-06 07:09:16,512 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-04-06 07:09:16,513 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 06.04 07:09:16" (1/4) ... [2022-04-06 07:09:16,513 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@79041a1f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.04 07:09:16, skipping insertion in model container [2022-04-06 07:09:16,513 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 07:09:16" (2/4) ... [2022-04-06 07:09:16,513 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@79041a1f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.04 07:09:16, skipping insertion in model container [2022-04-06 07:09:16,514 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.04 07:09:16" (3/4) ... [2022-04-06 07:09:16,514 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@79041a1f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 06.04 07:09:16, skipping insertion in model container [2022-04-06 07:09:16,514 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 06.04 07:09:16" (4/4) ... [2022-04-06 07:09:16,515 INFO L111 eAbstractionObserver]: Analyzing ICFG hard-ll_valuebound20.cJordan [2022-04-06 07:09:16,518 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:false NWA Interpolation:ForwardPredicates Determinization: PREDICATE_ABSTRACTION [2022-04-06 07:09:16,518 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-04-06 07:09:16,564 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-04-06 07:09:16,569 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-04-06 07:09:16,569 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-04-06 07:09:16,577 INFO L276 IsEmpty]: Start isEmpty. Operand has 38 states, 20 states have (on average 1.5) internal successors, (30), 21 states have internal predecessors, (30), 12 states have call successors, (12), 4 states have call predecessors, (12), 4 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-06 07:09:16,582 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2022-04-06 07:09:16,582 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 07:09:16,582 INFO L499 BasicCegarLoop]: trace histogram [3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 07:09:16,582 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 07:09:16,585 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 07:09:16,586 INFO L85 PathProgramCache]: Analyzing trace with hash 1011787902, now seen corresponding path program 1 times [2022-04-06 07:09:16,591 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 07:09:16,592 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1472446178] [2022-04-06 07:09:16,592 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 07:09:16,592 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 07:09:16,667 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 07:09:16,729 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-06 07:09:16,732 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 07:09:16,745 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-06 07:09:16,746 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 07:09:16,751 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2022-04-06 07:09:16,753 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 07:09:16,759 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2022-04-06 07:09:16,760 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 07:09:16,766 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-04-06 07:09:16,766 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 07:09:16,767 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1472446178] [2022-04-06 07:09:16,767 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1472446178] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 07:09:16,767 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 07:09:16,767 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-06 07:09:16,768 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2032559319] [2022-04-06 07:09:16,769 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 07:09:16,771 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-04-06 07:09:16,771 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 07:09:16,795 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-04-06 07:09:16,796 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-06 07:09:16,797 INFO L87 Difference]: Start difference. First operand has 38 states, 20 states have (on average 1.5) internal successors, (30), 21 states have internal predecessors, (30), 12 states have call successors, (12), 4 states have call predecessors, (12), 4 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) Second operand has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-06 07:09:16,865 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 07:09:16,865 INFO L93 Difference]: Finished difference Result 38 states and 48 transitions. [2022-04-06 07:09:16,866 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-04-06 07:09:16,867 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 28 [2022-04-06 07:09:16,867 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 07:09:16,871 INFO L225 Difference]: With dead ends: 38 [2022-04-06 07:09:16,871 INFO L226 Difference]: Without dead ends: 33 [2022-04-06 07:09:16,872 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 12 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-04-06 07:09:16,875 INFO L913 BasicCegarLoop]: 38 mSDtfsCounter, 21 mSDsluCounter, 3 mSDsCounter, 0 mSdLazyCounter, 12 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 31 SdHoareTripleChecker+Valid, 41 SdHoareTripleChecker+Invalid, 23 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 12 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 07:09:16,876 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [31 Valid, 41 Invalid, 23 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 12 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 07:09:16,885 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 33 states. [2022-04-06 07:09:16,899 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 33 to 33. [2022-04-06 07:09:16,900 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 33 states, 17 states have (on average 1.2352941176470589) internal successors, (21), 18 states have internal predecessors, (21), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-06 07:09:16,901 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 43 transitions. [2022-04-06 07:09:16,902 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 43 transitions. Word has length 28 [2022-04-06 07:09:16,903 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 07:09:16,903 INFO L478 AbstractCegarLoop]: Abstraction has 33 states and 43 transitions. [2022-04-06 07:09:16,903 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-06 07:09:16,904 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 43 transitions. [2022-04-06 07:09:16,905 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2022-04-06 07:09:16,905 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 07:09:16,905 INFO L499 BasicCegarLoop]: trace histogram [3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 07:09:16,906 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-04-06 07:09:16,906 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 07:09:16,908 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 07:09:16,908 INFO L85 PathProgramCache]: Analyzing trace with hash -1710049411, now seen corresponding path program 1 times [2022-04-06 07:09:16,908 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 07:09:16,908 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1651673122] [2022-04-06 07:09:16,908 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 07:09:16,909 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 07:09:16,944 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 07:09:17,015 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-06 07:09:17,019 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 07:09:17,029 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-06 07:09:17,035 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 07:09:17,044 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2022-04-06 07:09:17,045 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 07:09:17,064 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2022-04-06 07:09:17,065 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 07:09:17,074 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-04-06 07:09:17,074 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 07:09:17,075 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1651673122] [2022-04-06 07:09:17,075 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1651673122] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 07:09:17,075 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 07:09:17,078 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-06 07:09:17,078 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1362438473] [2022-04-06 07:09:17,078 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 07:09:17,082 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-04-06 07:09:17,082 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 07:09:17,082 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-04-06 07:09:17,082 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-04-06 07:09:17,082 INFO L87 Difference]: Start difference. First operand 33 states and 43 transitions. Second operand has 6 states, 6 states have (on average 2.0) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2022-04-06 07:09:17,265 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 07:09:17,265 INFO L93 Difference]: Finished difference Result 44 states and 58 transitions. [2022-04-06 07:09:17,266 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-04-06 07:09:17,266 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.0) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 28 [2022-04-06 07:09:17,267 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 07:09:17,268 INFO L225 Difference]: With dead ends: 44 [2022-04-06 07:09:17,269 INFO L226 Difference]: Without dead ends: 44 [2022-04-06 07:09:17,269 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 17 GetRequests, 9 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2022-04-06 07:09:17,270 INFO L913 BasicCegarLoop]: 31 mSDtfsCounter, 38 mSDsluCounter, 17 mSDsCounter, 0 mSdLazyCounter, 126 mSolverCounterSat, 29 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 44 SdHoareTripleChecker+Valid, 48 SdHoareTripleChecker+Invalid, 155 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 29 IncrementalHoareTripleChecker+Valid, 126 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 07:09:17,270 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [44 Valid, 48 Invalid, 155 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [29 Valid, 126 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 07:09:17,271 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2022-04-06 07:09:17,275 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 37. [2022-04-06 07:09:17,275 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 37 states, 20 states have (on average 1.2) internal successors, (24), 21 states have internal predecessors, (24), 12 states have call successors, (12), 5 states have call predecessors, (12), 4 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-06 07:09:17,276 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 46 transitions. [2022-04-06 07:09:17,276 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 46 transitions. Word has length 28 [2022-04-06 07:09:17,276 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 07:09:17,276 INFO L478 AbstractCegarLoop]: Abstraction has 37 states and 46 transitions. [2022-04-06 07:09:17,277 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.0) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2022-04-06 07:09:17,277 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 46 transitions. [2022-04-06 07:09:17,277 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2022-04-06 07:09:17,277 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 07:09:17,277 INFO L499 BasicCegarLoop]: trace histogram [3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 07:09:17,277 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2022-04-06 07:09:17,278 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 07:09:17,278 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 07:09:17,278 INFO L85 PathProgramCache]: Analyzing trace with hash 1042498848, now seen corresponding path program 1 times [2022-04-06 07:09:17,278 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 07:09:17,278 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [149497055] [2022-04-06 07:09:17,278 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 07:09:17,278 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 07:09:17,288 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 07:09:17,324 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-06 07:09:17,325 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 07:09:17,328 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-06 07:09:17,328 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 07:09:17,330 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2022-04-06 07:09:17,331 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 07:09:17,333 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2022-04-06 07:09:17,334 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 07:09:17,336 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2022-04-06 07:09:17,337 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 07:09:17,340 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-04-06 07:09:17,340 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 07:09:17,340 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [149497055] [2022-04-06 07:09:17,340 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [149497055] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 07:09:17,340 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 07:09:17,340 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-06 07:09:17,340 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1321036375] [2022-04-06 07:09:17,340 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 07:09:17,341 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-04-06 07:09:17,341 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 07:09:17,341 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-04-06 07:09:17,341 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-04-06 07:09:17,341 INFO L87 Difference]: Start difference. First operand 37 states and 46 transitions. Second operand has 6 states, 6 states have (on average 2.5) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-06 07:09:17,460 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 07:09:17,460 INFO L93 Difference]: Finished difference Result 48 states and 61 transitions. [2022-04-06 07:09:17,461 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-04-06 07:09:17,461 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.5) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 33 [2022-04-06 07:09:17,461 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 07:09:17,461 INFO L225 Difference]: With dead ends: 48 [2022-04-06 07:09:17,461 INFO L226 Difference]: Without dead ends: 48 [2022-04-06 07:09:17,462 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 19 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2022-04-06 07:09:17,463 INFO L913 BasicCegarLoop]: 31 mSDtfsCounter, 33 mSDsluCounter, 17 mSDsCounter, 0 mSdLazyCounter, 132 mSolverCounterSat, 28 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 39 SdHoareTripleChecker+Valid, 48 SdHoareTripleChecker+Invalid, 160 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 28 IncrementalHoareTripleChecker+Valid, 132 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 07:09:17,463 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [39 Valid, 48 Invalid, 160 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [28 Valid, 132 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 07:09:17,463 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states. [2022-04-06 07:09:17,466 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 41. [2022-04-06 07:09:17,466 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 41 states, 23 states have (on average 1.173913043478261) internal successors, (27), 24 states have internal predecessors, (27), 12 states have call successors, (12), 6 states have call predecessors, (12), 5 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-06 07:09:17,467 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 49 transitions. [2022-04-06 07:09:17,467 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 49 transitions. Word has length 33 [2022-04-06 07:09:17,467 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 07:09:17,467 INFO L478 AbstractCegarLoop]: Abstraction has 41 states and 49 transitions. [2022-04-06 07:09:17,467 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.5) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-06 07:09:17,468 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 49 transitions. [2022-04-06 07:09:17,468 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2022-04-06 07:09:17,468 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 07:09:17,468 INFO L499 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 07:09:17,468 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2022-04-06 07:09:17,469 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 07:09:17,469 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 07:09:17,469 INFO L85 PathProgramCache]: Analyzing trace with hash 1436069466, now seen corresponding path program 1 times [2022-04-06 07:09:17,469 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 07:09:17,469 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1198937756] [2022-04-06 07:09:17,469 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 07:09:17,469 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 07:09:17,478 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 07:09:17,478 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [488818274] [2022-04-06 07:09:17,478 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 07:09:17,479 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 07:09:17,479 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 07:09:17,480 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-04-06 07:09:17,537 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-04-06 07:09:17,546 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 07:09:17,547 INFO L263 TraceCheckSpWp]: Trace formula consists of 106 conjuncts, 12 conjunts are in the unsatisfiable core [2022-04-06 07:09:17,551 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 07:09:17,739 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2022-04-06 07:09:17,739 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-06 07:09:17,740 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 07:09:17,740 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1198937756] [2022-04-06 07:09:17,740 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 07:09:17,740 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [488818274] [2022-04-06 07:09:17,740 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [488818274] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 07:09:17,740 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 07:09:17,740 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2022-04-06 07:09:17,740 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [284831262] [2022-04-06 07:09:17,740 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 07:09:17,741 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-04-06 07:09:17,741 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 07:09:17,741 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-04-06 07:09:17,741 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2022-04-06 07:09:17,741 INFO L87 Difference]: Start difference. First operand 41 states and 49 transitions. Second operand has 8 states, 8 states have (on average 2.25) internal successors, (18), 6 states have internal predecessors, (18), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (6), 3 states have call predecessors, (6), 2 states have call successors, (6) [2022-04-06 07:09:17,861 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 07:09:17,861 INFO L93 Difference]: Finished difference Result 56 states and 70 transitions. [2022-04-06 07:09:17,861 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-04-06 07:09:17,862 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 2.25) internal successors, (18), 6 states have internal predecessors, (18), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (6), 3 states have call predecessors, (6), 2 states have call successors, (6) Word has length 38 [2022-04-06 07:09:17,862 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 07:09:17,863 INFO L225 Difference]: With dead ends: 56 [2022-04-06 07:09:17,863 INFO L226 Difference]: Without dead ends: 55 [2022-04-06 07:09:17,864 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 39 GetRequests, 31 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=22, Invalid=68, Unknown=0, NotChecked=0, Total=90 [2022-04-06 07:09:17,871 INFO L913 BasicCegarLoop]: 40 mSDtfsCounter, 20 mSDsluCounter, 156 mSDsCounter, 0 mSdLazyCounter, 128 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 30 SdHoareTripleChecker+Valid, 196 SdHoareTripleChecker+Invalid, 134 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 128 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 07:09:17,872 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [30 Valid, 196 Invalid, 134 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 128 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 07:09:17,873 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2022-04-06 07:09:17,880 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 55. [2022-04-06 07:09:17,880 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 55 states, 30 states have (on average 1.1666666666666667) internal successors, (35), 32 states have internal predecessors, (35), 18 states have call successors, (18), 7 states have call predecessors, (18), 6 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) [2022-04-06 07:09:17,881 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 68 transitions. [2022-04-06 07:09:17,882 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 68 transitions. Word has length 38 [2022-04-06 07:09:17,882 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 07:09:17,882 INFO L478 AbstractCegarLoop]: Abstraction has 55 states and 68 transitions. [2022-04-06 07:09:17,882 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 2.25) internal successors, (18), 6 states have internal predecessors, (18), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (6), 3 states have call predecessors, (6), 2 states have call successors, (6) [2022-04-06 07:09:17,883 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 68 transitions. [2022-04-06 07:09:17,883 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2022-04-06 07:09:17,884 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 07:09:17,884 INFO L499 BasicCegarLoop]: trace histogram [4, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 07:09:17,906 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-04-06 07:09:18,084 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 07:09:18,085 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 07:09:18,085 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 07:09:18,085 INFO L85 PathProgramCache]: Analyzing trace with hash 5711864, now seen corresponding path program 1 times [2022-04-06 07:09:18,085 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 07:09:18,086 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1799871844] [2022-04-06 07:09:18,086 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 07:09:18,086 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 07:09:18,093 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 07:09:18,093 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1748700121] [2022-04-06 07:09:18,093 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 07:09:18,093 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 07:09:18,093 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 07:09:18,103 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-04-06 07:09:18,104 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-04-06 07:09:18,137 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 07:09:18,138 INFO L263 TraceCheckSpWp]: Trace formula consists of 117 conjuncts, 14 conjunts are in the unsatisfiable core [2022-04-06 07:09:18,140 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 07:09:18,318 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 9 proven. 3 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2022-04-06 07:09:18,318 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 07:09:18,454 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-04-06 07:09:18,454 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 07:09:18,457 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1799871844] [2022-04-06 07:09:18,457 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 07:09:18,457 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1748700121] [2022-04-06 07:09:18,458 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1748700121] provided 1 perfect and 1 imperfect interpolant sequences [2022-04-06 07:09:18,458 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-04-06 07:09:18,458 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [9] total 11 [2022-04-06 07:09:18,458 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [537201850] [2022-04-06 07:09:18,458 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 07:09:18,458 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-04-06 07:09:18,458 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 07:09:18,459 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-04-06 07:09:18,459 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=84, Unknown=0, NotChecked=0, Total=110 [2022-04-06 07:09:18,460 INFO L87 Difference]: Start difference. First operand 55 states and 68 transitions. Second operand has 6 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 5 states have internal predecessors, (17), 3 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-04-06 07:09:18,516 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 07:09:18,516 INFO L93 Difference]: Finished difference Result 66 states and 83 transitions. [2022-04-06 07:09:18,516 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-06 07:09:18,516 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 5 states have internal predecessors, (17), 3 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 45 [2022-04-06 07:09:18,518 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 07:09:18,519 INFO L225 Difference]: With dead ends: 66 [2022-04-06 07:09:18,519 INFO L226 Difference]: Without dead ends: 66 [2022-04-06 07:09:18,519 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 90 GetRequests, 79 SyntacticMatches, 1 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2022-04-06 07:09:18,519 INFO L913 BasicCegarLoop]: 42 mSDtfsCounter, 12 mSDsluCounter, 109 mSDsCounter, 0 mSdLazyCounter, 68 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 151 SdHoareTripleChecker+Invalid, 69 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 68 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 07:09:18,520 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [18 Valid, 151 Invalid, 69 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 68 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 07:09:18,520 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 66 states. [2022-04-06 07:09:18,523 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 66 to 64. [2022-04-06 07:09:18,523 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 64 states, 36 states have (on average 1.1944444444444444) internal successors, (43), 38 states have internal predecessors, (43), 20 states have call successors, (20), 8 states have call predecessors, (20), 7 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) [2022-04-06 07:09:18,524 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 64 states to 64 states and 80 transitions. [2022-04-06 07:09:18,524 INFO L78 Accepts]: Start accepts. Automaton has 64 states and 80 transitions. Word has length 45 [2022-04-06 07:09:18,524 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 07:09:18,524 INFO L478 AbstractCegarLoop]: Abstraction has 64 states and 80 transitions. [2022-04-06 07:09:18,525 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 5 states have internal predecessors, (17), 3 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-04-06 07:09:18,525 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 80 transitions. [2022-04-06 07:09:18,525 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2022-04-06 07:09:18,525 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 07:09:18,526 INFO L499 BasicCegarLoop]: trace histogram [6, 5, 5, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 07:09:18,543 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-04-06 07:09:18,726 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 07:09:18,726 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 07:09:18,727 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 07:09:18,728 INFO L85 PathProgramCache]: Analyzing trace with hash 1597443315, now seen corresponding path program 1 times [2022-04-06 07:09:18,728 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 07:09:18,728 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [38568734] [2022-04-06 07:09:18,728 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 07:09:18,729 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 07:09:18,743 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 07:09:18,743 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1755335088] [2022-04-06 07:09:18,743 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 07:09:18,743 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 07:09:18,743 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 07:09:18,749 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-04-06 07:09:18,752 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-04-06 07:09:18,797 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 07:09:18,798 INFO L263 TraceCheckSpWp]: Trace formula consists of 139 conjuncts, 16 conjunts are in the unsatisfiable core [2022-04-06 07:09:18,799 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 07:09:18,984 INFO L134 CoverageAnalysis]: Checked inductivity of 66 backedges. 16 proven. 4 refuted. 0 times theorem prover too weak. 46 trivial. 0 not checked. [2022-04-06 07:09:18,985 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 07:09:19,093 INFO L134 CoverageAnalysis]: Checked inductivity of 66 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 56 trivial. 0 not checked. [2022-04-06 07:09:19,093 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 07:09:19,094 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [38568734] [2022-04-06 07:09:19,094 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 07:09:19,094 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1755335088] [2022-04-06 07:09:19,094 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1755335088] provided 1 perfect and 1 imperfect interpolant sequences [2022-04-06 07:09:19,094 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-04-06 07:09:19,094 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [9] total 10 [2022-04-06 07:09:19,094 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [123880458] [2022-04-06 07:09:19,094 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 07:09:19,095 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-06 07:09:19,095 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 07:09:19,096 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-06 07:09:19,096 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=69, Unknown=0, NotChecked=0, Total=90 [2022-04-06 07:09:19,097 INFO L87 Difference]: Start difference. First operand 64 states and 80 transitions. Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-04-06 07:09:19,167 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 07:09:19,167 INFO L93 Difference]: Finished difference Result 74 states and 93 transitions. [2022-04-06 07:09:19,167 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-06 07:09:19,167 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 55 [2022-04-06 07:09:19,168 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 07:09:19,171 INFO L225 Difference]: With dead ends: 74 [2022-04-06 07:09:19,171 INFO L226 Difference]: Without dead ends: 74 [2022-04-06 07:09:19,171 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 110 GetRequests, 99 SyntacticMatches, 2 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=25, Invalid=85, Unknown=0, NotChecked=0, Total=110 [2022-04-06 07:09:19,172 INFO L913 BasicCegarLoop]: 41 mSDtfsCounter, 8 mSDsluCounter, 88 mSDsCounter, 0 mSdLazyCounter, 50 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 129 SdHoareTripleChecker+Invalid, 51 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 50 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 07:09:19,173 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [11 Valid, 129 Invalid, 51 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 50 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 07:09:19,174 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 74 states. [2022-04-06 07:09:19,189 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 74 to 71. [2022-04-06 07:09:19,189 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 71 states, 40 states have (on average 1.175) internal successors, (47), 43 states have internal predecessors, (47), 22 states have call successors, (22), 9 states have call predecessors, (22), 8 states have return successors, (19), 18 states have call predecessors, (19), 19 states have call successors, (19) [2022-04-06 07:09:19,190 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 88 transitions. [2022-04-06 07:09:19,190 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 88 transitions. Word has length 55 [2022-04-06 07:09:19,190 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 07:09:19,190 INFO L478 AbstractCegarLoop]: Abstraction has 71 states and 88 transitions. [2022-04-06 07:09:19,191 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-04-06 07:09:19,191 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 88 transitions. [2022-04-06 07:09:19,192 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2022-04-06 07:09:19,192 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 07:09:19,192 INFO L499 BasicCegarLoop]: trace histogram [6, 5, 5, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 07:09:19,227 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-04-06 07:09:19,392 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 07:09:19,393 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 07:09:19,393 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 07:09:19,393 INFO L85 PathProgramCache]: Analyzing trace with hash 810354846, now seen corresponding path program 1 times [2022-04-06 07:09:19,393 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 07:09:19,393 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [41478483] [2022-04-06 07:09:19,393 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 07:09:19,393 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 07:09:19,403 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 07:09:19,403 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1866532566] [2022-04-06 07:09:19,403 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 07:09:19,403 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 07:09:19,404 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 07:09:19,404 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-04-06 07:09:19,426 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-04-06 07:09:19,463 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 07:09:19,464 INFO L263 TraceCheckSpWp]: Trace formula consists of 137 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-06 07:09:19,466 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 07:09:19,538 INFO L134 CoverageAnalysis]: Checked inductivity of 62 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2022-04-06 07:09:19,538 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-06 07:09:19,538 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 07:09:19,538 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [41478483] [2022-04-06 07:09:19,539 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 07:09:19,539 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1866532566] [2022-04-06 07:09:19,539 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1866532566] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 07:09:19,539 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 07:09:19,539 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 07:09:19,539 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1700359314] [2022-04-06 07:09:19,539 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 07:09:19,539 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-06 07:09:19,539 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 07:09:19,540 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-06 07:09:19,540 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-06 07:09:19,540 INFO L87 Difference]: Start difference. First operand 71 states and 88 transitions. Second operand has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2022-04-06 07:09:19,570 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 07:09:19,571 INFO L93 Difference]: Finished difference Result 77 states and 94 transitions. [2022-04-06 07:09:19,571 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-06 07:09:19,571 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) Word has length 56 [2022-04-06 07:09:19,571 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 07:09:19,572 INFO L225 Difference]: With dead ends: 77 [2022-04-06 07:09:19,573 INFO L226 Difference]: Without dead ends: 72 [2022-04-06 07:09:19,573 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 56 GetRequests, 52 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-04-06 07:09:19,573 INFO L913 BasicCegarLoop]: 36 mSDtfsCounter, 8 mSDsluCounter, 87 mSDsCounter, 0 mSdLazyCounter, 49 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 123 SdHoareTripleChecker+Invalid, 52 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 49 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 07:09:19,573 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [9 Valid, 123 Invalid, 52 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 49 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 07:09:19,574 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 72 states. [2022-04-06 07:09:19,577 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 72 to 71. [2022-04-06 07:09:19,577 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 71 states, 41 states have (on average 1.146341463414634) internal successors, (47), 44 states have internal predecessors, (47), 20 states have call successors, (20), 10 states have call predecessors, (20), 9 states have return successors, (18), 16 states have call predecessors, (18), 18 states have call successors, (18) [2022-04-06 07:09:19,578 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 85 transitions. [2022-04-06 07:09:19,578 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 85 transitions. Word has length 56 [2022-04-06 07:09:19,578 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 07:09:19,578 INFO L478 AbstractCegarLoop]: Abstraction has 71 states and 85 transitions. [2022-04-06 07:09:19,578 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2022-04-06 07:09:19,578 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 85 transitions. [2022-04-06 07:09:19,579 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 76 [2022-04-06 07:09:19,579 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 07:09:19,579 INFO L499 BasicCegarLoop]: trace histogram [9, 8, 8, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 07:09:19,606 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-04-06 07:09:19,806 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 07:09:19,806 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 07:09:19,807 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 07:09:19,807 INFO L85 PathProgramCache]: Analyzing trace with hash 1689231171, now seen corresponding path program 1 times [2022-04-06 07:09:19,807 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 07:09:19,807 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [549537796] [2022-04-06 07:09:19,807 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 07:09:19,807 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 07:09:19,815 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 07:09:19,815 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1007509792] [2022-04-06 07:09:19,815 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 07:09:19,815 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 07:09:19,815 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 07:09:19,816 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-04-06 07:09:19,817 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-04-06 07:09:19,871 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 07:09:19,871 INFO L263 TraceCheckSpWp]: Trace formula consists of 179 conjuncts, 30 conjunts are in the unsatisfiable core [2022-04-06 07:09:19,873 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 07:09:20,424 INFO L134 CoverageAnalysis]: Checked inductivity of 147 backedges. 36 proven. 8 refuted. 0 times theorem prover too weak. 103 trivial. 0 not checked. [2022-04-06 07:09:20,424 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 07:09:52,919 WARN L232 SmtUtils]: Spent 17.86s on a formula simplification that was a NOOP. DAG size: 53 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-06 07:10:42,340 WARN L855 $PredicateComparison]: unable to prove that (let ((.cse0 (mod c_main_~B~0 4294967296))) (or (<= c_main_~d~0 c_main_~r~0) (not (= c_main_~d~0 (* c_main_~p~0 .cse0))) (let ((.cse4 (= (mod c_main_~p~0 2) 0)) (.cse10 (div c_main_~p~0 2))) (let ((.cse6 (* (+ c_main_~q~0 .cse10) .cse0)) (.cse7 (not .cse4)) (.cse1 (mod c_main_~A~0 4294967296)) (.cse2 (* (- 1) (div c_main_~d~0 2))) (.cse3 (* (+ c_main_~q~0 .cse10 1) .cse0)) (.cse9 (= (mod c_main_~d~0 2) 0)) (.cse8 (< c_main_~d~0 0))) (and (or (let ((.cse5 (< c_main_~p~0 0))) (and (or (= .cse1 (+ c_main_~r~0 .cse2 .cse3)) .cse4 (not .cse5)) (or (= .cse1 (+ .cse6 c_main_~r~0 .cse2)) (and .cse7 .cse5)))) (and .cse8 (not .cse9))) (or (and (or (= .cse1 (+ (- 1) .cse6 c_main_~r~0 .cse2)) .cse7) (or .cse4 (= .cse1 (+ (- 1) c_main_~r~0 .cse2 .cse3)))) .cse9 (not .cse8))))))) is different from true [2022-04-06 07:11:43,879 INFO L134 CoverageAnalysis]: Checked inductivity of 147 backedges. 36 proven. 3 refuted. 0 times theorem prover too weak. 103 trivial. 5 not checked. [2022-04-06 07:11:43,879 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 07:11:43,879 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [549537796] [2022-04-06 07:11:43,880 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 07:11:43,880 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1007509792] [2022-04-06 07:11:43,880 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1007509792] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 07:11:43,880 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 07:11:43,880 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 12] total 18 [2022-04-06 07:11:43,880 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1031226627] [2022-04-06 07:11:43,880 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-06 07:11:43,881 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2022-04-06 07:11:43,881 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 07:11:43,881 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2022-04-06 07:11:43,881 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=60, Invalid=215, Unknown=1, NotChecked=30, Total=306 [2022-04-06 07:11:43,881 INFO L87 Difference]: Start difference. First operand 71 states and 85 transitions. Second operand has 18 states, 18 states have (on average 2.0) internal successors, (36), 16 states have internal predecessors, (36), 9 states have call successors, (23), 2 states have call predecessors, (23), 2 states have return successors, (20), 8 states have call predecessors, (20), 7 states have call successors, (20) [2022-04-06 07:11:45,962 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-06 07:11:49,098 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-06 07:12:13,505 WARN L232 SmtUtils]: Spent 23.39s on a formula simplification. DAG size of input: 67 DAG size of output: 27 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-06 07:12:15,753 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-06 07:12:18,609 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.60s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-06 07:12:20,712 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 07:12:20,712 INFO L93 Difference]: Finished difference Result 115 states and 147 transitions. [2022-04-06 07:12:20,713 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2022-04-06 07:12:20,713 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 18 states have (on average 2.0) internal successors, (36), 16 states have internal predecessors, (36), 9 states have call successors, (23), 2 states have call predecessors, (23), 2 states have return successors, (20), 8 states have call predecessors, (20), 7 states have call successors, (20) Word has length 75 [2022-04-06 07:12:20,713 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 07:12:20,714 INFO L225 Difference]: With dead ends: 115 [2022-04-06 07:12:20,714 INFO L226 Difference]: Without dead ends: 115 [2022-04-06 07:12:20,714 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 156 GetRequests, 131 SyntacticMatches, 4 SemanticMatches, 21 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 85 ImplicationChecksByTransitivity, 45.3s TimeCoverageRelationStatistics Valid=99, Invalid=366, Unknown=1, NotChecked=40, Total=506 [2022-04-06 07:12:20,715 INFO L913 BasicCegarLoop]: 37 mSDtfsCounter, 57 mSDsluCounter, 149 mSDsCounter, 0 mSdLazyCounter, 433 mSolverCounterSat, 124 mSolverCounterUnsat, 3 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 11.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 62 SdHoareTripleChecker+Valid, 186 SdHoareTripleChecker+Invalid, 636 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 124 IncrementalHoareTripleChecker+Valid, 433 IncrementalHoareTripleChecker+Invalid, 3 IncrementalHoareTripleChecker+Unknown, 76 IncrementalHoareTripleChecker+Unchecked, 12.0s IncrementalHoareTripleChecker+Time [2022-04-06 07:12:20,715 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [62 Valid, 186 Invalid, 636 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [124 Valid, 433 Invalid, 3 Unknown, 76 Unchecked, 12.0s Time] [2022-04-06 07:12:20,715 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 115 states. [2022-04-06 07:12:20,721 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 115 to 103. [2022-04-06 07:12:20,722 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 103 states, 60 states have (on average 1.15) internal successors, (69), 65 states have internal predecessors, (69), 30 states have call successors, (30), 13 states have call predecessors, (30), 12 states have return successors, (28), 24 states have call predecessors, (28), 28 states have call successors, (28) [2022-04-06 07:12:20,722 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 103 states to 103 states and 127 transitions. [2022-04-06 07:12:20,722 INFO L78 Accepts]: Start accepts. Automaton has 103 states and 127 transitions. Word has length 75 [2022-04-06 07:12:20,723 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 07:12:20,723 INFO L478 AbstractCegarLoop]: Abstraction has 103 states and 127 transitions. [2022-04-06 07:12:20,723 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 18 states have (on average 2.0) internal successors, (36), 16 states have internal predecessors, (36), 9 states have call successors, (23), 2 states have call predecessors, (23), 2 states have return successors, (20), 8 states have call predecessors, (20), 7 states have call successors, (20) [2022-04-06 07:12:20,723 INFO L276 IsEmpty]: Start isEmpty. Operand 103 states and 127 transitions. [2022-04-06 07:12:20,724 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 87 [2022-04-06 07:12:20,724 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 07:12:20,724 INFO L499 BasicCegarLoop]: trace histogram [11, 10, 10, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 07:12:20,742 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2022-04-06 07:12:20,935 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 07:12:20,936 INFO L403 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 07:12:20,936 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 07:12:20,936 INFO L85 PathProgramCache]: Analyzing trace with hash -102783885, now seen corresponding path program 1 times [2022-04-06 07:12:20,936 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 07:12:20,936 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [890187997] [2022-04-06 07:12:20,936 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 07:12:20,936 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 07:12:20,944 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 07:12:20,944 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [554242339] [2022-04-06 07:12:20,944 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 07:12:20,944 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 07:12:20,944 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 07:12:20,945 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-04-06 07:12:20,945 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-04-06 07:12:20,986 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 07:12:20,987 INFO L263 TraceCheckSpWp]: Trace formula consists of 199 conjuncts, 13 conjunts are in the unsatisfiable core [2022-04-06 07:12:20,989 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 07:12:21,176 INFO L134 CoverageAnalysis]: Checked inductivity of 221 backedges. 20 proven. 4 refuted. 0 times theorem prover too weak. 197 trivial. 0 not checked. [2022-04-06 07:12:21,177 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 07:12:21,380 INFO L134 CoverageAnalysis]: Checked inductivity of 221 backedges. 20 proven. 4 refuted. 0 times theorem prover too weak. 197 trivial. 0 not checked. [2022-04-06 07:12:21,380 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 07:12:21,380 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [890187997] [2022-04-06 07:12:21,380 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 07:12:21,380 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [554242339] [2022-04-06 07:12:21,381 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [554242339] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 07:12:21,381 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 07:12:21,381 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 9 [2022-04-06 07:12:21,381 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [572471975] [2022-04-06 07:12:21,381 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-06 07:12:21,381 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-04-06 07:12:21,381 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 07:12:21,382 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-04-06 07:12:21,382 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=51, Unknown=0, NotChecked=0, Total=72 [2022-04-06 07:12:21,382 INFO L87 Difference]: Start difference. First operand 103 states and 127 transitions. Second operand has 9 states, 7 states have (on average 3.5714285714285716) internal successors, (25), 8 states have internal predecessors, (25), 6 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (13), 4 states have call predecessors, (13), 4 states have call successors, (13) [2022-04-06 07:12:21,708 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 07:12:21,708 INFO L93 Difference]: Finished difference Result 114 states and 141 transitions. [2022-04-06 07:12:21,709 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-04-06 07:12:21,709 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 7 states have (on average 3.5714285714285716) internal successors, (25), 8 states have internal predecessors, (25), 6 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (13), 4 states have call predecessors, (13), 4 states have call successors, (13) Word has length 86 [2022-04-06 07:12:21,709 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 07:12:21,710 INFO L225 Difference]: With dead ends: 114 [2022-04-06 07:12:21,710 INFO L226 Difference]: Without dead ends: 114 [2022-04-06 07:12:21,710 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 173 GetRequests, 162 SyntacticMatches, 2 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=31, Invalid=79, Unknown=0, NotChecked=0, Total=110 [2022-04-06 07:12:21,710 INFO L913 BasicCegarLoop]: 44 mSDtfsCounter, 21 mSDsluCounter, 117 mSDsCounter, 0 mSdLazyCounter, 121 mSolverCounterSat, 17 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 161 SdHoareTripleChecker+Invalid, 138 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 17 IncrementalHoareTripleChecker+Valid, 121 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-04-06 07:12:21,710 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [22 Valid, 161 Invalid, 138 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [17 Valid, 121 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-04-06 07:12:21,711 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 114 states. [2022-04-06 07:12:21,715 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 114 to 107. [2022-04-06 07:12:21,715 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 107 states, 62 states have (on average 1.1612903225806452) internal successors, (72), 67 states have internal predecessors, (72), 32 states have call successors, (32), 13 states have call predecessors, (32), 12 states have return successors, (30), 26 states have call predecessors, (30), 30 states have call successors, (30) [2022-04-06 07:12:21,715 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 107 states to 107 states and 134 transitions. [2022-04-06 07:12:21,716 INFO L78 Accepts]: Start accepts. Automaton has 107 states and 134 transitions. Word has length 86 [2022-04-06 07:12:21,716 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 07:12:21,716 INFO L478 AbstractCegarLoop]: Abstraction has 107 states and 134 transitions. [2022-04-06 07:12:21,716 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 7 states have (on average 3.5714285714285716) internal successors, (25), 8 states have internal predecessors, (25), 6 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (13), 4 states have call predecessors, (13), 4 states have call successors, (13) [2022-04-06 07:12:21,716 INFO L276 IsEmpty]: Start isEmpty. Operand 107 states and 134 transitions. [2022-04-06 07:12:21,717 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 89 [2022-04-06 07:12:21,717 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 07:12:21,717 INFO L499 BasicCegarLoop]: trace histogram [11, 10, 10, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 07:12:21,735 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-04-06 07:12:21,927 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 07:12:21,927 INFO L403 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 07:12:21,928 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 07:12:21,928 INFO L85 PathProgramCache]: Analyzing trace with hash 1406960063, now seen corresponding path program 2 times [2022-04-06 07:12:21,928 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 07:12:21,928 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1427471207] [2022-04-06 07:12:21,928 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 07:12:21,928 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 07:12:21,935 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 07:12:21,935 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1183095948] [2022-04-06 07:12:21,935 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 07:12:21,935 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 07:12:21,935 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 07:12:21,936 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-04-06 07:12:21,952 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-04-06 07:12:21,984 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 07:12:21,984 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 07:12:21,985 INFO L263 TraceCheckSpWp]: Trace formula consists of 208 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-06 07:12:21,986 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 07:12:22,095 INFO L134 CoverageAnalysis]: Checked inductivity of 226 backedges. 25 proven. 9 refuted. 0 times theorem prover too weak. 192 trivial. 0 not checked. [2022-04-06 07:12:22,095 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 07:12:22,273 INFO L134 CoverageAnalysis]: Checked inductivity of 226 backedges. 25 proven. 9 refuted. 0 times theorem prover too weak. 192 trivial. 0 not checked. [2022-04-06 07:12:22,273 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 07:12:22,273 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1427471207] [2022-04-06 07:12:22,273 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 07:12:22,273 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1183095948] [2022-04-06 07:12:22,273 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1183095948] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 07:12:22,274 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 07:12:22,274 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 5 [2022-04-06 07:12:22,275 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1726100156] [2022-04-06 07:12:22,276 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-06 07:12:22,277 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-06 07:12:22,278 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 07:12:22,278 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-06 07:12:22,278 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-04-06 07:12:22,278 INFO L87 Difference]: Start difference. First operand 107 states and 134 transitions. Second operand has 5 states, 5 states have (on average 6.0) internal successors, (30), 5 states have internal predecessors, (30), 5 states have call successors, (21), 2 states have call predecessors, (21), 1 states have return successors, (19), 4 states have call predecessors, (19), 4 states have call successors, (19) [2022-04-06 07:12:22,341 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 07:12:22,341 INFO L93 Difference]: Finished difference Result 111 states and 140 transitions. [2022-04-06 07:12:22,341 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2022-04-06 07:12:22,341 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 6.0) internal successors, (30), 5 states have internal predecessors, (30), 5 states have call successors, (21), 2 states have call predecessors, (21), 1 states have return successors, (19), 4 states have call predecessors, (19), 4 states have call successors, (19) Word has length 88 [2022-04-06 07:12:22,342 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 07:12:22,343 INFO L225 Difference]: With dead ends: 111 [2022-04-06 07:12:22,343 INFO L226 Difference]: Without dead ends: 111 [2022-04-06 07:12:22,343 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 175 GetRequests, 171 SyntacticMatches, 1 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-04-06 07:12:22,344 INFO L913 BasicCegarLoop]: 56 mSDtfsCounter, 1 mSDsluCounter, 113 mSDsCounter, 0 mSdLazyCounter, 51 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 169 SdHoareTripleChecker+Invalid, 52 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 51 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 07:12:22,344 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 169 Invalid, 52 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 51 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 07:12:22,344 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 111 states. [2022-04-06 07:12:22,348 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 111 to 111. [2022-04-06 07:12:22,348 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 111 states, 64 states have (on average 1.15625) internal successors, (74), 69 states have internal predecessors, (74), 34 states have call successors, (34), 13 states have call predecessors, (34), 12 states have return successors, (32), 28 states have call predecessors, (32), 32 states have call successors, (32) [2022-04-06 07:12:22,349 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 111 states to 111 states and 140 transitions. [2022-04-06 07:12:22,349 INFO L78 Accepts]: Start accepts. Automaton has 111 states and 140 transitions. Word has length 88 [2022-04-06 07:12:22,349 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 07:12:22,349 INFO L478 AbstractCegarLoop]: Abstraction has 111 states and 140 transitions. [2022-04-06 07:12:22,349 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 6.0) internal successors, (30), 5 states have internal predecessors, (30), 5 states have call successors, (21), 2 states have call predecessors, (21), 1 states have return successors, (19), 4 states have call predecessors, (19), 4 states have call successors, (19) [2022-04-06 07:12:22,349 INFO L276 IsEmpty]: Start isEmpty. Operand 111 states and 140 transitions. [2022-04-06 07:12:22,350 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 92 [2022-04-06 07:12:22,350 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 07:12:22,350 INFO L499 BasicCegarLoop]: trace histogram [12, 11, 11, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 07:12:22,371 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-04-06 07:12:22,571 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 07:12:22,573 INFO L403 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 07:12:22,573 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 07:12:22,573 INFO L85 PathProgramCache]: Analyzing trace with hash 966352941, now seen corresponding path program 1 times [2022-04-06 07:12:22,573 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 07:12:22,574 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1705617696] [2022-04-06 07:12:22,574 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 07:12:22,574 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 07:12:22,581 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 07:12:22,581 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [606585501] [2022-04-06 07:12:22,581 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 07:12:22,581 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 07:12:22,581 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 07:12:22,589 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-04-06 07:12:22,589 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-04-06 07:12:22,635 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 07:12:22,636 INFO L263 TraceCheckSpWp]: Trace formula consists of 208 conjuncts, 11 conjunts are in the unsatisfiable core [2022-04-06 07:12:22,637 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 07:12:22,824 INFO L134 CoverageAnalysis]: Checked inductivity of 263 backedges. 22 proven. 9 refuted. 0 times theorem prover too weak. 232 trivial. 0 not checked. [2022-04-06 07:12:22,825 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 07:12:23,133 INFO L134 CoverageAnalysis]: Checked inductivity of 263 backedges. 22 proven. 9 refuted. 0 times theorem prover too weak. 232 trivial. 0 not checked. [2022-04-06 07:12:23,133 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 07:12:23,134 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1705617696] [2022-04-06 07:12:23,134 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 07:12:23,134 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [606585501] [2022-04-06 07:12:23,134 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [606585501] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 07:12:23,134 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 07:12:23,134 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 11 [2022-04-06 07:12:23,134 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [798166910] [2022-04-06 07:12:23,134 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-06 07:12:23,135 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2022-04-06 07:12:23,135 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 07:12:23,135 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2022-04-06 07:12:23,135 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=83, Unknown=0, NotChecked=0, Total=110 [2022-04-06 07:12:23,135 INFO L87 Difference]: Start difference. First operand 111 states and 140 transitions. Second operand has 11 states, 11 states have (on average 3.0) internal successors, (33), 10 states have internal predecessors, (33), 8 states have call successors, (29), 2 states have call predecessors, (29), 1 states have return successors, (26), 8 states have call predecessors, (26), 8 states have call successors, (26) [2022-04-06 07:12:23,381 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 07:12:23,381 INFO L93 Difference]: Finished difference Result 117 states and 146 transitions. [2022-04-06 07:12:23,382 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-04-06 07:12:23,382 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 3.0) internal successors, (33), 10 states have internal predecessors, (33), 8 states have call successors, (29), 2 states have call predecessors, (29), 1 states have return successors, (26), 8 states have call predecessors, (26), 8 states have call successors, (26) Word has length 91 [2022-04-06 07:12:23,382 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 07:12:23,383 INFO L225 Difference]: With dead ends: 117 [2022-04-06 07:12:23,383 INFO L226 Difference]: Without dead ends: 102 [2022-04-06 07:12:23,383 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 184 GetRequests, 171 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=43, Invalid=139, Unknown=0, NotChecked=0, Total=182 [2022-04-06 07:12:23,383 INFO L913 BasicCegarLoop]: 58 mSDtfsCounter, 12 mSDsluCounter, 181 mSDsCounter, 0 mSdLazyCounter, 131 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 239 SdHoareTripleChecker+Invalid, 145 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 131 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-04-06 07:12:23,384 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [12 Valid, 239 Invalid, 145 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 131 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-04-06 07:12:23,384 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 102 states. [2022-04-06 07:12:23,388 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 102 to 102. [2022-04-06 07:12:23,388 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 102 states, 59 states have (on average 1.152542372881356) internal successors, (68), 64 states have internal predecessors, (68), 30 states have call successors, (30), 13 states have call predecessors, (30), 12 states have return successors, (28), 24 states have call predecessors, (28), 28 states have call successors, (28) [2022-04-06 07:12:23,389 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 102 states to 102 states and 126 transitions. [2022-04-06 07:12:23,389 INFO L78 Accepts]: Start accepts. Automaton has 102 states and 126 transitions. Word has length 91 [2022-04-06 07:12:23,389 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 07:12:23,389 INFO L478 AbstractCegarLoop]: Abstraction has 102 states and 126 transitions. [2022-04-06 07:12:23,390 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 3.0) internal successors, (33), 10 states have internal predecessors, (33), 8 states have call successors, (29), 2 states have call predecessors, (29), 1 states have return successors, (26), 8 states have call predecessors, (26), 8 states have call successors, (26) [2022-04-06 07:12:23,390 INFO L276 IsEmpty]: Start isEmpty. Operand 102 states and 126 transitions. [2022-04-06 07:12:23,390 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 96 [2022-04-06 07:12:23,390 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 07:12:23,390 INFO L499 BasicCegarLoop]: trace histogram [13, 12, 12, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 07:12:23,429 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-04-06 07:12:23,605 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,SelfDestructingSolverStorable10 [2022-04-06 07:12:23,605 INFO L403 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 07:12:23,605 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 07:12:23,605 INFO L85 PathProgramCache]: Analyzing trace with hash -1871497790, now seen corresponding path program 1 times [2022-04-06 07:12:23,606 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 07:12:23,606 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [185196514] [2022-04-06 07:12:23,606 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 07:12:23,606 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 07:12:23,613 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 07:12:23,613 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [900334107] [2022-04-06 07:12:23,613 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 07:12:23,613 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 07:12:23,614 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 07:12:23,635 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-04-06 07:12:23,653 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-04-06 07:12:23,689 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 07:12:23,690 INFO L263 TraceCheckSpWp]: Trace formula consists of 212 conjuncts, 4 conjunts are in the unsatisfiable core [2022-04-06 07:12:23,691 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 07:12:23,884 INFO L134 CoverageAnalysis]: Checked inductivity of 315 backedges. 81 proven. 0 refuted. 0 times theorem prover too weak. 234 trivial. 0 not checked. [2022-04-06 07:12:23,884 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-06 07:12:23,885 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 07:12:23,885 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [185196514] [2022-04-06 07:12:23,885 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 07:12:23,885 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [900334107] [2022-04-06 07:12:23,885 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [900334107] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 07:12:23,886 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 07:12:23,886 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 07:12:23,886 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [342392609] [2022-04-06 07:12:23,886 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 07:12:23,886 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-06 07:12:23,886 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 07:12:23,887 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-06 07:12:23,887 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2022-04-06 07:12:23,887 INFO L87 Difference]: Start difference. First operand 102 states and 126 transitions. Second operand has 5 states, 5 states have (on average 4.8) internal successors, (24), 5 states have internal predecessors, (24), 5 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (16), 5 states have call predecessors, (16), 5 states have call successors, (16) [2022-04-06 07:12:23,937 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 07:12:23,937 INFO L93 Difference]: Finished difference Result 104 states and 127 transitions. [2022-04-06 07:12:23,938 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-06 07:12:23,938 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 4.8) internal successors, (24), 5 states have internal predecessors, (24), 5 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (16), 5 states have call predecessors, (16), 5 states have call successors, (16) Word has length 95 [2022-04-06 07:12:23,938 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 07:12:23,940 INFO L225 Difference]: With dead ends: 104 [2022-04-06 07:12:23,940 INFO L226 Difference]: Without dead ends: 104 [2022-04-06 07:12:23,941 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 94 GetRequests, 91 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2022-04-06 07:12:23,942 INFO L913 BasicCegarLoop]: 57 mSDtfsCounter, 9 mSDsluCounter, 64 mSDsCounter, 0 mSdLazyCounter, 34 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 121 SdHoareTripleChecker+Invalid, 41 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 34 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 07:12:23,942 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [14 Valid, 121 Invalid, 41 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 34 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 07:12:23,942 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 104 states. [2022-04-06 07:12:23,963 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 104 to 104. [2022-04-06 07:12:23,964 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 104 states, 61 states have (on average 1.1311475409836065) internal successors, (69), 64 states have internal predecessors, (69), 30 states have call successors, (30), 13 states have call predecessors, (30), 12 states have return successors, (28), 26 states have call predecessors, (28), 28 states have call successors, (28) [2022-04-06 07:12:23,965 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 104 states to 104 states and 127 transitions. [2022-04-06 07:12:23,965 INFO L78 Accepts]: Start accepts. Automaton has 104 states and 127 transitions. Word has length 95 [2022-04-06 07:12:23,966 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 07:12:23,966 INFO L478 AbstractCegarLoop]: Abstraction has 104 states and 127 transitions. [2022-04-06 07:12:23,967 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 4.8) internal successors, (24), 5 states have internal predecessors, (24), 5 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (16), 5 states have call predecessors, (16), 5 states have call successors, (16) [2022-04-06 07:12:23,967 INFO L276 IsEmpty]: Start isEmpty. Operand 104 states and 127 transitions. [2022-04-06 07:12:23,969 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 106 [2022-04-06 07:12:23,969 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 07:12:23,969 INFO L499 BasicCegarLoop]: trace histogram [14, 13, 13, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 07:12:23,998 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-04-06 07:12:24,193 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 07:12:24,194 INFO L403 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 07:12:24,194 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 07:12:24,194 INFO L85 PathProgramCache]: Analyzing trace with hash -317970408, now seen corresponding path program 3 times [2022-04-06 07:12:24,194 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 07:12:24,194 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [938076141] [2022-04-06 07:12:24,194 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 07:12:24,194 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 07:12:24,202 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 07:12:24,202 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1599212972] [2022-04-06 07:12:24,202 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-04-06 07:12:24,202 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 07:12:24,202 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 07:12:24,203 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-04-06 07:12:24,224 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-04-06 07:12:24,297 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2022-04-06 07:12:24,297 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 07:12:24,298 INFO L263 TraceCheckSpWp]: Trace formula consists of 194 conjuncts, 45 conjunts are in the unsatisfiable core [2022-04-06 07:12:24,300 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 07:12:24,977 INFO L134 CoverageAnalysis]: Checked inductivity of 374 backedges. 37 proven. 55 refuted. 0 times theorem prover too weak. 282 trivial. 0 not checked. [2022-04-06 07:12:24,977 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 07:13:18,616 INFO L134 CoverageAnalysis]: Checked inductivity of 374 backedges. 31 proven. 46 refuted. 9 times theorem prover too weak. 288 trivial. 0 not checked. [2022-04-06 07:13:18,616 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 07:13:18,616 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [938076141] [2022-04-06 07:13:18,616 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 07:13:18,616 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1599212972] [2022-04-06 07:13:18,617 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1599212972] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 07:13:18,617 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 07:13:18,617 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 13] total 23 [2022-04-06 07:13:18,617 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [355362438] [2022-04-06 07:13:18,617 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-06 07:13:18,617 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2022-04-06 07:13:18,617 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 07:13:18,617 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2022-04-06 07:13:18,618 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=85, Invalid=418, Unknown=3, NotChecked=0, Total=506 [2022-04-06 07:13:18,618 INFO L87 Difference]: Start difference. First operand 104 states and 127 transitions. Second operand has 23 states, 23 states have (on average 2.130434782608696) internal successors, (49), 20 states have internal predecessors, (49), 11 states have call successors, (33), 2 states have call predecessors, (33), 3 states have return successors, (31), 11 states have call predecessors, (31), 9 states have call successors, (31) [2022-04-06 07:14:36,337 WARN L232 SmtUtils]: Spent 1.25m on a formula simplification. DAG size of input: 196 DAG size of output: 46 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-06 07:14:38,350 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-06 07:14:39,731 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.36s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-06 07:14:41,649 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.90s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-06 07:14:43,621 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.93s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-06 07:14:45,995 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-06 07:14:50,657 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-06 07:16:32,210 WARN L232 SmtUtils]: Spent 1.57m on a formula simplification. DAG size of input: 181 DAG size of output: 110 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-06 07:16:51,214 WARN L232 SmtUtils]: Spent 12.28s on a formula simplification. DAG size of input: 85 DAG size of output: 29 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-06 07:17:07,196 WARN L232 SmtUtils]: Spent 13.37s on a formula simplification. DAG size of input: 84 DAG size of output: 27 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-06 07:17:10,542 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-06 07:17:14,880 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-06 07:17:17,225 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.48s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-06 07:17:21,038 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-06 07:17:22,578 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.42s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-06 07:17:23,192 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 07:17:23,193 INFO L93 Difference]: Finished difference Result 197 states and 255 transitions. [2022-04-06 07:17:23,193 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2022-04-06 07:17:23,194 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 23 states have (on average 2.130434782608696) internal successors, (49), 20 states have internal predecessors, (49), 11 states have call successors, (33), 2 states have call predecessors, (33), 3 states have return successors, (31), 11 states have call predecessors, (31), 9 states have call successors, (31) Word has length 105 [2022-04-06 07:17:23,194 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 07:17:23,195 INFO L225 Difference]: With dead ends: 197 [2022-04-06 07:17:23,195 INFO L226 Difference]: Without dead ends: 181 [2022-04-06 07:17:23,195 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 225 GetRequests, 184 SyntacticMatches, 4 SemanticMatches, 37 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 288 ImplicationChecksByTransitivity, 224.4s TimeCoverageRelationStatistics Valid=257, Invalid=1220, Unknown=5, NotChecked=0, Total=1482 [2022-04-06 07:17:23,195 INFO L913 BasicCegarLoop]: 50 mSDtfsCounter, 112 mSDsluCounter, 264 mSDsCounter, 0 mSdLazyCounter, 1354 mSolverCounterSat, 267 mSolverCounterUnsat, 6 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 35.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 124 SdHoareTripleChecker+Valid, 314 SdHoareTripleChecker+Invalid, 1627 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 267 IncrementalHoareTripleChecker+Valid, 1354 IncrementalHoareTripleChecker+Invalid, 6 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 35.4s IncrementalHoareTripleChecker+Time [2022-04-06 07:17:23,196 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [124 Valid, 314 Invalid, 1627 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [267 Valid, 1354 Invalid, 6 Unknown, 0 Unchecked, 35.4s Time] [2022-04-06 07:17:23,216 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 181 states. [2022-04-06 07:17:23,220 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 181 to 161. [2022-04-06 07:17:23,221 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 161 states, 96 states have (on average 1.125) internal successors, (108), 103 states have internal predecessors, (108), 46 states have call successors, (46), 19 states have call predecessors, (46), 18 states have return successors, (44), 38 states have call predecessors, (44), 44 states have call successors, (44) [2022-04-06 07:17:23,221 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 161 states to 161 states and 198 transitions. [2022-04-06 07:17:23,221 INFO L78 Accepts]: Start accepts. Automaton has 161 states and 198 transitions. Word has length 105 [2022-04-06 07:17:23,222 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 07:17:23,222 INFO L478 AbstractCegarLoop]: Abstraction has 161 states and 198 transitions. [2022-04-06 07:17:23,222 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 23 states have (on average 2.130434782608696) internal successors, (49), 20 states have internal predecessors, (49), 11 states have call successors, (33), 2 states have call predecessors, (33), 3 states have return successors, (31), 11 states have call predecessors, (31), 9 states have call successors, (31) [2022-04-06 07:17:23,222 INFO L276 IsEmpty]: Start isEmpty. Operand 161 states and 198 transitions. [2022-04-06 07:17:23,223 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 117 [2022-04-06 07:17:23,223 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 07:17:23,223 INFO L499 BasicCegarLoop]: trace histogram [16, 15, 15, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 07:17:23,257 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2022-04-06 07:17:23,436 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,SelfDestructingSolverStorable12 [2022-04-06 07:17:23,437 INFO L403 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 07:17:23,438 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 07:17:23,438 INFO L85 PathProgramCache]: Analyzing trace with hash -1498631042, now seen corresponding path program 2 times [2022-04-06 07:17:23,438 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 07:17:23,438 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1870099205] [2022-04-06 07:17:23,438 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 07:17:23,438 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 07:17:23,453 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 07:17:23,453 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [842147800] [2022-04-06 07:17:23,453 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 07:17:23,453 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 07:17:23,453 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 07:17:23,466 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-04-06 07:17:23,467 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-04-06 07:17:23,597 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 07:17:23,597 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 07:17:23,599 INFO L263 TraceCheckSpWp]: Trace formula consists of 261 conjuncts, 49 conjunts are in the unsatisfiable core [2022-04-06 07:17:23,602 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 07:17:24,478 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-04-06 07:17:27,393 INFO L134 CoverageAnalysis]: Checked inductivity of 490 backedges. 106 proven. 30 refuted. 0 times theorem prover too weak. 354 trivial. 0 not checked. [2022-04-06 07:17:27,393 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 07:17:28,645 INFO L134 CoverageAnalysis]: Checked inductivity of 490 backedges. 110 proven. 2 refuted. 0 times theorem prover too weak. 378 trivial. 0 not checked. [2022-04-06 07:17:28,645 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 07:17:28,645 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1870099205] [2022-04-06 07:17:28,645 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 07:17:28,645 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [842147800] [2022-04-06 07:17:28,646 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [842147800] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 07:17:28,646 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 07:17:28,646 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 9] total 20 [2022-04-06 07:17:28,646 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1151351812] [2022-04-06 07:17:28,646 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-06 07:17:28,646 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2022-04-06 07:17:28,646 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 07:17:28,646 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2022-04-06 07:17:28,647 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=78, Invalid=302, Unknown=0, NotChecked=0, Total=380 [2022-04-06 07:17:28,647 INFO L87 Difference]: Start difference. First operand 161 states and 198 transitions. Second operand has 20 states, 17 states have (on average 2.411764705882353) internal successors, (41), 16 states have internal predecessors, (41), 10 states have call successors, (28), 2 states have call predecessors, (28), 2 states have return successors, (26), 10 states have call predecessors, (26), 8 states have call successors, (26) [2022-04-06 07:17:30,608 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 07:17:30,608 INFO L93 Difference]: Finished difference Result 191 states and 229 transitions. [2022-04-06 07:17:30,609 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2022-04-06 07:17:30,609 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 17 states have (on average 2.411764705882353) internal successors, (41), 16 states have internal predecessors, (41), 10 states have call successors, (28), 2 states have call predecessors, (28), 2 states have return successors, (26), 10 states have call predecessors, (26), 8 states have call successors, (26) Word has length 116 [2022-04-06 07:17:30,609 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 07:17:30,610 INFO L225 Difference]: With dead ends: 191 [2022-04-06 07:17:30,610 INFO L226 Difference]: Without dead ends: 163 [2022-04-06 07:17:30,610 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 233 GetRequests, 211 SyntacticMatches, 2 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 60 ImplicationChecksByTransitivity, 2.8s TimeCoverageRelationStatistics Valid=91, Invalid=371, Unknown=0, NotChecked=0, Total=462 [2022-04-06 07:17:30,611 INFO L913 BasicCegarLoop]: 46 mSDtfsCounter, 45 mSDsluCounter, 133 mSDsCounter, 0 mSdLazyCounter, 524 mSolverCounterSat, 107 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 58 SdHoareTripleChecker+Valid, 179 SdHoareTripleChecker+Invalid, 631 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 107 IncrementalHoareTripleChecker+Valid, 524 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.8s IncrementalHoareTripleChecker+Time [2022-04-06 07:17:30,611 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [58 Valid, 179 Invalid, 631 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [107 Valid, 524 Invalid, 0 Unknown, 0 Unchecked, 1.8s Time] [2022-04-06 07:17:30,611 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 163 states. [2022-04-06 07:17:30,614 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 163 to 142. [2022-04-06 07:17:30,614 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 142 states, 87 states have (on average 1.103448275862069) internal successors, (96), 92 states have internal predecessors, (96), 35 states have call successors, (35), 20 states have call predecessors, (35), 19 states have return successors, (33), 29 states have call predecessors, (33), 33 states have call successors, (33) [2022-04-06 07:17:30,615 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 142 states to 142 states and 164 transitions. [2022-04-06 07:17:30,615 INFO L78 Accepts]: Start accepts. Automaton has 142 states and 164 transitions. Word has length 116 [2022-04-06 07:17:30,615 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 07:17:30,615 INFO L478 AbstractCegarLoop]: Abstraction has 142 states and 164 transitions. [2022-04-06 07:17:30,615 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 17 states have (on average 2.411764705882353) internal successors, (41), 16 states have internal predecessors, (41), 10 states have call successors, (28), 2 states have call predecessors, (28), 2 states have return successors, (26), 10 states have call predecessors, (26), 8 states have call successors, (26) [2022-04-06 07:17:30,615 INFO L276 IsEmpty]: Start isEmpty. Operand 142 states and 164 transitions. [2022-04-06 07:17:30,616 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 136 [2022-04-06 07:17:30,616 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 07:17:30,616 INFO L499 BasicCegarLoop]: trace histogram [19, 18, 18, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 07:17:30,635 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-04-06 07:17:30,825 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,SelfDestructingSolverStorable13 [2022-04-06 07:17:30,825 INFO L403 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 07:17:30,825 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 07:17:30,825 INFO L85 PathProgramCache]: Analyzing trace with hash -715358301, now seen corresponding path program 4 times [2022-04-06 07:17:30,825 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 07:17:30,825 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [21673483] [2022-04-06 07:17:30,825 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 07:17:30,825 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 07:17:30,839 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 07:17:30,839 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [592209009] [2022-04-06 07:17:30,839 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-04-06 07:17:30,839 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 07:17:30,839 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 07:17:30,844 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-04-06 07:17:30,845 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-04-06 07:17:30,905 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-04-06 07:17:30,905 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 07:17:30,907 INFO L263 TraceCheckSpWp]: Trace formula consists of 303 conjuncts, 51 conjunts are in the unsatisfiable core [2022-04-06 07:17:30,909 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 07:17:31,786 INFO L134 CoverageAnalysis]: Checked inductivity of 711 backedges. 36 proven. 51 refuted. 0 times theorem prover too weak. 624 trivial. 0 not checked. [2022-04-06 07:17:31,787 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 07:19:46,147 WARN L232 SmtUtils]: Spent 30.03s on a formula simplification that was a NOOP. DAG size: 451 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-06 07:21:30,502 WARN L232 SmtUtils]: Spent 7.63s on a formula simplification that was a NOOP. DAG size: 119 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-06 07:22:11,347 INFO L134 CoverageAnalysis]: Checked inductivity of 711 backedges. 36 proven. 51 refuted. 0 times theorem prover too weak. 624 trivial. 0 not checked. [2022-04-06 07:22:11,347 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 07:22:11,347 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [21673483] [2022-04-06 07:22:11,347 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 07:22:11,347 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [592209009] [2022-04-06 07:22:11,347 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [592209009] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 07:22:11,347 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 07:22:11,347 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 15] total 26 [2022-04-06 07:22:11,348 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2086676496] [2022-04-06 07:22:11,348 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-06 07:22:11,348 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2022-04-06 07:22:11,348 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 07:22:11,348 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2022-04-06 07:22:11,349 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=131, Invalid=517, Unknown=2, NotChecked=0, Total=650 [2022-04-06 07:22:11,349 INFO L87 Difference]: Start difference. First operand 142 states and 164 transitions. Second operand has 26 states, 26 states have (on average 1.9615384615384615) internal successors, (51), 25 states have internal predecessors, (51), 17 states have call successors, (43), 2 states have call predecessors, (43), 1 states have return successors, (40), 15 states have call predecessors, (40), 15 states have call successors, (40)