/usr/bin/java -Xmx8000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata ./data --core.log.level.for.class de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN -tc ../../../trunk/examples/toolchains/AutomizerCTransformed.xml -s ../../../trunk/examples/settings/automizer/LoopAccelerationJordanC.epf -i ../../../trunk/examples/svcomp/nla-digbench-scaling/ps4-ll_unwindbound50.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-7390193 [2022-04-05 03:49:11,112 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-04-05 03:49:11,114 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-04-05 03:49:11,174 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-04-05 03:49:11,174 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-04-05 03:49:11,176 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-04-05 03:49:11,178 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-04-05 03:49:11,180 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-04-05 03:49:11,181 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-04-05 03:49:11,185 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-04-05 03:49:11,186 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-04-05 03:49:11,187 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-04-05 03:49:11,187 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-04-05 03:49:11,189 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-04-05 03:49:11,190 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-04-05 03:49:11,192 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-04-05 03:49:11,193 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-04-05 03:49:11,194 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-04-05 03:49:11,196 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-04-05 03:49:11,200 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-04-05 03:49:11,202 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-04-05 03:49:11,203 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-04-05 03:49:11,204 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-04-05 03:49:11,204 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-04-05 03:49:11,206 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-04-05 03:49:11,211 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-04-05 03:49:11,211 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-04-05 03:49:11,212 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-04-05 03:49:11,212 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-04-05 03:49:11,213 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-04-05 03:49:11,214 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-04-05 03:49:11,214 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-04-05 03:49:11,215 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-04-05 03:49:11,216 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-04-05 03:49:11,216 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-04-05 03:49:11,217 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-04-05 03:49:11,217 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-04-05 03:49:11,218 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-04-05 03:49:11,218 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-04-05 03:49:11,218 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-04-05 03:49:11,219 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-04-05 03:49:11,220 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-04-05 03:49:11,221 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/LoopAccelerationJordanC.epf [2022-04-05 03:49:11,232 INFO L113 SettingsManager]: Loading preferences was successful [2022-04-05 03:49:11,232 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-04-05 03:49:11,233 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-04-05 03:49:11,233 INFO L138 SettingsManager]: * sizeof long=4 [2022-04-05 03:49:11,233 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-04-05 03:49:11,234 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-04-05 03:49:11,234 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-04-05 03:49:11,234 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-04-05 03:49:11,234 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-04-05 03:49:11,235 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-04-05 03:49:11,235 INFO L138 SettingsManager]: * sizeof long double=12 [2022-04-05 03:49:11,235 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-04-05 03:49:11,235 INFO L138 SettingsManager]: * Use constant arrays=true [2022-04-05 03:49:11,236 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-04-05 03:49:11,236 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-04-05 03:49:11,236 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-04-05 03:49:11,236 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-04-05 03:49:11,236 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-04-05 03:49:11,236 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-05 03:49:11,237 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-04-05 03:49:11,237 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-04-05 03:49:11,238 INFO L136 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2022-04-05 03:49:11,238 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-05 03:49:11,475 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-04-05 03:49:11,506 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-04-05 03:49:11,508 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-04-05 03:49:11,508 INFO L271 PluginConnector]: Initializing CDTParser... [2022-04-05 03:49:11,510 INFO L275 PluginConnector]: CDTParser initialized [2022-04-05 03:49:11,511 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/ps4-ll_unwindbound50.c [2022-04-05 03:49:11,558 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/fd93e29cc/88db8d51f6914a7ebfa469dc09bead3a/FLAGd9e5daebe [2022-04-05 03:49:11,951 INFO L306 CDTParser]: Found 1 translation units. [2022-04-05 03:49:11,952 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/ps4-ll_unwindbound50.c [2022-04-05 03:49:11,959 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/fd93e29cc/88db8d51f6914a7ebfa469dc09bead3a/FLAGd9e5daebe [2022-04-05 03:49:12,362 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/fd93e29cc/88db8d51f6914a7ebfa469dc09bead3a [2022-04-05 03:49:12,364 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-04-05 03:49:12,365 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2022-04-05 03:49:12,368 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-04-05 03:49:12,368 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-04-05 03:49:12,374 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-04-05 03:49:12,375 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 05.04 03:49:12" (1/1) ... [2022-04-05 03:49:12,376 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@e33110d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 03:49:12, skipping insertion in model container [2022-04-05 03:49:12,376 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 05.04 03:49:12" (1/1) ... [2022-04-05 03:49:12,382 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-04-05 03:49:12,394 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-04-05 03:49:12,544 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/ps4-ll_unwindbound50.c[458,471] [2022-04-05 03:49:12,557 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-05 03:49:12,563 INFO L203 MainTranslator]: Completed pre-run [2022-04-05 03:49:12,571 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/ps4-ll_unwindbound50.c[458,471] [2022-04-05 03:49:12,575 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-05 03:49:12,584 INFO L208 MainTranslator]: Completed translation [2022-04-05 03:49:12,585 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 03:49:12 WrapperNode [2022-04-05 03:49:12,585 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-04-05 03:49:12,586 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-04-05 03:49:12,586 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-04-05 03:49:12,586 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-04-05 03:49:12,594 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 03:49:12" (1/1) ... [2022-04-05 03:49:12,594 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 03:49:12" (1/1) ... [2022-04-05 03:49:12,599 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 03:49:12" (1/1) ... [2022-04-05 03:49:12,599 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 03:49:12" (1/1) ... [2022-04-05 03:49:12,603 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 03:49:12" (1/1) ... [2022-04-05 03:49:12,605 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 03:49:12" (1/1) ... [2022-04-05 03:49:12,606 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 03:49:12" (1/1) ... [2022-04-05 03:49:12,607 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-04-05 03:49:12,608 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-04-05 03:49:12,608 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-04-05 03:49:12,608 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-04-05 03:49:12,609 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 03:49:12" (1/1) ... [2022-04-05 03:49:12,617 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-05 03:49:12,625 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 03:49:12,638 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-05 03:49:12,645 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-05 03:49:12,668 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-04-05 03:49:12,669 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-04-05 03:49:12,669 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-04-05 03:49:12,669 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-04-05 03:49:12,669 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-04-05 03:49:12,669 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-04-05 03:49:12,669 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-04-05 03:49:12,669 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-04-05 03:49:12,669 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-04-05 03:49:12,669 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-04-05 03:49:12,670 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_short [2022-04-05 03:49:12,670 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-04-05 03:49:12,670 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-04-05 03:49:12,670 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-04-05 03:49:12,670 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-04-05 03:49:12,670 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-04-05 03:49:12,670 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-04-05 03:49:12,670 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-04-05 03:49:12,670 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-04-05 03:49:12,671 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-04-05 03:49:12,720 INFO L234 CfgBuilder]: Building ICFG [2022-04-05 03:49:12,721 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-04-05 03:49:12,893 INFO L275 CfgBuilder]: Performing block encoding [2022-04-05 03:49:12,898 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-04-05 03:49:12,898 INFO L299 CfgBuilder]: Removed 1 assume(true) statements. [2022-04-05 03:49:12,899 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 05.04 03:49:12 BoogieIcfgContainer [2022-04-05 03:49:12,900 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-04-05 03:49:12,900 INFO L113 PluginConnector]: ------------------------IcfgTransformer---------------------------- [2022-04-05 03:49:12,900 INFO L271 PluginConnector]: Initializing IcfgTransformer... [2022-04-05 03:49:12,901 INFO L275 PluginConnector]: IcfgTransformer initialized [2022-04-05 03:49:12,904 INFO L185 PluginConnector]: Executing the observer IcfgTransformationObserver from plugin IcfgTransformer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 05.04 03:49:12" (1/1) ... [2022-04-05 03:49:12,905 INFO L168 ansformationObserver]: Applying ICFG transformation LOOP_ACCELERATION_JORDAN [2022-04-05 03:49:12,917 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 05.04 03:49:12 BasicIcfg [2022-04-05 03:49:12,917 INFO L132 PluginConnector]: ------------------------ END IcfgTransformer---------------------------- [2022-04-05 03:49:12,919 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-04-05 03:49:12,919 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-04-05 03:49:12,921 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-04-05 03:49:12,921 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 05.04 03:49:12" (1/4) ... [2022-04-05 03:49:12,922 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4fc126ff and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 05.04 03:49:12, skipping insertion in model container [2022-04-05 03:49:12,922 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 03:49:12" (2/4) ... [2022-04-05 03:49:12,922 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4fc126ff and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 05.04 03:49:12, skipping insertion in model container [2022-04-05 03:49:12,922 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 05.04 03:49:12" (3/4) ... [2022-04-05 03:49:12,922 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4fc126ff and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 05.04 03:49:12, skipping insertion in model container [2022-04-05 03:49:12,923 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 05.04 03:49:12" (4/4) ... [2022-04-05 03:49:12,923 INFO L111 eAbstractionObserver]: Analyzing ICFG ps4-ll_unwindbound50.cJordan [2022-04-05 03:49:12,927 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:false NWA Interpolation:ForwardPredicates Determinization: PREDICATE_ABSTRACTION [2022-04-05 03:49:12,928 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-04-05 03:49:12,960 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-04-05 03:49:12,966 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-05 03:49:12,966 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-04-05 03:49:12,976 INFO L276 IsEmpty]: Start isEmpty. Operand has 23 states, 13 states have (on average 1.3846153846153846) internal successors, (18), 14 states have internal predecessors, (18), 5 states have call successors, (5), 3 states have call predecessors, (5), 3 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-04-05 03:49:12,981 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2022-04-05 03:49:12,982 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 03:49:12,982 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 03:49:12,982 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 03:49:12,987 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 03:49:12,987 INFO L85 PathProgramCache]: Analyzing trace with hash 1984627219, now seen corresponding path program 1 times [2022-04-05 03:49:12,994 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 03:49:12,995 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [454990524] [2022-04-05 03:49:12,995 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 03:49:12,995 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 03:49:13,086 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 03:49:13,168 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-05 03:49:13,177 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 03:49:13,191 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-05 03:49:13,192 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 03:49:13,193 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [454990524] [2022-04-05 03:49:13,194 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [454990524] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-05 03:49:13,194 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-05 03:49:13,195 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-05 03:49:13,196 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1135594531] [2022-04-05 03:49:13,196 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-05 03:49:13,200 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-04-05 03:49:13,201 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 03:49:13,228 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-04-05 03:49:13,230 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-05 03:49:13,231 INFO L87 Difference]: Start difference. First operand has 23 states, 13 states have (on average 1.3846153846153846) internal successors, (18), 14 states have internal predecessors, (18), 5 states have call successors, (5), 3 states have call predecessors, (5), 3 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) Second operand has 3 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 2 states have internal predecessors, (7), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-05 03:49:13,297 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 03:49:13,298 INFO L93 Difference]: Finished difference Result 24 states and 27 transitions. [2022-04-05 03:49:13,300 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-04-05 03:49:13,301 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 2 states have internal predecessors, (7), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 11 [2022-04-05 03:49:13,301 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 03:49:13,306 INFO L225 Difference]: With dead ends: 24 [2022-04-05 03:49:13,306 INFO L226 Difference]: Without dead ends: 19 [2022-04-05 03:49:13,308 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 3 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-05 03:49:13,313 INFO L913 BasicCegarLoop]: 25 mSDtfsCounter, 6 mSDsluCounter, 4 mSDsCounter, 0 mSdLazyCounter, 12 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 29 SdHoareTripleChecker+Invalid, 16 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 12 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-05 03:49:13,314 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [6 Valid, 29 Invalid, 16 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 12 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-05 03:49:13,328 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 19 states. [2022-04-05 03:49:13,343 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 19 to 18. [2022-04-05 03:49:13,344 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 18 states, 10 states have (on average 1.3) internal successors, (13), 11 states have internal predecessors, (13), 5 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-04-05 03:49:13,346 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 18 states to 18 states and 21 transitions. [2022-04-05 03:49:13,346 INFO L78 Accepts]: Start accepts. Automaton has 18 states and 21 transitions. Word has length 11 [2022-04-05 03:49:13,347 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 03:49:13,347 INFO L478 AbstractCegarLoop]: Abstraction has 18 states and 21 transitions. [2022-04-05 03:49:13,348 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 2 states have internal predecessors, (7), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-05 03:49:13,348 INFO L276 IsEmpty]: Start isEmpty. Operand 18 states and 21 transitions. [2022-04-05 03:49:13,349 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2022-04-05 03:49:13,349 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 03:49:13,349 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 03:49:13,349 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-04-05 03:49:13,349 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 03:49:13,352 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 03:49:13,352 INFO L85 PathProgramCache]: Analyzing trace with hash 1423332195, now seen corresponding path program 1 times [2022-04-05 03:49:13,352 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 03:49:13,352 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1590958505] [2022-04-05 03:49:13,352 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 03:49:13,353 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 03:49:13,380 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 03:49:13,380 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1465359039] [2022-04-05 03:49:13,380 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 03:49:13,380 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 03:49:13,381 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 03:49:13,385 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-05 03:49:13,386 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-05 03:49:13,444 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 03:49:13,446 INFO L263 TraceCheckSpWp]: Trace formula consists of 71 conjuncts, 5 conjunts are in the unsatisfiable core [2022-04-05 03:49:13,450 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 03:49:13,536 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-05 03:49:13,536 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-05 03:49:13,536 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 03:49:13,537 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1590958505] [2022-04-05 03:49:13,537 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 03:49:13,537 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1465359039] [2022-04-05 03:49:13,540 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1465359039] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-05 03:49:13,541 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-05 03:49:13,541 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-04-05 03:49:13,541 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2009931381] [2022-04-05 03:49:13,542 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-05 03:49:13,543 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2022-04-05 03:49:13,543 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 03:49:13,543 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2022-04-05 03:49:13,544 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-04-05 03:49:13,544 INFO L87 Difference]: Start difference. First operand 18 states and 21 transitions. Second operand has 4 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-05 03:49:13,559 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 03:49:13,559 INFO L93 Difference]: Finished difference Result 20 states and 23 transitions. [2022-04-05 03:49:13,560 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2022-04-05 03:49:13,560 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 12 [2022-04-05 03:49:13,560 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 03:49:13,561 INFO L225 Difference]: With dead ends: 20 [2022-04-05 03:49:13,562 INFO L226 Difference]: Without dead ends: 20 [2022-04-05 03:49:13,563 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 9 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-04-05 03:49:13,566 INFO L913 BasicCegarLoop]: 19 mSDtfsCounter, 0 mSDsluCounter, 32 mSDsCounter, 0 mSdLazyCounter, 7 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 51 SdHoareTripleChecker+Invalid, 7 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 7 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-05 03:49:13,567 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [0 Valid, 51 Invalid, 7 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 7 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-05 03:49:13,574 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 20 states. [2022-04-05 03:49:13,578 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 20 to 20. [2022-04-05 03:49:13,578 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 20 states, 12 states have (on average 1.25) internal successors, (15), 13 states have internal predecessors, (15), 5 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-04-05 03:49:13,580 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 23 transitions. [2022-04-05 03:49:13,581 INFO L78 Accepts]: Start accepts. Automaton has 20 states and 23 transitions. Word has length 12 [2022-04-05 03:49:13,581 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 03:49:13,581 INFO L478 AbstractCegarLoop]: Abstraction has 20 states and 23 transitions. [2022-04-05 03:49:13,581 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-05 03:49:13,581 INFO L276 IsEmpty]: Start isEmpty. Operand 20 states and 23 transitions. [2022-04-05 03:49:13,581 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2022-04-05 03:49:13,582 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 03:49:13,582 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 03:49:13,611 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-05 03:49:13,804 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 03:49:13,804 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 03:49:13,805 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 03:49:13,805 INFO L85 PathProgramCache]: Analyzing trace with hash 1424404671, now seen corresponding path program 1 times [2022-04-05 03:49:13,805 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 03:49:13,805 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [378415459] [2022-04-05 03:49:13,805 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 03:49:13,806 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 03:49:13,815 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 03:49:13,816 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1035013971] [2022-04-05 03:49:13,816 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 03:49:13,816 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 03:49:13,816 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 03:49:13,817 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-05 03:49:13,842 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-05 03:49:13,860 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 03:49:13,862 INFO L263 TraceCheckSpWp]: Trace formula consists of 71 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-05 03:49:13,864 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 03:49:13,957 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-05 03:49:13,957 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-05 03:49:13,959 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 03:49:13,959 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [378415459] [2022-04-05 03:49:13,959 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 03:49:13,959 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1035013971] [2022-04-05 03:49:13,960 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1035013971] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-05 03:49:13,960 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-05 03:49:13,960 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-05 03:49:13,960 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [413223756] [2022-04-05 03:49:13,960 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-05 03:49:13,961 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-05 03:49:13,961 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 03:49:13,962 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-05 03:49:13,962 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-05 03:49:13,962 INFO L87 Difference]: Start difference. First operand 20 states and 23 transitions. Second operand has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-05 03:49:14,020 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 03:49:14,020 INFO L93 Difference]: Finished difference Result 28 states and 33 transitions. [2022-04-05 03:49:14,020 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-05 03:49:14,021 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 12 [2022-04-05 03:49:14,021 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 03:49:14,022 INFO L225 Difference]: With dead ends: 28 [2022-04-05 03:49:14,022 INFO L226 Difference]: Without dead ends: 26 [2022-04-05 03:49:14,023 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 12 GetRequests, 8 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-05 03:49:14,025 INFO L913 BasicCegarLoop]: 19 mSDtfsCounter, 6 mSDsluCounter, 45 mSDsCounter, 0 mSdLazyCounter, 28 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 64 SdHoareTripleChecker+Invalid, 30 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 28 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-05 03:49:14,027 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [8 Valid, 64 Invalid, 30 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 28 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-05 03:49:14,028 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 26 states. [2022-04-05 03:49:14,036 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 26 to 26. [2022-04-05 03:49:14,036 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 26 states, 16 states have (on average 1.1875) internal successors, (19), 17 states have internal predecessors, (19), 6 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2022-04-05 03:49:14,038 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 29 transitions. [2022-04-05 03:49:14,038 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 29 transitions. Word has length 12 [2022-04-05 03:49:14,039 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 03:49:14,039 INFO L478 AbstractCegarLoop]: Abstraction has 26 states and 29 transitions. [2022-04-05 03:49:14,040 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-05 03:49:14,041 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 29 transitions. [2022-04-05 03:49:14,042 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2022-04-05 03:49:14,042 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 03:49:14,042 INFO L499 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 03:49:14,074 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-05 03:49:14,274 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2022-04-05 03:49:14,274 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 03:49:14,275 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 03:49:14,275 INFO L85 PathProgramCache]: Analyzing trace with hash -381498108, now seen corresponding path program 1 times [2022-04-05 03:49:14,275 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 03:49:14,275 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1226443862] [2022-04-05 03:49:14,275 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 03:49:14,275 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 03:49:14,288 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 03:49:14,289 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1692450247] [2022-04-05 03:49:14,289 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 03:49:14,289 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 03:49:14,289 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 03:49:14,296 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-05 03:49:14,299 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-05 03:49:14,334 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 03:49:14,336 INFO L263 TraceCheckSpWp]: Trace formula consists of 92 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-05 03:49:14,337 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 03:49:14,422 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-05 03:49:14,423 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 03:49:14,506 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-05 03:49:14,506 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 03:49:14,506 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1226443862] [2022-04-05 03:49:14,506 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 03:49:14,506 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1692450247] [2022-04-05 03:49:14,507 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1692450247] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-05 03:49:14,507 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-05 03:49:14,507 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 8 [2022-04-05 03:49:14,508 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [212422603] [2022-04-05 03:49:14,508 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-05 03:49:14,509 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-04-05 03:49:14,509 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 03:49:14,509 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-04-05 03:49:14,509 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=36, Unknown=0, NotChecked=0, Total=56 [2022-04-05 03:49:14,510 INFO L87 Difference]: Start difference. First operand 26 states and 29 transitions. Second operand has 8 states, 8 states have (on average 3.125) internal successors, (25), 8 states have internal predecessors, (25), 6 states have call successors, (6), 5 states have call predecessors, (6), 4 states have return successors, (4), 4 states have call predecessors, (4), 3 states have call successors, (4) [2022-04-05 03:49:14,606 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 03:49:14,607 INFO L93 Difference]: Finished difference Result 52 states and 59 transitions. [2022-04-05 03:49:14,607 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-04-05 03:49:14,607 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 3.125) internal successors, (25), 8 states have internal predecessors, (25), 6 states have call successors, (6), 5 states have call predecessors, (6), 4 states have return successors, (4), 4 states have call predecessors, (4), 3 states have call successors, (4) Word has length 20 [2022-04-05 03:49:14,608 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 03:49:14,609 INFO L225 Difference]: With dead ends: 52 [2022-04-05 03:49:14,609 INFO L226 Difference]: Without dead ends: 52 [2022-04-05 03:49:14,609 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 42 GetRequests, 33 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=40, Invalid=70, Unknown=0, NotChecked=0, Total=110 [2022-04-05 03:49:14,611 INFO L913 BasicCegarLoop]: 24 mSDtfsCounter, 39 mSDsluCounter, 62 mSDsCounter, 0 mSdLazyCounter, 34 mSolverCounterSat, 17 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 39 SdHoareTripleChecker+Valid, 86 SdHoareTripleChecker+Invalid, 51 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 17 IncrementalHoareTripleChecker+Valid, 34 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-05 03:49:14,612 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [39 Valid, 86 Invalid, 51 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [17 Valid, 34 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-05 03:49:14,613 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 52 states. [2022-04-05 03:49:14,625 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 52 to 48. [2022-04-05 03:49:14,626 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 48 states, 30 states have (on average 1.2333333333333334) internal successors, (37), 33 states have internal predecessors, (37), 12 states have call successors, (12), 6 states have call predecessors, (12), 5 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-05 03:49:14,629 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 57 transitions. [2022-04-05 03:49:14,629 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 57 transitions. Word has length 20 [2022-04-05 03:49:14,629 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 03:49:14,629 INFO L478 AbstractCegarLoop]: Abstraction has 48 states and 57 transitions. [2022-04-05 03:49:14,629 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 3.125) internal successors, (25), 8 states have internal predecessors, (25), 6 states have call successors, (6), 5 states have call predecessors, (6), 4 states have return successors, (4), 4 states have call predecessors, (4), 3 states have call successors, (4) [2022-04-05 03:49:14,630 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 57 transitions. [2022-04-05 03:49:14,631 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2022-04-05 03:49:14,634 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 03:49:14,634 INFO L499 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 03:49:14,657 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-05 03:49:14,851 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 03:49:14,852 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 03:49:14,852 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 03:49:14,852 INFO L85 PathProgramCache]: Analyzing trace with hash -380425632, now seen corresponding path program 1 times [2022-04-05 03:49:14,852 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 03:49:14,852 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [828542504] [2022-04-05 03:49:14,853 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 03:49:14,853 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 03:49:14,867 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 03:49:14,867 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [344800836] [2022-04-05 03:49:14,867 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 03:49:14,867 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 03:49:14,868 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 03:49:14,868 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-05 03:49:14,894 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-05 03:49:14,926 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 03:49:14,927 INFO L263 TraceCheckSpWp]: Trace formula consists of 92 conjuncts, 11 conjunts are in the unsatisfiable core [2022-04-05 03:49:14,929 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 03:49:15,058 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 2 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-05 03:49:15,058 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 03:49:15,299 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2022-04-05 03:49:15,300 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 03:49:15,300 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [828542504] [2022-04-05 03:49:15,300 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 03:49:15,300 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [344800836] [2022-04-05 03:49:15,300 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [344800836] provided 1 perfect and 1 imperfect interpolant sequences [2022-04-05 03:49:15,300 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-04-05 03:49:15,300 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2022-04-05 03:49:15,301 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1210757736] [2022-04-05 03:49:15,301 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-05 03:49:15,302 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-05 03:49:15,302 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 03:49:15,303 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-05 03:49:15,303 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2022-04-05 03:49:15,303 INFO L87 Difference]: Start difference. First operand 48 states and 57 transitions. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-05 03:49:15,338 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 03:49:15,338 INFO L93 Difference]: Finished difference Result 60 states and 66 transitions. [2022-04-05 03:49:15,339 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-05 03:49:15,339 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 20 [2022-04-05 03:49:15,339 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 03:49:15,340 INFO L225 Difference]: With dead ends: 60 [2022-04-05 03:49:15,340 INFO L226 Difference]: Without dead ends: 51 [2022-04-05 03:49:15,340 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 40 GetRequests, 32 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2022-04-05 03:49:15,341 INFO L913 BasicCegarLoop]: 17 mSDtfsCounter, 7 mSDsluCounter, 36 mSDsCounter, 0 mSdLazyCounter, 21 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 53 SdHoareTripleChecker+Invalid, 22 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 21 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-05 03:49:15,341 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [8 Valid, 53 Invalid, 22 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 21 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-05 03:49:15,341 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2022-04-05 03:49:15,344 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 45. [2022-04-05 03:49:15,344 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 45 states, 32 states have (on average 1.125) internal successors, (36), 32 states have internal predecessors, (36), 7 states have call successors, (7), 7 states have call predecessors, (7), 5 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-04-05 03:49:15,345 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 48 transitions. [2022-04-05 03:49:15,345 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 48 transitions. Word has length 20 [2022-04-05 03:49:15,345 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 03:49:15,346 INFO L478 AbstractCegarLoop]: Abstraction has 45 states and 48 transitions. [2022-04-05 03:49:15,346 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-05 03:49:15,346 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 48 transitions. [2022-04-05 03:49:15,346 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2022-04-05 03:49:15,346 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 03:49:15,347 INFO L499 BasicCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 03:49:15,363 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-05 03:49:15,547 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 03:49:15,547 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 03:49:15,548 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 03:49:15,548 INFO L85 PathProgramCache]: Analyzing trace with hash 1647871298, now seen corresponding path program 1 times [2022-04-05 03:49:15,548 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 03:49:15,548 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1632670652] [2022-04-05 03:49:15,548 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 03:49:15,548 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 03:49:15,556 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 03:49:15,557 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [887126301] [2022-04-05 03:49:15,557 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 03:49:15,557 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 03:49:15,557 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 03:49:15,558 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-05 03:49:15,578 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-05 03:49:15,605 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 03:49:15,607 INFO L263 TraceCheckSpWp]: Trace formula consists of 102 conjuncts, 19 conjunts are in the unsatisfiable core [2022-04-05 03:49:15,609 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 03:49:15,896 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 6 proven. 5 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2022-04-05 03:49:15,896 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 03:49:33,479 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 03:49:33,479 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1632670652] [2022-04-05 03:49:33,479 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 03:49:33,479 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [887126301] [2022-04-05 03:49:33,479 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [887126301] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-05 03:49:33,480 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-05 03:49:33,480 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2022-04-05 03:49:33,480 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1549435811] [2022-04-05 03:49:33,480 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-04-05 03:49:33,480 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-04-05 03:49:33,480 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 03:49:33,481 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-04-05 03:49:33,481 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=46, Invalid=164, Unknown=0, NotChecked=0, Total=210 [2022-04-05 03:49:33,481 INFO L87 Difference]: Start difference. First operand 45 states and 48 transitions. Second operand has 10 states, 9 states have (on average 2.0) internal successors, (18), 8 states have internal predecessors, (18), 4 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-04-05 03:49:33,599 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 03:49:33,599 INFO L93 Difference]: Finished difference Result 48 states and 50 transitions. [2022-04-05 03:49:33,600 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-04-05 03:49:33,600 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 9 states have (on average 2.0) internal successors, (18), 8 states have internal predecessors, (18), 4 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Word has length 26 [2022-04-05 03:49:33,600 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 03:49:33,601 INFO L225 Difference]: With dead ends: 48 [2022-04-05 03:49:33,601 INFO L226 Difference]: Without dead ends: 45 [2022-04-05 03:49:33,601 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 42 GetRequests, 25 SyntacticMatches, 1 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 27 ImplicationChecksByTransitivity, 13.4s TimeCoverageRelationStatistics Valid=67, Invalid=239, Unknown=0, NotChecked=0, Total=306 [2022-04-05 03:49:33,601 INFO L913 BasicCegarLoop]: 17 mSDtfsCounter, 9 mSDsluCounter, 84 mSDsCounter, 0 mSdLazyCounter, 88 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 101 SdHoareTripleChecker+Invalid, 90 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 88 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-05 03:49:33,602 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [10 Valid, 101 Invalid, 90 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 88 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-05 03:49:33,602 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2022-04-05 03:49:33,604 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 45. [2022-04-05 03:49:33,605 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 45 states, 32 states have (on average 1.09375) internal successors, (35), 32 states have internal predecessors, (35), 7 states have call successors, (7), 7 states have call predecessors, (7), 5 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-04-05 03:49:33,605 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 47 transitions. [2022-04-05 03:49:33,605 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 47 transitions. Word has length 26 [2022-04-05 03:49:33,606 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 03:49:33,606 INFO L478 AbstractCegarLoop]: Abstraction has 45 states and 47 transitions. [2022-04-05 03:49:33,606 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 9 states have (on average 2.0) internal successors, (18), 8 states have internal predecessors, (18), 4 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-04-05 03:49:33,606 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 47 transitions. [2022-04-05 03:49:33,607 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2022-04-05 03:49:33,607 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 03:49:33,607 INFO L499 BasicCegarLoop]: trace histogram [4, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 03:49:33,626 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2022-04-05 03:49:33,815 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 03:49:33,816 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 03:49:33,816 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 03:49:33,816 INFO L85 PathProgramCache]: Analyzing trace with hash 31133987, now seen corresponding path program 2 times [2022-04-05 03:49:33,816 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 03:49:33,816 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1132349065] [2022-04-05 03:49:33,816 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 03:49:33,816 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 03:49:33,833 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 03:49:33,833 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1728327833] [2022-04-05 03:49:33,833 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-05 03:49:33,833 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 03:49:33,834 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 03:49:33,840 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-05 03:49:33,843 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-05 03:49:33,886 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-05 03:49:33,886 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-05 03:49:33,888 INFO L263 TraceCheckSpWp]: Trace formula consists of 123 conjuncts, 16 conjunts are in the unsatisfiable core [2022-04-05 03:49:33,890 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 03:49:34,075 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 6 proven. 12 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-04-05 03:49:34,075 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 03:49:34,210 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 03:49:34,210 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1132349065] [2022-04-05 03:49:34,210 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 03:49:34,211 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1728327833] [2022-04-05 03:49:34,211 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1728327833] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-05 03:49:34,211 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-05 03:49:34,211 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8] total 8 [2022-04-05 03:49:34,211 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1492287848] [2022-04-05 03:49:34,211 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-04-05 03:49:34,212 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-04-05 03:49:34,212 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 03:49:34,212 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-04-05 03:49:34,212 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=83, Unknown=0, NotChecked=0, Total=110 [2022-04-05 03:49:34,213 INFO L87 Difference]: Start difference. First operand 45 states and 47 transitions. Second operand has 8 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 7 states have internal predecessors, (18), 5 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2022-04-05 03:49:34,289 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 03:49:34,289 INFO L93 Difference]: Finished difference Result 48 states and 49 transitions. [2022-04-05 03:49:34,289 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-04-05 03:49:34,289 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 7 states have internal predecessors, (18), 5 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Word has length 34 [2022-04-05 03:49:34,290 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 03:49:34,290 INFO L225 Difference]: With dead ends: 48 [2022-04-05 03:49:34,290 INFO L226 Difference]: Without dead ends: 45 [2022-04-05 03:49:34,290 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 49 GetRequests, 37 SyntacticMatches, 1 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=37, Invalid=119, Unknown=0, NotChecked=0, Total=156 [2022-04-05 03:49:34,291 INFO L913 BasicCegarLoop]: 26 mSDtfsCounter, 2 mSDsluCounter, 106 mSDsCounter, 0 mSdLazyCounter, 71 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 132 SdHoareTripleChecker+Invalid, 71 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 71 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-05 03:49:34,291 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 132 Invalid, 71 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 71 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-05 03:49:34,292 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2022-04-05 03:49:34,294 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 45. [2022-04-05 03:49:34,294 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 45 states, 32 states have (on average 1.0625) internal successors, (34), 32 states have internal predecessors, (34), 7 states have call successors, (7), 7 states have call predecessors, (7), 5 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-04-05 03:49:34,295 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 46 transitions. [2022-04-05 03:49:34,295 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 46 transitions. Word has length 34 [2022-04-05 03:49:34,295 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 03:49:34,295 INFO L478 AbstractCegarLoop]: Abstraction has 45 states and 46 transitions. [2022-04-05 03:49:34,295 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 7 states have internal predecessors, (18), 5 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2022-04-05 03:49:34,295 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 46 transitions. [2022-04-05 03:49:34,296 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2022-04-05 03:49:34,296 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 03:49:34,296 INFO L499 BasicCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 03:49:34,322 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-05 03:49:34,497 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 03:49:34,497 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 03:49:34,497 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 03:49:34,498 INFO L85 PathProgramCache]: Analyzing trace with hash 1474833412, now seen corresponding path program 3 times [2022-04-05 03:49:34,498 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 03:49:34,498 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [412961698] [2022-04-05 03:49:34,498 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 03:49:34,498 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 03:49:34,528 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 03:49:34,529 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1217657496] [2022-04-05 03:49:34,529 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-04-05 03:49:34,529 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 03:49:34,529 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 03:49:34,536 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-05 03:49:34,559 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-05 03:49:34,621 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2022-04-05 03:49:34,622 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-05 03:49:34,623 INFO L263 TraceCheckSpWp]: Trace formula consists of 144 conjuncts, 20 conjunts are in the unsatisfiable core [2022-04-05 03:49:34,625 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 03:49:34,825 INFO L134 CoverageAnalysis]: Checked inductivity of 56 backedges. 8 proven. 24 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-04-05 03:49:34,826 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 03:49:35,008 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 03:49:35,009 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [412961698] [2022-04-05 03:49:35,009 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 03:49:35,009 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1217657496] [2022-04-05 03:49:35,009 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1217657496] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-05 03:49:35,009 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-05 03:49:35,009 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2022-04-05 03:49:35,010 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1135946016] [2022-04-05 03:49:35,010 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-04-05 03:49:35,010 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-04-05 03:49:35,010 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 03:49:35,010 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-04-05 03:49:35,010 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2022-04-05 03:49:35,011 INFO L87 Difference]: Start difference. First operand 45 states and 46 transitions. Second operand has 9 states, 8 states have (on average 2.625) internal successors, (21), 8 states have internal predecessors, (21), 6 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-04-05 03:49:35,117 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 03:49:35,117 INFO L93 Difference]: Finished difference Result 50 states and 52 transitions. [2022-04-05 03:49:35,118 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-04-05 03:49:35,118 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 2.625) internal successors, (21), 8 states have internal predecessors, (21), 6 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) Word has length 42 [2022-04-05 03:49:35,118 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 03:49:35,119 INFO L225 Difference]: With dead ends: 50 [2022-04-05 03:49:35,119 INFO L226 Difference]: Without dead ends: 47 [2022-04-05 03:49:35,119 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 57 GetRequests, 44 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=40, Invalid=142, Unknown=0, NotChecked=0, Total=182 [2022-04-05 03:49:35,119 INFO L913 BasicCegarLoop]: 30 mSDtfsCounter, 2 mSDsluCounter, 138 mSDsCounter, 0 mSdLazyCounter, 102 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 168 SdHoareTripleChecker+Invalid, 102 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 102 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-05 03:49:35,120 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 168 Invalid, 102 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 102 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-05 03:49:35,120 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2022-04-05 03:49:35,122 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 47. [2022-04-05 03:49:35,122 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 47 states, 33 states have (on average 1.0606060606060606) internal successors, (35), 33 states have internal predecessors, (35), 8 states have call successors, (8), 7 states have call predecessors, (8), 5 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-05 03:49:35,123 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 47 states to 47 states and 49 transitions. [2022-04-05 03:49:35,123 INFO L78 Accepts]: Start accepts. Automaton has 47 states and 49 transitions. Word has length 42 [2022-04-05 03:49:35,123 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 03:49:35,123 INFO L478 AbstractCegarLoop]: Abstraction has 47 states and 49 transitions. [2022-04-05 03:49:35,123 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 8 states have (on average 2.625) internal successors, (21), 8 states have internal predecessors, (21), 6 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-04-05 03:49:35,123 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 49 transitions. [2022-04-05 03:49:35,124 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2022-04-05 03:49:35,124 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 03:49:35,124 INFO L499 BasicCegarLoop]: trace histogram [5, 5, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 03:49:35,151 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-05 03:49:35,324 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 03:49:35,325 INFO L403 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 03:49:35,325 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 03:49:35,326 INFO L85 PathProgramCache]: Analyzing trace with hash 831591399, now seen corresponding path program 2 times [2022-04-05 03:49:35,326 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 03:49:35,326 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1198912621] [2022-04-05 03:49:35,326 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 03:49:35,326 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 03:49:35,334 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 03:49:35,334 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1188144163] [2022-04-05 03:49:35,334 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-05 03:49:35,334 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 03:49:35,335 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 03:49:35,340 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-05 03:49:35,342 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-05 03:49:35,389 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-05 03:49:35,389 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-05 03:49:35,390 INFO L263 TraceCheckSpWp]: Trace formula consists of 155 conjuncts, 13 conjunts are in the unsatisfiable core [2022-04-05 03:49:35,397 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 03:49:35,520 INFO L134 CoverageAnalysis]: Checked inductivity of 64 backedges. 8 proven. 56 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-05 03:49:35,521 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 03:49:35,675 INFO L134 CoverageAnalysis]: Checked inductivity of 64 backedges. 8 proven. 32 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-04-05 03:49:35,676 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 03:49:35,676 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1198912621] [2022-04-05 03:49:35,676 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 03:49:35,676 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1188144163] [2022-04-05 03:49:35,676 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1188144163] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-05 03:49:35,676 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-05 03:49:35,676 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 14 [2022-04-05 03:49:35,678 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1918892552] [2022-04-05 03:49:35,678 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-05 03:49:35,680 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2022-04-05 03:49:35,680 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 03:49:35,680 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2022-04-05 03:49:35,680 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=111, Unknown=0, NotChecked=0, Total=182 [2022-04-05 03:49:35,682 INFO L87 Difference]: Start difference. First operand 47 states and 49 transitions. Second operand has 14 states, 14 states have (on average 3.7142857142857144) internal successors, (52), 14 states have internal predecessors, (52), 12 states have call successors, (12), 8 states have call predecessors, (12), 7 states have return successors, (10), 10 states have call predecessors, (10), 9 states have call successors, (10) [2022-04-05 03:49:35,858 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 03:49:35,858 INFO L93 Difference]: Finished difference Result 118 states and 119 transitions. [2022-04-05 03:49:35,858 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2022-04-05 03:49:35,859 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 3.7142857142857144) internal successors, (52), 14 states have internal predecessors, (52), 12 states have call successors, (12), 8 states have call predecessors, (12), 7 states have return successors, (10), 10 states have call predecessors, (10), 9 states have call successors, (10) Word has length 44 [2022-04-05 03:49:35,859 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 03:49:35,860 INFO L225 Difference]: With dead ends: 118 [2022-04-05 03:49:35,860 INFO L226 Difference]: Without dead ends: 118 [2022-04-05 03:49:35,860 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 96 GetRequests, 75 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 55 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=184, Invalid=322, Unknown=0, NotChecked=0, Total=506 [2022-04-05 03:49:35,861 INFO L913 BasicCegarLoop]: 26 mSDtfsCounter, 108 mSDsluCounter, 88 mSDsCounter, 0 mSdLazyCounter, 62 mSolverCounterSat, 44 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 108 SdHoareTripleChecker+Valid, 114 SdHoareTripleChecker+Invalid, 106 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 44 IncrementalHoareTripleChecker+Valid, 62 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-05 03:49:35,861 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [108 Valid, 114 Invalid, 106 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [44 Valid, 62 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-05 03:49:35,861 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 118 states. [2022-04-05 03:49:35,865 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 118 to 93. [2022-04-05 03:49:35,866 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 93 states, 68 states have (on average 1.1029411764705883) internal successors, (75), 68 states have internal predecessors, (75), 13 states have call successors, (13), 13 states have call predecessors, (13), 11 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-05 03:49:35,866 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 99 transitions. [2022-04-05 03:49:35,866 INFO L78 Accepts]: Start accepts. Automaton has 93 states and 99 transitions. Word has length 44 [2022-04-05 03:49:35,867 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 03:49:35,867 INFO L478 AbstractCegarLoop]: Abstraction has 93 states and 99 transitions. [2022-04-05 03:49:35,869 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 3.7142857142857144) internal successors, (52), 14 states have internal predecessors, (52), 12 states have call successors, (12), 8 states have call predecessors, (12), 7 states have return successors, (10), 10 states have call predecessors, (10), 9 states have call successors, (10) [2022-04-05 03:49:35,870 INFO L276 IsEmpty]: Start isEmpty. Operand 93 states and 99 transitions. [2022-04-05 03:49:35,874 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2022-04-05 03:49:35,875 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 03:49:35,875 INFO L499 BasicCegarLoop]: trace histogram [6, 5, 5, 5, 5, 5, 5, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 03:49:35,897 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-05 03:49:36,091 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable8 [2022-04-05 03:49:36,091 INFO L403 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 03:49:36,091 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 03:49:36,092 INFO L85 PathProgramCache]: Analyzing trace with hash -1805593115, now seen corresponding path program 4 times [2022-04-05 03:49:36,092 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 03:49:36,092 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1961918219] [2022-04-05 03:49:36,092 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 03:49:36,092 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 03:49:36,124 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 03:49:36,124 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [159986295] [2022-04-05 03:49:36,124 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-04-05 03:49:36,125 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 03:49:36,125 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 03:49:36,132 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-05 03:49:36,133 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-05 03:49:36,217 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-04-05 03:49:36,217 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-05 03:49:36,218 INFO L263 TraceCheckSpWp]: Trace formula consists of 165 conjuncts, 24 conjunts are in the unsatisfiable core [2022-04-05 03:49:36,220 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 03:49:36,449 INFO L134 CoverageAnalysis]: Checked inductivity of 90 backedges. 10 proven. 40 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2022-04-05 03:49:36,450 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 03:49:36,644 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 03:49:36,645 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1961918219] [2022-04-05 03:49:36,645 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 03:49:36,645 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [159986295] [2022-04-05 03:49:36,645 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [159986295] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-05 03:49:36,645 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-05 03:49:36,645 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2022-04-05 03:49:36,645 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [517987791] [2022-04-05 03:49:36,646 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-04-05 03:49:36,646 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-04-05 03:49:36,646 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 03:49:36,646 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-04-05 03:49:36,647 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=123, Unknown=0, NotChecked=0, Total=156 [2022-04-05 03:49:36,647 INFO L87 Difference]: Start difference. First operand 93 states and 99 transitions. Second operand has 10 states, 9 states have (on average 2.6666666666666665) internal successors, (24), 9 states have internal predecessors, (24), 7 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-05 03:49:36,786 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 03:49:36,786 INFO L93 Difference]: Finished difference Result 96 states and 101 transitions. [2022-04-05 03:49:36,786 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-04-05 03:49:36,786 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 9 states have (on average 2.6666666666666665) internal successors, (24), 9 states have internal predecessors, (24), 7 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) Word has length 50 [2022-04-05 03:49:36,787 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 03:49:36,789 INFO L225 Difference]: With dead ends: 96 [2022-04-05 03:49:36,789 INFO L226 Difference]: Without dead ends: 93 [2022-04-05 03:49:36,789 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 65 GetRequests, 51 SyntacticMatches, 1 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=43, Invalid=167, Unknown=0, NotChecked=0, Total=210 [2022-04-05 03:49:36,789 INFO L913 BasicCegarLoop]: 34 mSDtfsCounter, 2 mSDsluCounter, 174 mSDsCounter, 0 mSdLazyCounter, 139 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 208 SdHoareTripleChecker+Invalid, 139 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 139 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-05 03:49:36,790 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 208 Invalid, 139 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 139 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-05 03:49:36,790 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 93 states. [2022-04-05 03:49:36,795 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 93 to 93. [2022-04-05 03:49:36,795 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 93 states, 68 states have (on average 1.088235294117647) internal successors, (74), 68 states have internal predecessors, (74), 13 states have call successors, (13), 13 states have call predecessors, (13), 11 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-05 03:49:36,796 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 98 transitions. [2022-04-05 03:49:36,796 INFO L78 Accepts]: Start accepts. Automaton has 93 states and 98 transitions. Word has length 50 [2022-04-05 03:49:36,796 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 03:49:36,796 INFO L478 AbstractCegarLoop]: Abstraction has 93 states and 98 transitions. [2022-04-05 03:49:36,796 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 9 states have (on average 2.6666666666666665) internal successors, (24), 9 states have internal predecessors, (24), 7 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-05 03:49:36,797 INFO L276 IsEmpty]: Start isEmpty. Operand 93 states and 98 transitions. [2022-04-05 03:49:36,797 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2022-04-05 03:49:36,797 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 03:49:36,797 INFO L499 BasicCegarLoop]: trace histogram [7, 6, 6, 6, 6, 6, 6, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 03:49:36,826 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-05 03:49:37,018 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2022-04-05 03:49:37,019 INFO L403 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 03:49:37,019 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 03:49:37,019 INFO L85 PathProgramCache]: Analyzing trace with hash 1447431878, now seen corresponding path program 5 times [2022-04-05 03:49:37,019 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 03:49:37,019 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [989494666] [2022-04-05 03:49:37,020 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 03:49:37,020 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 03:49:37,027 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 03:49:37,027 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1739820238] [2022-04-05 03:49:37,027 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2022-04-05 03:49:37,028 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 03:49:37,028 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 03:49:37,037 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-05 03:49:37,039 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-05 03:49:37,254 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2022-04-05 03:49:37,254 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-05 03:49:37,255 INFO L263 TraceCheckSpWp]: Trace formula consists of 186 conjuncts, 28 conjunts are in the unsatisfiable core [2022-04-05 03:49:37,257 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 03:49:37,514 INFO L134 CoverageAnalysis]: Checked inductivity of 132 backedges. 12 proven. 60 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2022-04-05 03:49:37,514 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 03:49:37,648 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 03:49:37,648 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [989494666] [2022-04-05 03:49:37,648 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 03:49:37,649 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1739820238] [2022-04-05 03:49:37,649 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1739820238] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-05 03:49:37,649 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-05 03:49:37,649 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11] total 11 [2022-04-05 03:49:37,649 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1774699262] [2022-04-05 03:49:37,649 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-04-05 03:49:37,649 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2022-04-05 03:49:37,650 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 03:49:37,650 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2022-04-05 03:49:37,650 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=36, Invalid=146, Unknown=0, NotChecked=0, Total=182 [2022-04-05 03:49:37,650 INFO L87 Difference]: Start difference. First operand 93 states and 98 transitions. Second operand has 11 states, 10 states have (on average 2.7) internal successors, (27), 10 states have internal predecessors, (27), 8 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-05 03:49:37,789 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 03:49:37,789 INFO L93 Difference]: Finished difference Result 96 states and 100 transitions. [2022-04-05 03:49:37,789 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2022-04-05 03:49:37,790 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 10 states have (on average 2.7) internal successors, (27), 10 states have internal predecessors, (27), 8 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Word has length 58 [2022-04-05 03:49:37,790 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 03:49:37,791 INFO L225 Difference]: With dead ends: 96 [2022-04-05 03:49:37,791 INFO L226 Difference]: Without dead ends: 93 [2022-04-05 03:49:37,791 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 73 GetRequests, 58 SyntacticMatches, 1 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=46, Invalid=194, Unknown=0, NotChecked=0, Total=240 [2022-04-05 03:49:37,792 INFO L913 BasicCegarLoop]: 38 mSDtfsCounter, 2 mSDsluCounter, 214 mSDsCounter, 0 mSdLazyCounter, 182 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 252 SdHoareTripleChecker+Invalid, 182 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 182 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-05 03:49:37,792 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 252 Invalid, 182 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 182 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-05 03:49:37,792 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 93 states. [2022-04-05 03:49:37,796 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 93 to 93. [2022-04-05 03:49:37,797 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 93 states, 68 states have (on average 1.0735294117647058) internal successors, (73), 68 states have internal predecessors, (73), 13 states have call successors, (13), 13 states have call predecessors, (13), 11 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-05 03:49:37,797 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 97 transitions. [2022-04-05 03:49:37,798 INFO L78 Accepts]: Start accepts. Automaton has 93 states and 97 transitions. Word has length 58 [2022-04-05 03:49:37,798 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 03:49:37,798 INFO L478 AbstractCegarLoop]: Abstraction has 93 states and 97 transitions. [2022-04-05 03:49:37,798 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 10 states have (on average 2.7) internal successors, (27), 10 states have internal predecessors, (27), 8 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-05 03:49:37,798 INFO L276 IsEmpty]: Start isEmpty. Operand 93 states and 97 transitions. [2022-04-05 03:49:37,799 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 67 [2022-04-05 03:49:37,799 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 03:49:37,799 INFO L499 BasicCegarLoop]: trace histogram [8, 7, 7, 7, 7, 7, 7, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 03:49:37,818 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-05 03:49:38,012 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2022-04-05 03:49:38,012 INFO L403 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 03:49:38,012 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 03:49:38,012 INFO L85 PathProgramCache]: Analyzing trace with hash -1416046937, now seen corresponding path program 6 times [2022-04-05 03:49:38,013 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 03:49:38,013 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [417315455] [2022-04-05 03:49:38,013 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 03:49:38,013 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 03:49:38,020 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 03:49:38,021 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1455239246] [2022-04-05 03:49:38,021 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-04-05 03:49:38,021 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 03:49:38,021 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 03:49:38,022 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-05 03:49:38,025 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-05 03:49:38,398 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2022-04-05 03:49:38,398 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-05 03:49:38,399 INFO L263 TraceCheckSpWp]: Trace formula consists of 207 conjuncts, 32 conjunts are in the unsatisfiable core [2022-04-05 03:49:38,401 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 03:49:38,641 INFO L134 CoverageAnalysis]: Checked inductivity of 182 backedges. 14 proven. 84 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2022-04-05 03:49:38,642 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 03:49:38,780 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 03:49:38,780 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [417315455] [2022-04-05 03:49:38,780 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 03:49:38,780 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1455239246] [2022-04-05 03:49:38,780 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1455239246] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-05 03:49:38,781 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-05 03:49:38,781 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12] total 12 [2022-04-05 03:49:38,781 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1460675222] [2022-04-05 03:49:38,781 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-04-05 03:49:38,781 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2022-04-05 03:49:38,781 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 03:49:38,782 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-04-05 03:49:38,782 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=39, Invalid=171, Unknown=0, NotChecked=0, Total=210 [2022-04-05 03:49:38,782 INFO L87 Difference]: Start difference. First operand 93 states and 97 transitions. Second operand has 12 states, 11 states have (on average 2.727272727272727) internal successors, (30), 11 states have internal predecessors, (30), 9 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-05 03:49:38,962 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 03:49:38,962 INFO L93 Difference]: Finished difference Result 96 states and 99 transitions. [2022-04-05 03:49:38,962 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2022-04-05 03:49:38,963 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 11 states have (on average 2.727272727272727) internal successors, (30), 11 states have internal predecessors, (30), 9 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) Word has length 66 [2022-04-05 03:49:38,963 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 03:49:38,963 INFO L225 Difference]: With dead ends: 96 [2022-04-05 03:49:38,964 INFO L226 Difference]: Without dead ends: 93 [2022-04-05 03:49:38,964 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 81 GetRequests, 65 SyntacticMatches, 1 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=49, Invalid=223, Unknown=0, NotChecked=0, Total=272 [2022-04-05 03:49:38,964 INFO L913 BasicCegarLoop]: 42 mSDtfsCounter, 2 mSDsluCounter, 258 mSDsCounter, 0 mSdLazyCounter, 231 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 300 SdHoareTripleChecker+Invalid, 231 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 231 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-04-05 03:49:38,965 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 300 Invalid, 231 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 231 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-04-05 03:49:38,965 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 93 states. [2022-04-05 03:49:38,969 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 93 to 93. [2022-04-05 03:49:38,969 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 93 states, 68 states have (on average 1.0588235294117647) internal successors, (72), 68 states have internal predecessors, (72), 13 states have call successors, (13), 13 states have call predecessors, (13), 11 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-05 03:49:38,970 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 96 transitions. [2022-04-05 03:49:38,970 INFO L78 Accepts]: Start accepts. Automaton has 93 states and 96 transitions. Word has length 66 [2022-04-05 03:49:38,970 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 03:49:38,970 INFO L478 AbstractCegarLoop]: Abstraction has 93 states and 96 transitions. [2022-04-05 03:49:38,970 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 11 states have (on average 2.727272727272727) internal successors, (30), 11 states have internal predecessors, (30), 9 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-05 03:49:38,970 INFO L276 IsEmpty]: Start isEmpty. Operand 93 states and 96 transitions. [2022-04-05 03:49:38,971 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2022-04-05 03:49:38,971 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 03:49:38,971 INFO L499 BasicCegarLoop]: trace histogram [9, 8, 8, 8, 8, 8, 8, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 03:49:38,983 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-05 03:49:39,177 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2022-04-05 03:49:39,177 INFO L403 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 03:49:39,178 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 03:49:39,178 INFO L85 PathProgramCache]: Analyzing trace with hash 291122568, now seen corresponding path program 7 times [2022-04-05 03:49:39,178 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 03:49:39,178 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [984284083] [2022-04-05 03:49:39,178 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 03:49:39,178 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 03:49:39,189 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 03:49:39,189 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [64310105] [2022-04-05 03:49:39,190 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2022-04-05 03:49:39,190 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 03:49:39,190 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 03:49:39,191 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-05 03:49:39,207 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-05 03:49:39,725 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 03:49:39,726 INFO L263 TraceCheckSpWp]: Trace formula consists of 228 conjuncts, 37 conjunts are in the unsatisfiable core [2022-04-05 03:49:39,728 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 03:49:40,090 INFO L134 CoverageAnalysis]: Checked inductivity of 240 backedges. 16 proven. 112 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2022-04-05 03:49:40,090 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 03:49:40,646 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 03:49:40,646 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [984284083] [2022-04-05 03:49:40,646 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 03:49:40,646 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [64310105] [2022-04-05 03:49:40,646 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [64310105] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-05 03:49:40,646 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-05 03:49:40,647 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2022-04-05 03:49:40,647 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1142149530] [2022-04-05 03:49:40,647 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-04-05 03:49:40,647 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2022-04-05 03:49:40,647 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 03:49:40,648 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2022-04-05 03:49:40,648 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=97, Invalid=365, Unknown=0, NotChecked=0, Total=462 [2022-04-05 03:49:40,648 INFO L87 Difference]: Start difference. First operand 93 states and 96 transitions. Second operand has 13 states, 12 states have (on average 2.75) internal successors, (33), 12 states have internal predecessors, (33), 10 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-05 03:49:40,871 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 03:49:40,872 INFO L93 Difference]: Finished difference Result 96 states and 98 transitions. [2022-04-05 03:49:40,872 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2022-04-05 03:49:40,872 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 12 states have (on average 2.75) internal successors, (33), 12 states have internal predecessors, (33), 10 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Word has length 74 [2022-04-05 03:49:40,873 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 03:49:40,873 INFO L225 Difference]: With dead ends: 96 [2022-04-05 03:49:40,873 INFO L226 Difference]: Without dead ends: 93 [2022-04-05 03:49:40,874 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 137 GetRequests, 114 SyntacticMatches, 1 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=107, Invalid=445, Unknown=0, NotChecked=0, Total=552 [2022-04-05 03:49:40,874 INFO L913 BasicCegarLoop]: 46 mSDtfsCounter, 2 mSDsluCounter, 306 mSDsCounter, 0 mSdLazyCounter, 286 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 352 SdHoareTripleChecker+Invalid, 286 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 286 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-04-05 03:49:40,874 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 352 Invalid, 286 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 286 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-04-05 03:49:40,875 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 93 states. [2022-04-05 03:49:40,877 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 93 to 93. [2022-04-05 03:49:40,878 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 93 states, 68 states have (on average 1.0441176470588236) internal successors, (71), 68 states have internal predecessors, (71), 13 states have call successors, (13), 13 states have call predecessors, (13), 11 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-05 03:49:40,878 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 95 transitions. [2022-04-05 03:49:40,878 INFO L78 Accepts]: Start accepts. Automaton has 93 states and 95 transitions. Word has length 74 [2022-04-05 03:49:40,878 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 03:49:40,878 INFO L478 AbstractCegarLoop]: Abstraction has 93 states and 95 transitions. [2022-04-05 03:49:40,879 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 12 states have (on average 2.75) internal successors, (33), 12 states have internal predecessors, (33), 10 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-05 03:49:40,879 INFO L276 IsEmpty]: Start isEmpty. Operand 93 states and 95 transitions. [2022-04-05 03:49:40,879 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 83 [2022-04-05 03:49:40,879 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 03:49:40,879 INFO L499 BasicCegarLoop]: trace histogram [10, 9, 9, 9, 9, 9, 9, 8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 03:49:40,893 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2022-04-05 03:49:41,091 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2022-04-05 03:49:41,091 INFO L403 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 03:49:41,092 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 03:49:41,092 INFO L85 PathProgramCache]: Analyzing trace with hash 1938494313, now seen corresponding path program 8 times [2022-04-05 03:49:41,092 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 03:49:41,092 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1247759681] [2022-04-05 03:49:41,092 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 03:49:41,092 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 03:49:41,100 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 03:49:41,100 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1123234884] [2022-04-05 03:49:41,100 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-05 03:49:41,100 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 03:49:41,101 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 03:49:41,103 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-05 03:49:41,104 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2022-04-05 03:49:41,635 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-05 03:49:41,635 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-05 03:49:41,637 INFO L263 TraceCheckSpWp]: Trace formula consists of 249 conjuncts, 40 conjunts are in the unsatisfiable core [2022-04-05 03:49:41,638 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 03:49:41,940 INFO L134 CoverageAnalysis]: Checked inductivity of 306 backedges. 18 proven. 144 refuted. 0 times theorem prover too weak. 144 trivial. 0 not checked. [2022-04-05 03:49:41,940 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 03:49:42,114 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 03:49:42,114 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1247759681] [2022-04-05 03:49:42,114 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 03:49:42,114 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1123234884] [2022-04-05 03:49:42,114 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1123234884] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-05 03:49:42,114 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-05 03:49:42,114 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14] total 14 [2022-04-05 03:49:42,115 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [841305882] [2022-04-05 03:49:42,115 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-04-05 03:49:42,115 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2022-04-05 03:49:42,115 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 03:49:42,115 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2022-04-05 03:49:42,116 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=45, Invalid=227, Unknown=0, NotChecked=0, Total=272 [2022-04-05 03:49:42,116 INFO L87 Difference]: Start difference. First operand 93 states and 95 transitions. Second operand has 14 states, 13 states have (on average 2.769230769230769) internal successors, (36), 13 states have internal predecessors, (36), 11 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-05 03:49:42,363 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 03:49:42,363 INFO L93 Difference]: Finished difference Result 96 states and 97 transitions. [2022-04-05 03:49:42,363 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2022-04-05 03:49:42,363 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 13 states have (on average 2.769230769230769) internal successors, (36), 13 states have internal predecessors, (36), 11 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Word has length 82 [2022-04-05 03:49:42,364 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 03:49:42,364 INFO L225 Difference]: With dead ends: 96 [2022-04-05 03:49:42,364 INFO L226 Difference]: Without dead ends: 93 [2022-04-05 03:49:42,364 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 97 GetRequests, 79 SyntacticMatches, 1 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=55, Invalid=287, Unknown=0, NotChecked=0, Total=342 [2022-04-05 03:49:42,365 INFO L913 BasicCegarLoop]: 50 mSDtfsCounter, 2 mSDsluCounter, 358 mSDsCounter, 0 mSdLazyCounter, 347 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 408 SdHoareTripleChecker+Invalid, 347 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 347 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-04-05 03:49:42,365 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 408 Invalid, 347 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 347 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-04-05 03:49:42,365 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 93 states. [2022-04-05 03:49:42,368 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 93 to 93. [2022-04-05 03:49:42,368 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 93 states, 68 states have (on average 1.0294117647058822) internal successors, (70), 68 states have internal predecessors, (70), 13 states have call successors, (13), 13 states have call predecessors, (13), 11 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-05 03:49:42,369 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 94 transitions. [2022-04-05 03:49:42,369 INFO L78 Accepts]: Start accepts. Automaton has 93 states and 94 transitions. Word has length 82 [2022-04-05 03:49:42,369 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 03:49:42,369 INFO L478 AbstractCegarLoop]: Abstraction has 93 states and 94 transitions. [2022-04-05 03:49:42,369 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 13 states have (on average 2.769230769230769) internal successors, (36), 13 states have internal predecessors, (36), 11 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-05 03:49:42,369 INFO L276 IsEmpty]: Start isEmpty. Operand 93 states and 94 transitions. [2022-04-05 03:49:42,370 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 91 [2022-04-05 03:49:42,370 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 03:49:42,370 INFO L499 BasicCegarLoop]: trace histogram [11, 10, 10, 10, 10, 10, 10, 9, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 03:49:42,380 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2022-04-05 03:49:42,570 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2022-04-05 03:49:42,571 INFO L403 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 03:49:42,571 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 03:49:42,571 INFO L85 PathProgramCache]: Analyzing trace with hash 757893194, now seen corresponding path program 9 times [2022-04-05 03:49:42,572 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 03:49:42,572 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [293549394] [2022-04-05 03:49:42,572 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 03:49:42,572 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 03:49:42,584 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 03:49:42,584 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1788652168] [2022-04-05 03:49:42,585 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-04-05 03:49:42,585 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 03:49:42,585 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 03:49:42,586 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-05 03:49:42,587 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2022-04-05 03:49:43,059 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 10 check-sat command(s) [2022-04-05 03:49:43,059 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-05 03:49:43,061 INFO L263 TraceCheckSpWp]: Trace formula consists of 270 conjuncts, 55 conjunts are in the unsatisfiable core [2022-04-05 03:49:43,066 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 03:49:43,517 INFO L134 CoverageAnalysis]: Checked inductivity of 380 backedges. 66 proven. 182 refuted. 0 times theorem prover too weak. 132 trivial. 0 not checked. [2022-04-05 03:49:43,517 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 03:49:47,762 WARN L833 $PredicateComparison]: unable to prove that (let ((.cse0 (* 6 c_main_~y~0 c_main_~y~0 c_main_~y~0)) (.cse1 (* 13 c_main_~y~0 c_main_~y~0)) (.cse2 (* c_main_~y~0 c_main_~y~0 c_main_~y~0 c_main_~y~0))) (or (not (<= (+ (* c_main_~y~0 c_main_~y~0 c_main_~y~0) c_main_~x~0 1 (* 3 (* c_main_~y~0 c_main_~y~0))) (div (+ .cse0 .cse1 4 .cse2) 4))) (forall ((main_~k~0 Int)) (or (< (+ c_main_~c~0 1) main_~k~0) (not (< c_main_~c~0 main_~k~0)) (let ((.cse3 (+ c_main_~y~0 1))) (= (* .cse3 .cse3) (* main_~k~0 .cse3))))) (not (= 0 (mod (+ .cse0 .cse1 .cse2) 4))))) is different from false [2022-04-05 03:49:51,815 WARN L833 $PredicateComparison]: unable to prove that (or (forall ((main_~k~0 Int)) (or (< (+ c_main_~c~0 1) main_~k~0) (not (< c_main_~c~0 main_~k~0)) (let ((.cse0 (+ c_main_~y~0 1))) (= (* .cse0 .cse0) (* main_~k~0 .cse0))))) (not (= 0 (mod (+ (* 6 c_main_~y~0 c_main_~y~0 c_main_~y~0) (* 13 c_main_~y~0 c_main_~y~0) (* c_main_~y~0 c_main_~y~0 c_main_~y~0 c_main_~y~0)) 4)))) is different from false [2022-04-05 03:49:51,817 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 03:49:51,818 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [293549394] [2022-04-05 03:49:51,818 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 03:49:51,818 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1788652168] [2022-04-05 03:49:51,818 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1788652168] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-05 03:49:51,818 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-05 03:49:51,818 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19] total 19 [2022-04-05 03:49:51,818 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [939198770] [2022-04-05 03:49:51,818 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-04-05 03:49:51,818 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2022-04-05 03:49:51,819 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 03:49:51,819 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2022-04-05 03:49:51,819 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=66, Invalid=446, Unknown=2, NotChecked=86, Total=600 [2022-04-05 03:49:51,819 INFO L87 Difference]: Start difference. First operand 93 states and 94 transitions. Second operand has 19 states, 18 states have (on average 2.3333333333333335) internal successors, (42), 16 states have internal predecessors, (42), 12 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-05 03:49:52,157 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 03:49:52,157 INFO L93 Difference]: Finished difference Result 98 states and 100 transitions. [2022-04-05 03:49:52,157 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2022-04-05 03:49:52,158 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 18 states have (on average 2.3333333333333335) internal successors, (42), 16 states have internal predecessors, (42), 12 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) Word has length 90 [2022-04-05 03:49:52,158 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 03:49:52,159 INFO L225 Difference]: With dead ends: 98 [2022-04-05 03:49:52,159 INFO L226 Difference]: Without dead ends: 95 [2022-04-05 03:49:52,159 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 106 GetRequests, 79 SyntacticMatches, 1 SemanticMatches, 26 ConstructedPredicates, 2 IntricatePredicates, 0 DeprecatedPredicates, 32 ImplicationChecksByTransitivity, 4.3s TimeCoverageRelationStatistics Valid=87, Invalid=569, Unknown=2, NotChecked=98, Total=756 [2022-04-05 03:49:52,160 INFO L913 BasicCegarLoop]: 41 mSDtfsCounter, 10 mSDsluCounter, 386 mSDsCounter, 0 mSdLazyCounter, 518 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 427 SdHoareTripleChecker+Invalid, 520 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 518 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-04-05 03:49:52,160 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [12 Valid, 427 Invalid, 520 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 518 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-04-05 03:49:52,160 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 95 states. [2022-04-05 03:49:52,163 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 95 to 95. [2022-04-05 03:49:52,163 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 95 states, 69 states have (on average 1.0289855072463767) internal successors, (71), 69 states have internal predecessors, (71), 14 states have call successors, (14), 13 states have call predecessors, (14), 11 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-05 03:49:52,164 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 95 states to 95 states and 97 transitions. [2022-04-05 03:49:52,164 INFO L78 Accepts]: Start accepts. Automaton has 95 states and 97 transitions. Word has length 90 [2022-04-05 03:49:52,164 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 03:49:52,164 INFO L478 AbstractCegarLoop]: Abstraction has 95 states and 97 transitions. [2022-04-05 03:49:52,164 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 18 states have (on average 2.3333333333333335) internal successors, (42), 16 states have internal predecessors, (42), 12 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-05 03:49:52,164 INFO L276 IsEmpty]: Start isEmpty. Operand 95 states and 97 transitions. [2022-04-05 03:49:52,165 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 93 [2022-04-05 03:49:52,165 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 03:49:52,165 INFO L499 BasicCegarLoop]: trace histogram [11, 11, 10, 10, 10, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 03:49:52,177 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2022-04-05 03:49:52,365 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable14,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 03:49:52,366 INFO L403 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 03:49:52,366 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 03:49:52,366 INFO L85 PathProgramCache]: Analyzing trace with hash -953190739, now seen corresponding path program 3 times [2022-04-05 03:49:52,367 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 03:49:52,367 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1889097191] [2022-04-05 03:49:52,367 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 03:49:52,367 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 03:49:52,374 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 03:49:52,374 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [616944618] [2022-04-05 03:49:52,374 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-04-05 03:49:52,374 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 03:49:52,375 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 03:49:52,381 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-05 03:49:52,383 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2022-04-05 03:49:52,449 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 11 check-sat command(s) [2022-04-05 03:49:52,449 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-05 03:49:52,450 INFO L263 TraceCheckSpWp]: Trace formula consists of 281 conjuncts, 25 conjunts are in the unsatisfiable core [2022-04-05 03:49:52,452 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 03:49:52,679 INFO L134 CoverageAnalysis]: Checked inductivity of 400 backedges. 20 proven. 380 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-05 03:49:52,680 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 03:49:52,998 INFO L134 CoverageAnalysis]: Checked inductivity of 400 backedges. 20 proven. 200 refuted. 0 times theorem prover too weak. 180 trivial. 0 not checked. [2022-04-05 03:49:52,999 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 03:49:52,999 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1889097191] [2022-04-05 03:49:52,999 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 03:49:52,999 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [616944618] [2022-04-05 03:49:52,999 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [616944618] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-05 03:49:52,999 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-05 03:49:52,999 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 26 [2022-04-05 03:49:53,000 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [185722405] [2022-04-05 03:49:53,000 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-05 03:49:53,000 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2022-04-05 03:49:53,000 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 03:49:53,001 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2022-04-05 03:49:53,001 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=281, Invalid=369, Unknown=0, NotChecked=0, Total=650 [2022-04-05 03:49:53,001 INFO L87 Difference]: Start difference. First operand 95 states and 97 transitions. Second operand has 26 states, 26 states have (on average 4.076923076923077) internal successors, (106), 26 states have internal predecessors, (106), 24 states have call successors, (24), 14 states have call predecessors, (24), 13 states have return successors, (22), 22 states have call predecessors, (22), 21 states have call successors, (22) [2022-04-05 03:49:53,414 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 03:49:53,415 INFO L93 Difference]: Finished difference Result 244 states and 245 transitions. [2022-04-05 03:49:53,415 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 46 states. [2022-04-05 03:49:53,415 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 26 states have (on average 4.076923076923077) internal successors, (106), 26 states have internal predecessors, (106), 24 states have call successors, (24), 14 states have call predecessors, (24), 13 states have return successors, (22), 22 states have call predecessors, (22), 21 states have call successors, (22) Word has length 92 [2022-04-05 03:49:53,415 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 03:49:53,416 INFO L225 Difference]: With dead ends: 244 [2022-04-05 03:49:53,416 INFO L226 Difference]: Without dead ends: 244 [2022-04-05 03:49:53,417 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 204 GetRequests, 159 SyntacticMatches, 0 SemanticMatches, 45 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 286 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=796, Invalid=1366, Unknown=0, NotChecked=0, Total=2162 [2022-04-05 03:49:53,418 INFO L913 BasicCegarLoop]: 38 mSDtfsCounter, 286 mSDsluCounter, 175 mSDsCounter, 0 mSdLazyCounter, 142 mSolverCounterSat, 101 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 286 SdHoareTripleChecker+Valid, 213 SdHoareTripleChecker+Invalid, 243 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 101 IncrementalHoareTripleChecker+Valid, 142 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-04-05 03:49:53,418 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [286 Valid, 213 Invalid, 243 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [101 Valid, 142 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-04-05 03:49:53,418 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 244 states. [2022-04-05 03:49:53,423 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 244 to 189. [2022-04-05 03:49:53,423 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 189 states, 140 states have (on average 1.0928571428571427) internal successors, (153), 140 states have internal predecessors, (153), 25 states have call successors, (25), 25 states have call predecessors, (25), 23 states have return successors, (23), 23 states have call predecessors, (23), 23 states have call successors, (23) [2022-04-05 03:49:53,424 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 189 states to 189 states and 201 transitions. [2022-04-05 03:49:53,424 INFO L78 Accepts]: Start accepts. Automaton has 189 states and 201 transitions. Word has length 92 [2022-04-05 03:49:53,424 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 03:49:53,424 INFO L478 AbstractCegarLoop]: Abstraction has 189 states and 201 transitions. [2022-04-05 03:49:53,425 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 26 states have (on average 4.076923076923077) internal successors, (106), 26 states have internal predecessors, (106), 24 states have call successors, (24), 14 states have call predecessors, (24), 13 states have return successors, (22), 22 states have call predecessors, (22), 21 states have call successors, (22) [2022-04-05 03:49:53,425 INFO L276 IsEmpty]: Start isEmpty. Operand 189 states and 201 transitions. [2022-04-05 03:49:53,425 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 99 [2022-04-05 03:49:53,425 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 03:49:53,425 INFO L499 BasicCegarLoop]: trace histogram [12, 11, 11, 11, 11, 11, 11, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 03:49:53,451 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Forceful destruction successful, exit code 0 [2022-04-05 03:49:53,648 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2022-04-05 03:49:53,648 INFO L403 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 03:49:53,649 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 03:49:53,649 INFO L85 PathProgramCache]: Analyzing trace with hash 138382379, now seen corresponding path program 10 times [2022-04-05 03:49:53,649 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 03:49:53,649 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [150882274] [2022-04-05 03:49:53,649 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 03:49:53,649 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 03:49:53,663 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 03:49:53,663 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [121521710] [2022-04-05 03:49:53,663 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-04-05 03:49:53,663 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 03:49:53,663 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 03:49:53,671 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-05 03:49:53,672 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2022-04-05 03:49:54,895 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-04-05 03:49:54,895 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-05 03:49:54,897 INFO L263 TraceCheckSpWp]: Trace formula consists of 291 conjuncts, 48 conjunts are in the unsatisfiable core [2022-04-05 03:49:54,898 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 03:49:55,284 INFO L134 CoverageAnalysis]: Checked inductivity of 462 backedges. 22 proven. 220 refuted. 0 times theorem prover too weak. 220 trivial. 0 not checked. [2022-04-05 03:49:55,285 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 03:49:55,431 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 03:49:55,432 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [150882274] [2022-04-05 03:49:55,432 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 03:49:55,432 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [121521710] [2022-04-05 03:49:55,432 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [121521710] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-05 03:49:55,432 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-05 03:49:55,432 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16] total 16 [2022-04-05 03:49:55,432 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [738208717] [2022-04-05 03:49:55,432 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-04-05 03:49:55,433 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2022-04-05 03:49:55,433 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 03:49:55,433 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2022-04-05 03:49:55,433 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=51, Invalid=291, Unknown=0, NotChecked=0, Total=342 [2022-04-05 03:49:55,434 INFO L87 Difference]: Start difference. First operand 189 states and 201 transitions. Second operand has 16 states, 15 states have (on average 2.8) internal successors, (42), 15 states have internal predecessors, (42), 13 states have call successors, (14), 2 states have call predecessors, (14), 1 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-05 03:49:55,689 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 03:49:55,689 INFO L93 Difference]: Finished difference Result 192 states and 203 transitions. [2022-04-05 03:49:55,689 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2022-04-05 03:49:55,689 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 15 states have (on average 2.8) internal successors, (42), 15 states have internal predecessors, (42), 13 states have call successors, (14), 2 states have call predecessors, (14), 1 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) Word has length 98 [2022-04-05 03:49:55,690 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 03:49:55,690 INFO L225 Difference]: With dead ends: 192 [2022-04-05 03:49:55,690 INFO L226 Difference]: Without dead ends: 189 [2022-04-05 03:49:55,691 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 113 GetRequests, 93 SyntacticMatches, 1 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=61, Invalid=359, Unknown=0, NotChecked=0, Total=420 [2022-04-05 03:49:55,691 INFO L913 BasicCegarLoop]: 58 mSDtfsCounter, 2 mSDsluCounter, 474 mSDsCounter, 0 mSdLazyCounter, 487 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 532 SdHoareTripleChecker+Invalid, 487 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 487 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-04-05 03:49:55,691 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 532 Invalid, 487 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 487 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-04-05 03:49:55,692 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 189 states. [2022-04-05 03:49:55,696 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 189 to 189. [2022-04-05 03:49:55,696 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 189 states, 140 states have (on average 1.0857142857142856) internal successors, (152), 140 states have internal predecessors, (152), 25 states have call successors, (25), 25 states have call predecessors, (25), 23 states have return successors, (23), 23 states have call predecessors, (23), 23 states have call successors, (23) [2022-04-05 03:49:55,697 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 189 states to 189 states and 200 transitions. [2022-04-05 03:49:55,697 INFO L78 Accepts]: Start accepts. Automaton has 189 states and 200 transitions. Word has length 98 [2022-04-05 03:49:55,697 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 03:49:55,697 INFO L478 AbstractCegarLoop]: Abstraction has 189 states and 200 transitions. [2022-04-05 03:49:55,698 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 15 states have (on average 2.8) internal successors, (42), 15 states have internal predecessors, (42), 13 states have call successors, (14), 2 states have call predecessors, (14), 1 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-05 03:49:55,698 INFO L276 IsEmpty]: Start isEmpty. Operand 189 states and 200 transitions. [2022-04-05 03:49:55,698 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 107 [2022-04-05 03:49:55,699 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 03:49:55,699 INFO L499 BasicCegarLoop]: trace histogram [13, 12, 12, 12, 12, 12, 12, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 03:49:55,708 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Forceful destruction successful, exit code 0 [2022-04-05 03:49:55,904 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2022-04-05 03:49:55,905 INFO L403 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 03:49:55,905 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 03:49:55,905 INFO L85 PathProgramCache]: Analyzing trace with hash 1036328716, now seen corresponding path program 11 times [2022-04-05 03:49:55,905 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 03:49:55,905 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [529733509] [2022-04-05 03:49:55,905 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 03:49:55,906 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 03:49:55,915 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 03:49:55,915 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2098736722] [2022-04-05 03:49:55,915 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2022-04-05 03:49:55,915 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 03:49:55,915 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 03:49:55,918 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-05 03:49:55,921 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2022-04-05 03:49:56,471 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 12 check-sat command(s) [2022-04-05 03:49:56,471 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-05 03:49:56,474 INFO L263 TraceCheckSpWp]: Trace formula consists of 312 conjuncts, 52 conjunts are in the unsatisfiable core [2022-04-05 03:49:56,476 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 03:49:56,885 INFO L134 CoverageAnalysis]: Checked inductivity of 552 backedges. 24 proven. 264 refuted. 0 times theorem prover too weak. 264 trivial. 0 not checked. [2022-04-05 03:49:56,886 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 03:49:57,065 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 03:49:57,065 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [529733509] [2022-04-05 03:49:57,065 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 03:49:57,065 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2098736722] [2022-04-05 03:49:57,066 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2098736722] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-05 03:49:57,066 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-05 03:49:57,066 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17] total 17 [2022-04-05 03:49:57,066 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [968589575] [2022-04-05 03:49:57,066 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-04-05 03:49:57,066 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2022-04-05 03:49:57,066 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 03:49:57,067 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2022-04-05 03:49:57,067 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=54, Invalid=326, Unknown=0, NotChecked=0, Total=380 [2022-04-05 03:49:57,067 INFO L87 Difference]: Start difference. First operand 189 states and 200 transitions. Second operand has 17 states, 16 states have (on average 2.8125) internal successors, (45), 16 states have internal predecessors, (45), 14 states have call successors, (15), 2 states have call predecessors, (15), 1 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2022-04-05 03:49:57,370 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 03:49:57,370 INFO L93 Difference]: Finished difference Result 192 states and 202 transitions. [2022-04-05 03:49:57,371 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2022-04-05 03:49:57,371 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 16 states have (on average 2.8125) internal successors, (45), 16 states have internal predecessors, (45), 14 states have call successors, (15), 2 states have call predecessors, (15), 1 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) Word has length 106 [2022-04-05 03:49:57,372 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 03:49:57,372 INFO L225 Difference]: With dead ends: 192 [2022-04-05 03:49:57,372 INFO L226 Difference]: Without dead ends: 189 [2022-04-05 03:49:57,373 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 121 GetRequests, 100 SyntacticMatches, 1 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=64, Invalid=398, Unknown=0, NotChecked=0, Total=462 [2022-04-05 03:49:57,373 INFO L913 BasicCegarLoop]: 62 mSDtfsCounter, 2 mSDsluCounter, 538 mSDsCounter, 0 mSdLazyCounter, 566 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 600 SdHoareTripleChecker+Invalid, 566 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 566 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-04-05 03:49:57,373 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 600 Invalid, 566 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 566 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-04-05 03:49:57,374 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 189 states. [2022-04-05 03:49:57,378 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 189 to 189. [2022-04-05 03:49:57,378 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 189 states, 140 states have (on average 1.0785714285714285) internal successors, (151), 140 states have internal predecessors, (151), 25 states have call successors, (25), 25 states have call predecessors, (25), 23 states have return successors, (23), 23 states have call predecessors, (23), 23 states have call successors, (23) [2022-04-05 03:49:57,379 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 189 states to 189 states and 199 transitions. [2022-04-05 03:49:57,379 INFO L78 Accepts]: Start accepts. Automaton has 189 states and 199 transitions. Word has length 106 [2022-04-05 03:49:57,379 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 03:49:57,379 INFO L478 AbstractCegarLoop]: Abstraction has 189 states and 199 transitions. [2022-04-05 03:49:57,379 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 16 states have (on average 2.8125) internal successors, (45), 16 states have internal predecessors, (45), 14 states have call successors, (15), 2 states have call predecessors, (15), 1 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2022-04-05 03:49:57,380 INFO L276 IsEmpty]: Start isEmpty. Operand 189 states and 199 transitions. [2022-04-05 03:49:57,380 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 115 [2022-04-05 03:49:57,380 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 03:49:57,381 INFO L499 BasicCegarLoop]: trace histogram [14, 13, 13, 13, 13, 13, 13, 12, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 03:49:57,387 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Forceful destruction successful, exit code 0 [2022-04-05 03:49:57,586 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 18 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2022-04-05 03:49:57,587 INFO L403 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 03:49:57,587 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 03:49:57,587 INFO L85 PathProgramCache]: Analyzing trace with hash 1975402733, now seen corresponding path program 12 times [2022-04-05 03:49:57,587 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 03:49:57,587 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [832240299] [2022-04-05 03:49:57,588 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 03:49:57,588 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 03:49:57,605 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 03:49:57,605 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1260645936] [2022-04-05 03:49:57,605 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-04-05 03:49:57,605 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 03:49:57,605 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 03:49:57,609 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-05 03:49:57,626 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Waiting until timeout for monitored process [2022-04-05 03:49:58,136 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 13 check-sat command(s) [2022-04-05 03:49:58,137 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-05 03:49:58,139 INFO L263 TraceCheckSpWp]: Trace formula consists of 333 conjuncts, 56 conjunts are in the unsatisfiable core [2022-04-05 03:49:58,141 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 03:49:58,557 INFO L134 CoverageAnalysis]: Checked inductivity of 650 backedges. 26 proven. 312 refuted. 0 times theorem prover too weak. 312 trivial. 0 not checked. [2022-04-05 03:49:58,557 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 03:49:58,703 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 03:49:58,703 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [832240299] [2022-04-05 03:49:58,703 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 03:49:58,703 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1260645936] [2022-04-05 03:49:58,703 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1260645936] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-05 03:49:58,703 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-05 03:49:58,703 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18] total 18 [2022-04-05 03:49:58,703 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [92785143] [2022-04-05 03:49:58,704 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-04-05 03:49:58,704 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2022-04-05 03:49:58,704 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 03:49:58,704 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2022-04-05 03:49:58,704 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=57, Invalid=363, Unknown=0, NotChecked=0, Total=420 [2022-04-05 03:49:58,705 INFO L87 Difference]: Start difference. First operand 189 states and 199 transitions. Second operand has 18 states, 17 states have (on average 2.823529411764706) internal successors, (48), 17 states have internal predecessors, (48), 15 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) [2022-04-05 03:49:59,043 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 03:49:59,043 INFO L93 Difference]: Finished difference Result 192 states and 201 transitions. [2022-04-05 03:49:59,043 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2022-04-05 03:49:59,043 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 17 states have (on average 2.823529411764706) internal successors, (48), 17 states have internal predecessors, (48), 15 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) Word has length 114 [2022-04-05 03:49:59,043 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 03:49:59,044 INFO L225 Difference]: With dead ends: 192 [2022-04-05 03:49:59,044 INFO L226 Difference]: Without dead ends: 189 [2022-04-05 03:49:59,044 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 129 GetRequests, 107 SyntacticMatches, 1 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=67, Invalid=439, Unknown=0, NotChecked=0, Total=506 [2022-04-05 03:49:59,045 INFO L913 BasicCegarLoop]: 66 mSDtfsCounter, 2 mSDsluCounter, 606 mSDsCounter, 0 mSdLazyCounter, 651 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 672 SdHoareTripleChecker+Invalid, 651 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 651 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-04-05 03:49:59,045 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 672 Invalid, 651 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 651 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-04-05 03:49:59,045 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 189 states. [2022-04-05 03:49:59,049 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 189 to 189. [2022-04-05 03:49:59,049 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 189 states, 140 states have (on average 1.0714285714285714) internal successors, (150), 140 states have internal predecessors, (150), 25 states have call successors, (25), 25 states have call predecessors, (25), 23 states have return successors, (23), 23 states have call predecessors, (23), 23 states have call successors, (23) [2022-04-05 03:49:59,050 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 189 states to 189 states and 198 transitions. [2022-04-05 03:49:59,050 INFO L78 Accepts]: Start accepts. Automaton has 189 states and 198 transitions. Word has length 114 [2022-04-05 03:49:59,050 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 03:49:59,050 INFO L478 AbstractCegarLoop]: Abstraction has 189 states and 198 transitions. [2022-04-05 03:49:59,050 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 17 states have (on average 2.823529411764706) internal successors, (48), 17 states have internal predecessors, (48), 15 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) [2022-04-05 03:49:59,051 INFO L276 IsEmpty]: Start isEmpty. Operand 189 states and 198 transitions. [2022-04-05 03:49:59,051 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 123 [2022-04-05 03:49:59,051 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 03:49:59,052 INFO L499 BasicCegarLoop]: trace histogram [15, 14, 14, 14, 14, 14, 14, 13, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 03:49:59,057 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Forceful destruction successful, exit code 0 [2022-04-05 03:49:59,255 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,19 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 03:49:59,255 INFO L403 AbstractCegarLoop]: === Iteration 20 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 03:49:59,256 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 03:49:59,256 INFO L85 PathProgramCache]: Analyzing trace with hash -953421362, now seen corresponding path program 13 times [2022-04-05 03:49:59,256 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 03:49:59,256 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [923516334] [2022-04-05 03:49:59,256 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 03:49:59,257 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 03:49:59,274 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 03:49:59,274 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [495120343] [2022-04-05 03:49:59,275 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2022-04-05 03:49:59,275 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 03:49:59,275 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 03:49:59,277 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-05 03:49:59,295 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Waiting until timeout for monitored process [2022-04-05 03:50:00,337 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 03:50:00,339 INFO L263 TraceCheckSpWp]: Trace formula consists of 354 conjuncts, 67 conjunts are in the unsatisfiable core [2022-04-05 03:50:00,341 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 03:50:00,802 INFO L134 CoverageAnalysis]: Checked inductivity of 756 backedges. 66 proven. 365 refuted. 0 times theorem prover too weak. 325 trivial. 0 not checked. [2022-04-05 03:50:00,802 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 03:50:05,010 WARN L833 $PredicateComparison]: unable to prove that (or (forall ((main_~k~0 Int)) (or (< (+ c_main_~c~0 1) main_~k~0) (not (< c_main_~c~0 main_~k~0)) (let ((.cse0 (+ c_main_~y~0 1))) (= (* .cse0 .cse0) (* main_~k~0 .cse0))))) (not (= (mod (+ (* 2 c_main_~y~0 c_main_~y~0 c_main_~y~0) (* c_main_~y~0 c_main_~y~0) (* c_main_~y~0 c_main_~y~0 c_main_~y~0 c_main_~y~0)) 4) 0))) is different from false [2022-04-05 03:50:07,029 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 03:50:07,029 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [923516334] [2022-04-05 03:50:07,029 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 03:50:07,029 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [495120343] [2022-04-05 03:50:07,029 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [495120343] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-05 03:50:07,029 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-05 03:50:07,029 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21] total 21 [2022-04-05 03:50:07,029 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1601770233] [2022-04-05 03:50:07,029 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-04-05 03:50:07,030 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2022-04-05 03:50:07,030 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 03:50:07,030 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2022-04-05 03:50:07,030 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=64, Invalid=539, Unknown=1, NotChecked=46, Total=650 [2022-04-05 03:50:07,030 INFO L87 Difference]: Start difference. First operand 189 states and 198 transitions. Second operand has 21 states, 20 states have (on average 2.7) internal successors, (54), 20 states have internal predecessors, (54), 16 states have call successors, (17), 2 states have call predecessors, (17), 2 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) [2022-04-05 03:50:07,537 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 03:50:07,537 INFO L93 Difference]: Finished difference Result 192 states and 200 transitions. [2022-04-05 03:50:07,538 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2022-04-05 03:50:07,539 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 20 states have (on average 2.7) internal successors, (54), 20 states have internal predecessors, (54), 16 states have call successors, (17), 2 states have call predecessors, (17), 2 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) Word has length 122 [2022-04-05 03:50:07,539 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 03:50:07,540 INFO L225 Difference]: With dead ends: 192 [2022-04-05 03:50:07,540 INFO L226 Difference]: Without dead ends: 189 [2022-04-05 03:50:07,540 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 138 GetRequests, 110 SyntacticMatches, 1 SemanticMatches, 27 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 13 ImplicationChecksByTransitivity, 2.3s TimeCoverageRelationStatistics Valid=84, Invalid=675, Unknown=1, NotChecked=52, Total=812 [2022-04-05 03:50:07,541 INFO L913 BasicCegarLoop]: 53 mSDtfsCounter, 6 mSDsluCounter, 672 mSDsCounter, 0 mSdLazyCounter, 928 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 725 SdHoareTripleChecker+Invalid, 929 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 928 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2022-04-05 03:50:07,541 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [6 Valid, 725 Invalid, 929 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 928 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2022-04-05 03:50:07,541 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 189 states. [2022-04-05 03:50:07,545 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 189 to 189. [2022-04-05 03:50:07,545 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 189 states, 140 states have (on average 1.0642857142857143) internal successors, (149), 140 states have internal predecessors, (149), 25 states have call successors, (25), 25 states have call predecessors, (25), 23 states have return successors, (23), 23 states have call predecessors, (23), 23 states have call successors, (23) [2022-04-05 03:50:07,546 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 189 states to 189 states and 197 transitions. [2022-04-05 03:50:07,546 INFO L78 Accepts]: Start accepts. Automaton has 189 states and 197 transitions. Word has length 122 [2022-04-05 03:50:07,546 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 03:50:07,546 INFO L478 AbstractCegarLoop]: Abstraction has 189 states and 197 transitions. [2022-04-05 03:50:07,546 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 20 states have (on average 2.7) internal successors, (54), 20 states have internal predecessors, (54), 16 states have call successors, (17), 2 states have call predecessors, (17), 2 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) [2022-04-05 03:50:07,546 INFO L276 IsEmpty]: Start isEmpty. Operand 189 states and 197 transitions. [2022-04-05 03:50:07,547 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 131 [2022-04-05 03:50:07,547 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 03:50:07,547 INFO L499 BasicCegarLoop]: trace histogram [16, 15, 15, 15, 15, 15, 15, 14, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 03:50:07,553 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Forceful destruction successful, exit code 0 [2022-04-05 03:50:07,748 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19,20 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 03:50:07,748 INFO L403 AbstractCegarLoop]: === Iteration 21 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 03:50:07,748 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 03:50:07,749 INFO L85 PathProgramCache]: Analyzing trace with hash -1206963793, now seen corresponding path program 14 times [2022-04-05 03:50:07,749 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 03:50:07,749 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1482421051] [2022-04-05 03:50:07,749 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 03:50:07,749 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 03:50:07,755 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 03:50:07,755 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1058026301] [2022-04-05 03:50:07,755 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-05 03:50:07,755 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 03:50:07,755 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 03:50:07,756 INFO L229 MonitoredProcess]: Starting monitored process 21 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-05 03:50:07,757 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Waiting until timeout for monitored process [2022-04-05 03:50:08,610 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-05 03:50:08,611 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-05 03:50:08,613 INFO L263 TraceCheckSpWp]: Trace formula consists of 375 conjuncts, 64 conjunts are in the unsatisfiable core [2022-04-05 03:50:08,615 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 03:50:09,098 INFO L134 CoverageAnalysis]: Checked inductivity of 870 backedges. 30 proven. 420 refuted. 0 times theorem prover too weak. 420 trivial. 0 not checked. [2022-04-05 03:50:09,098 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 03:50:09,296 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 03:50:09,296 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1482421051] [2022-04-05 03:50:09,296 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 03:50:09,296 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1058026301] [2022-04-05 03:50:09,296 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1058026301] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-05 03:50:09,296 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-05 03:50:09,296 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [20] total 20 [2022-04-05 03:50:09,296 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2073313041] [2022-04-05 03:50:09,296 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-04-05 03:50:09,297 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2022-04-05 03:50:09,297 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 03:50:09,297 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2022-04-05 03:50:09,297 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=63, Invalid=443, Unknown=0, NotChecked=0, Total=506 [2022-04-05 03:50:09,298 INFO L87 Difference]: Start difference. First operand 189 states and 197 transitions. Second operand has 20 states, 19 states have (on average 2.8421052631578947) internal successors, (54), 19 states have internal predecessors, (54), 17 states have call successors, (18), 2 states have call predecessors, (18), 1 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2022-04-05 03:50:09,768 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 03:50:09,768 INFO L93 Difference]: Finished difference Result 192 states and 199 transitions. [2022-04-05 03:50:09,769 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2022-04-05 03:50:09,769 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 19 states have (on average 2.8421052631578947) internal successors, (54), 19 states have internal predecessors, (54), 17 states have call successors, (18), 2 states have call predecessors, (18), 1 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) Word has length 130 [2022-04-05 03:50:09,769 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 03:50:09,770 INFO L225 Difference]: With dead ends: 192 [2022-04-05 03:50:09,770 INFO L226 Difference]: Without dead ends: 189 [2022-04-05 03:50:09,770 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 145 GetRequests, 121 SyntacticMatches, 1 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=73, Invalid=527, Unknown=0, NotChecked=0, Total=600 [2022-04-05 03:50:09,771 INFO L913 BasicCegarLoop]: 74 mSDtfsCounter, 2 mSDsluCounter, 754 mSDsCounter, 0 mSdLazyCounter, 839 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 828 SdHoareTripleChecker+Invalid, 839 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 839 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2022-04-05 03:50:09,771 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 828 Invalid, 839 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 839 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2022-04-05 03:50:09,772 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 189 states. [2022-04-05 03:50:09,775 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 189 to 189. [2022-04-05 03:50:09,775 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 189 states, 140 states have (on average 1.0571428571428572) internal successors, (148), 140 states have internal predecessors, (148), 25 states have call successors, (25), 25 states have call predecessors, (25), 23 states have return successors, (23), 23 states have call predecessors, (23), 23 states have call successors, (23) [2022-04-05 03:50:09,776 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 189 states to 189 states and 196 transitions. [2022-04-05 03:50:09,776 INFO L78 Accepts]: Start accepts. Automaton has 189 states and 196 transitions. Word has length 130 [2022-04-05 03:50:09,776 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 03:50:09,776 INFO L478 AbstractCegarLoop]: Abstraction has 189 states and 196 transitions. [2022-04-05 03:50:09,777 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 19 states have (on average 2.8421052631578947) internal successors, (54), 19 states have internal predecessors, (54), 17 states have call successors, (18), 2 states have call predecessors, (18), 1 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2022-04-05 03:50:09,777 INFO L276 IsEmpty]: Start isEmpty. Operand 189 states and 196 transitions. [2022-04-05 03:50:09,778 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 139 [2022-04-05 03:50:09,778 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 03:50:09,778 INFO L499 BasicCegarLoop]: trace histogram [17, 16, 16, 16, 16, 16, 16, 15, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 03:50:09,787 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Forceful destruction successful, exit code 0 [2022-04-05 03:50:09,984 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 21 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable20 [2022-04-05 03:50:09,984 INFO L403 AbstractCegarLoop]: === Iteration 22 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 03:50:09,984 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 03:50:09,984 INFO L85 PathProgramCache]: Analyzing trace with hash 1030291600, now seen corresponding path program 15 times [2022-04-05 03:50:09,984 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 03:50:09,985 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1427372341] [2022-04-05 03:50:09,985 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 03:50:09,985 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 03:50:09,992 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 03:50:09,992 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [217509203] [2022-04-05 03:50:09,992 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-04-05 03:50:09,993 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 03:50:09,993 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 03:50:09,994 INFO L229 MonitoredProcess]: Starting monitored process 22 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-05 03:50:09,995 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (22)] Waiting until timeout for monitored process [2022-04-05 03:50:10,572 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 16 check-sat command(s) [2022-04-05 03:50:10,572 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-05 03:50:10,576 INFO L263 TraceCheckSpWp]: Trace formula consists of 396 conjuncts, 68 conjunts are in the unsatisfiable core [2022-04-05 03:50:10,578 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 03:50:11,086 INFO L134 CoverageAnalysis]: Checked inductivity of 992 backedges. 32 proven. 480 refuted. 0 times theorem prover too weak. 480 trivial. 0 not checked. [2022-04-05 03:50:11,086 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 03:50:11,220 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 03:50:11,221 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1427372341] [2022-04-05 03:50:11,221 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 03:50:11,221 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [217509203] [2022-04-05 03:50:11,221 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [217509203] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-05 03:50:11,221 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-05 03:50:11,221 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21] total 21 [2022-04-05 03:50:11,221 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [876487499] [2022-04-05 03:50:11,221 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-04-05 03:50:11,222 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2022-04-05 03:50:11,222 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 03:50:11,222 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2022-04-05 03:50:11,222 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=66, Invalid=486, Unknown=0, NotChecked=0, Total=552 [2022-04-05 03:50:11,223 INFO L87 Difference]: Start difference. First operand 189 states and 196 transitions. Second operand has 21 states, 20 states have (on average 2.85) internal successors, (57), 20 states have internal predecessors, (57), 18 states have call successors, (19), 2 states have call predecessors, (19), 1 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) [2022-04-05 03:50:11,748 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 03:50:11,748 INFO L93 Difference]: Finished difference Result 192 states and 198 transitions. [2022-04-05 03:50:11,750 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2022-04-05 03:50:11,750 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 20 states have (on average 2.85) internal successors, (57), 20 states have internal predecessors, (57), 18 states have call successors, (19), 2 states have call predecessors, (19), 1 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) Word has length 138 [2022-04-05 03:50:11,751 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 03:50:11,765 INFO L225 Difference]: With dead ends: 192 [2022-04-05 03:50:11,765 INFO L226 Difference]: Without dead ends: 189 [2022-04-05 03:50:11,765 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 153 GetRequests, 128 SyntacticMatches, 1 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=76, Invalid=574, Unknown=0, NotChecked=0, Total=650 [2022-04-05 03:50:11,766 INFO L913 BasicCegarLoop]: 78 mSDtfsCounter, 2 mSDsluCounter, 834 mSDsCounter, 0 mSdLazyCounter, 942 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 912 SdHoareTripleChecker+Invalid, 942 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 942 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2022-04-05 03:50:11,766 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 912 Invalid, 942 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 942 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2022-04-05 03:50:11,766 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 189 states. [2022-04-05 03:50:11,769 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 189 to 189. [2022-04-05 03:50:11,770 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 189 states, 140 states have (on average 1.05) internal successors, (147), 140 states have internal predecessors, (147), 25 states have call successors, (25), 25 states have call predecessors, (25), 23 states have return successors, (23), 23 states have call predecessors, (23), 23 states have call successors, (23) [2022-04-05 03:50:11,770 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 189 states to 189 states and 195 transitions. [2022-04-05 03:50:11,771 INFO L78 Accepts]: Start accepts. Automaton has 189 states and 195 transitions. Word has length 138 [2022-04-05 03:50:11,771 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 03:50:11,771 INFO L478 AbstractCegarLoop]: Abstraction has 189 states and 195 transitions. [2022-04-05 03:50:11,771 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 20 states have (on average 2.85) internal successors, (57), 20 states have internal predecessors, (57), 18 states have call successors, (19), 2 states have call predecessors, (19), 1 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) [2022-04-05 03:50:11,771 INFO L276 IsEmpty]: Start isEmpty. Operand 189 states and 195 transitions. [2022-04-05 03:50:11,772 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 147 [2022-04-05 03:50:11,772 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 03:50:11,772 INFO L499 BasicCegarLoop]: trace histogram [18, 17, 17, 17, 17, 17, 17, 16, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 03:50:11,784 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (22)] Forceful destruction successful, exit code 0 [2022-04-05 03:50:11,981 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 22 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable21 [2022-04-05 03:50:11,981 INFO L403 AbstractCegarLoop]: === Iteration 23 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 03:50:11,982 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 03:50:11,982 INFO L85 PathProgramCache]: Analyzing trace with hash -1153802639, now seen corresponding path program 16 times [2022-04-05 03:50:11,982 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 03:50:11,982 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1215864254] [2022-04-05 03:50:11,982 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 03:50:11,982 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 03:50:11,989 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 03:50:11,989 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [744802554] [2022-04-05 03:50:11,989 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-04-05 03:50:11,989 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 03:50:11,990 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 03:50:11,990 INFO L229 MonitoredProcess]: Starting monitored process 23 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-05 03:50:11,993 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (23)] Waiting until timeout for monitored process [2022-04-05 03:50:12,886 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-04-05 03:50:12,887 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-05 03:50:12,890 INFO L263 TraceCheckSpWp]: Trace formula consists of 417 conjuncts, 72 conjunts are in the unsatisfiable core [2022-04-05 03:50:12,892 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 03:50:13,420 INFO L134 CoverageAnalysis]: Checked inductivity of 1122 backedges. 34 proven. 544 refuted. 0 times theorem prover too weak. 544 trivial. 0 not checked. [2022-04-05 03:50:13,420 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 03:50:13,607 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 03:50:13,608 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1215864254] [2022-04-05 03:50:13,608 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 03:50:13,608 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [744802554] [2022-04-05 03:50:13,608 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [744802554] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-05 03:50:13,608 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-05 03:50:13,608 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22] total 22 [2022-04-05 03:50:13,608 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [264005088] [2022-04-05 03:50:13,608 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-04-05 03:50:13,609 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2022-04-05 03:50:13,609 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 03:50:13,609 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2022-04-05 03:50:13,610 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=69, Invalid=531, Unknown=0, NotChecked=0, Total=600 [2022-04-05 03:50:13,610 INFO L87 Difference]: Start difference. First operand 189 states and 195 transitions. Second operand has 22 states, 21 states have (on average 2.857142857142857) internal successors, (60), 21 states have internal predecessors, (60), 19 states have call successors, (20), 2 states have call predecessors, (20), 1 states have return successors, (18), 18 states have call predecessors, (18), 18 states have call successors, (18) [2022-04-05 03:50:14,219 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 03:50:14,219 INFO L93 Difference]: Finished difference Result 192 states and 197 transitions. [2022-04-05 03:50:14,220 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2022-04-05 03:50:14,220 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 21 states have (on average 2.857142857142857) internal successors, (60), 21 states have internal predecessors, (60), 19 states have call successors, (20), 2 states have call predecessors, (20), 1 states have return successors, (18), 18 states have call predecessors, (18), 18 states have call successors, (18) Word has length 146 [2022-04-05 03:50:14,220 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 03:50:14,221 INFO L225 Difference]: With dead ends: 192 [2022-04-05 03:50:14,221 INFO L226 Difference]: Without dead ends: 189 [2022-04-05 03:50:14,221 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 161 GetRequests, 135 SyntacticMatches, 1 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=79, Invalid=623, Unknown=0, NotChecked=0, Total=702 [2022-04-05 03:50:14,222 INFO L913 BasicCegarLoop]: 82 mSDtfsCounter, 2 mSDsluCounter, 918 mSDsCounter, 0 mSdLazyCounter, 1051 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 1000 SdHoareTripleChecker+Invalid, 1051 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 1051 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2022-04-05 03:50:14,222 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 1000 Invalid, 1051 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 1051 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2022-04-05 03:50:14,222 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 189 states. [2022-04-05 03:50:14,225 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 189 to 189. [2022-04-05 03:50:14,226 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 189 states, 140 states have (on average 1.042857142857143) internal successors, (146), 140 states have internal predecessors, (146), 25 states have call successors, (25), 25 states have call predecessors, (25), 23 states have return successors, (23), 23 states have call predecessors, (23), 23 states have call successors, (23) [2022-04-05 03:50:14,226 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 189 states to 189 states and 194 transitions. [2022-04-05 03:50:14,227 INFO L78 Accepts]: Start accepts. Automaton has 189 states and 194 transitions. Word has length 146 [2022-04-05 03:50:14,227 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 03:50:14,227 INFO L478 AbstractCegarLoop]: Abstraction has 189 states and 194 transitions. [2022-04-05 03:50:14,227 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 21 states have (on average 2.857142857142857) internal successors, (60), 21 states have internal predecessors, (60), 19 states have call successors, (20), 2 states have call predecessors, (20), 1 states have return successors, (18), 18 states have call predecessors, (18), 18 states have call successors, (18) [2022-04-05 03:50:14,227 INFO L276 IsEmpty]: Start isEmpty. Operand 189 states and 194 transitions. [2022-04-05 03:50:14,228 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 155 [2022-04-05 03:50:14,228 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 03:50:14,228 INFO L499 BasicCegarLoop]: trace histogram [19, 18, 18, 18, 18, 18, 18, 17, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 03:50:14,239 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (23)] Forceful destruction successful, exit code 0 [2022-04-05 03:50:14,435 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable22,23 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 03:50:14,435 INFO L403 AbstractCegarLoop]: === Iteration 24 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 03:50:14,436 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 03:50:14,436 INFO L85 PathProgramCache]: Analyzing trace with hash 75778898, now seen corresponding path program 17 times [2022-04-05 03:50:14,436 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 03:50:14,436 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [754975091] [2022-04-05 03:50:14,436 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 03:50:14,436 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 03:50:14,447 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 03:50:14,447 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1577794487] [2022-04-05 03:50:14,447 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2022-04-05 03:50:14,447 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 03:50:14,447 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 03:50:14,448 INFO L229 MonitoredProcess]: Starting monitored process 24 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-05 03:50:14,449 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (24)] Waiting until timeout for monitored process